A simulated annealing genetic algorithm for flexible job shop problem with sequence-dependent setup times (fjsp-sdst)
Article Sidebar
Main Article Content
Abstract
Production scheduling is one of the most critical issues in manufacturing systems and has been widely studied in the literature. The job shop scheduling problems (JSSP) are among the most studied combinatorial problems, where a set of jobs must be processed in a set of specific machines. Each job consists of a specific set of operations, which must be processed according to a specific order. Flexible job shop problem (FJSP) it is a generalization of the classic JSSP where each operation can be processed by more than one machine. The FJSP problem is considered an Np-hard type problem in which two difficulties are covered: the allocation problem and sequencing of operations. This document addresses the FJSP problem with sequence-dependent setup times (FJSP-SDST) where Makespan is minimized. We propose a hybrid algorithm based on a Genetic Algorithm (GA) and Simulated Annealing (SA) to solve this problem. To evaluate the performance of our algorithm, we compare our results with other methods in the literature. Solving the scenarios with results close to those found in the literature in reasonable computational times.
Downloads
Article Details
This journal is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0). The guiding principle of Creative Commons licenses is creative freedom. This system complements copyright law without opposing it, recognizing its importance within our culture. The content of the articles is the sole responsibility of each author and does not, in any way, commit the journal or the institution. The dissemination and reproduction of titles, abstracts, and full content are permitted for academic, scientific, and cultural purposes, provided that the corresponding source is properly cited. This work may not be used for commercial purposes.
References
Azzouz, A., Ennigrou, M., & Ben Said, L. (2017). A self-adaptive hybrid algorithm for solving flexible job-shop problem with sequence dependent setup time. Procedia Computer Science, 112, 457–466. https://doi.org/10.1016/j.procs.2017.08.023
Bagheri, A., & Zandieh, M. (2011). Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—Variable neighborhood search approach. Journal of Manufacturing Systems, 30(1), 8–15. https://doi.org/10.1016/J.JMSY.2011.02.004
Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41(3), 157–183. https://doi.org/10.1007/BF02023073
Brucker, P., & Schlie, R. (1990). Job-shop scheduling with multi-purpose machines. Computing, 45(4), 369–375. https://doi.org/10.1007/BF02238804
Bula, G. A. (2004). Programación de operaciones en el taller de trabajo utilizando la meta - heurística de recocido simulado. Revista UIS Ingenierías, 3(1), 8. Retrieved from Se desarrolla una aplicación de la meta-heurística de recocido simulado a la programación enel taller de trabaja para dos configuracionesjlow-shop y job-shop. El desarrollo de los algoritmosse hace en el lenguaje de programación Java versión 1.3.
Choi, I.-C., & Choi, D.-S. (2002). A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups. Computers & Industrial Engineering, 42(1), 43–58. https://doi.org/https://doi.org/10.1016/S0360-8352(02)00002-5
Cruz-Chávez, M. A., Martínez-Rangel, M. G., & Cruz-Rosales, M. H. (2017). Accelerated simulated annealing algorithm applied to the flexible job shop scheduling problem. International Transactions in Operational Research, 24(5), 1119–1137. https://doi.org/10.1111/itor.12195
Gen, M., Gao, J., & Lin, L. (2009). Multistage-based genetic algorithm for flexible job-shop scheduling problem. Studies in Computational Intelligence, 187, 183–196. https://doi.org/10.1007/978-3-540-95978-6_13
González, M. A., Vela, C. R., & Varela, R. (2013). An efficient memetic algorithm for the flexible job shop with setup times. ICAPS 2013 - Proceedings of the 23rd International Conference on Automated Planning and Scheduling, 91–99.
He, Y., Weng, W., & Fujimura, S. (2017). Improvements to genetic algorithm for flexible job shop scheduling with overlapping in operations. 2017 IEEE/ACIS 16th International Conference on Computer and Information Science (ICIS), 791–796. https://doi.org/10.1109/ICIS.2017.7960100
Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence.
Hurink, J., Jurisch, B., & Thole, M. (1994). Tabu search for the job-shop scheduling problem with multi-purpose machines. Operations-Research-Spektrum, 15(4), 205–215. https://doi.org/10.1007/BF01719451
Imanipour, N. (2006). Modeling amp; Solving Flexible Job Shop Problem With Sequence Dependent Setup Times. 2006 International Conference on Service Systems and Service Management, 2, 1205–1210. https://doi.org/10.1109/ICSSSM.2006.320680
Kacem, I., Hammadi, S., & Borne, P. (2002). Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 32(1), 1–13. https://doi.org/10.1109/TSMCC.2002.1009117}
Kato, E. R. R., Aranha, G. D. de A., & Tsunaki, R. H. (2018). A new approach to solve the flexible job shop problem based on a hybrid particle swarm optimization and Random-Restart Hill Climbing. Computers and Industrial Engineering, 125(August), 178–189. https://doi.org/10.1016/j.cie.2018.08.022
Lee, K.-., Yamakawa, T., & Lee, K.-M. (1998). A genetic algorithm for general machine scheduling problems. 1998 Second International Conference. Knowledge-Based Intelligent Electronic Systems. Proceedings KES’98 (Cat. No.98EX111), 2, 60–66 vol.2. https://doi.org/10.1109/KES.1998.725893
Najid, N. M., Dauzere-Peres, S., & Zaidat, A. (2002). A modified simulated annealing method for flexible job shop scheduling problem. IEEE International Conference on Systems, Man and Cybernetics, 5, 6 pp. vol.5-. https://doi.org/10.1109/ICSMC.2002.1176334
Nouiri, M., Bekrar, A., Jemai, A., Niar, S., & Ammari, A. C. (2018). An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem. Journal of Intelligent Manufacturing, 29(3), 603–615. https://doi.org/10.1007/s10845-015-1039-3
Pezzella, F., Morganti, G., & Ciaschetti, G. (2008). A genetic algorithm for the Flexible Job-shop Scheduling Problem. Computers & Operations Research, 35(10), 3202–3212. https://doi.org/https://doi.org/10.1016/j.cor.2007.02.014
Saidi-Mehrabad, M., & Fattahi, P. (2007). Flexible job shop scheduling with tabu search algorithms. The International Journal of Advanced Manufacturing Technology, 32(5), 563–570. https://doi.org/10.1007/s00170-005-0375-4
Shen, L., Dauzère-pérès, S., & Neufeld, J. S. (2018). Solving the flexible job shop scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 265, 503–516. https://doi.org/10.1016/j.ejor.2017.08.021
Teekeng, W., & Thammano, A. (2012). Modified Genetic Algorithm for Flexible Job-Shop Scheduling Problems. Procedia Computer Science, 12, 122–128. https://doi.org/10.1016/j.procs.2012.09.041
Teekeng, W., Thammano, A., Unkaw, P., & Kiatwuthiamorn, J. (2016). A new algorithm for flexible job-shop scheduling problem based on particle swarm optimization. Artificial Life and Robotics, 21(1), 18–23. https://doi.org/10.1007/s10015-015-0259-0
Zhang, G., Gao, L., & Shi, Y. (2011). An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications, 38(4), 3563–3573. https://doi.org/10.1016/j.eswa.2010.08.145