Como Citar
Díaz Bohórquez, C., Lozano Suarez, L., & Torres Cárdenas, F. (2020). Un algoritmo híbrido genético para el problema job shop flexible con tiempos de alistamiento dependientes de la secuencia (fjsp-sdst). Enfoque Disciplinario, 5(1), 16-29. https://doi.org/10.70165/enfdis.v5i1.282
Resumo
La programación de producción es uno de los temas más críticos en los sistemas de fabricación y ha sido ampliamente estudiado en la literatura. Los problemas de programación del taller (JSSP) se encuentran entre los problemas combinatorios más estudiados, donde un conjunto de trabajos deben procesarse en un conjunto de máquinas específicas. Cada trabajo consta de un conjunto específico de operaciones, que deben procesarse de acuerdo con un orden determinado. El problema del taller de trabajo flexible (FJSP) es una generalización del JSSP clásico donde cada operación puede ser procesada por más de una máquina, el problema FJSP es considerado un problema de tipo Np-hard en el que se cubren dos dificultades: el problema de asignación de máquinas y la secuenciación de operaciones. En este documento se aborda el problema FJSP con tiempos de alistamiento dependientes de la secuencia (FJSP-SDST) en el que se busca minimizar el Makespan. Proponemos un algoritmo hibrido basado en un algoritmo genético (GA) y recocido simulado (SA) para resolver este problema. Para evaluar el rendimiento de nuestro algoritmo, comparamos nuestros resultados con otros métodos existentes en la literatura. Resolviendo los escenarios con resultados cercanos a los encontrados en la literatura en tiempos computacionales razonables.
Referências
Amiri, M., Zandieh, M., Yazdani, M., & Bagheri, A. (2010). A variable neighbourhood search algorithm for the flexible job-shop scheduling problem. International Journal of Production Research, 48(19), 5671–5689. https://doi.org/10.1080/00207540903055743
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
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
Downloads
Não há dados estatísticos.