Evaluation of Genetic Algorithm and GRASP to Minimize Makespan in Flow Shop Scheduling at Different Instances of Number of Jobs and Iterations
Evaluación del Algoritmo Genético y GRASP para Minimizar el Makespan en la Programación de un Taller de Flujo en Diferentes Instancias Instancias de Número de Trabajos e Iteraciones
Keywords:
anova, genetic algorithm, GRASP, makespan, flow shop
Abstract
In this article, meta-heuristic algorithms are proposed for the production scheduling problem of a flow workshop, considered as a complete non-polynomial problem due to its complexity. The study of the problem is relevant given its usefulness in practice, for example, in factories with assembly lines or in collaborative supply chains planning. Thus, the objective of the present study consisted of evaluating two meta-heuristic algorithms, GRASP and a genetic algorithm. An experimental design was proposed to determine which factors (method, number of jobs and number of iterations) have a statistically significant effect on production scheduling completion time. According to the results, it could be observed that there is incidence of the first, second and third order of the factors, allowing to characterize the performance of the two algorithms in environments generated by the interaction of the three factors analyzed.
Downloads
References
Akhshabi, M., Haddadnia, J., Akhshabi, M. (2012). Solving flow shop scheduling problem using a parallel genetic algorithm. Procedia Technology, 1, 351-355.
Ángel-Bello, F., Álvarez, A., Pacheco, J., Martínez, I. (2011). A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times. Computers and Mathematics with Applications, 61, 797-808.
Bautista, J., Cano, A., Alfaro, R., Batalla, C. (2013). Algoritmos GRASP para solucionar el problema blocking flow shop. Multiconferencia CAEPIA'13. IX congreso español de metaheurísticas, algoritmos evolutivos y bioinspirados - MAEB 2013. Barcelona: Universitat Politécnica de Catalunya, 443-452.
Bertel, S., Billaut, J.C. (2004). A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculation. Journal of the Operational Research Society, 159, 651-662.
Castillo, T. A., Díaz, C. E., Gómez, J. D., Orduz, E. A., Niño, M. L. (2018). Optimización del makespan en el problema de Job Shop Flexible con restricciones de transporte usando Algoritmos Genéticos. Entre Ciencia e Ingeniería, 12, 105-115.
César, Y., Reyna, F., Jiménez, Y.M., Enrique, Á., León, F., Alberto, L., 2014. Influencia de los parámetros principales de un Algoritmo Genético para el Flow Shop Scheduling. Revista Cubana de Ciencias Informáticas, 8, 99–111.
Chiou, C. W., Chen, W. M., Liu, C. M., Wu, M. C. (2012). A genetic algorithm for scheduling dual flow shops. Expert Systems with Applications, 39, 1306-1314.
Choong, F., Alias, M.Y., 2011. Expert Systems with Applications Metaheuristic methods in hybrid flow shop scheduling problem. Expert Systems With Applications, 38, 10787–10793.
Engin, O., Ceran, G., Yilmaz, M. K. (2011). An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems. Applied Soft Computing Journal, 11, 3056-3065.
Feng, H., Lu, S., Li, X. (2009). Genetic algorithm for hybrid flow-shop scheduling with parrel batch processors. 2009 WASE international conference on information engineering, ICIE 2009. Jinan: IEEE Computer Society, 2, 9-13.
Gómez-Gasquet, P., Andrés, C., Lario, F. C. (2012). An agent-based genetic algorithm for hybrid flowshops with sequence dependent setup times to minimise makespan. Expert Systems with Applications, 39, 8095-8107.
Gómez, P. (2007). Un nuevo algoritmo genético basado en un sistema multiagente para la programación de la producción en un taller de flujo híbrido. XI congreso de ingeniería de organización. Madrid: Asociación para el Desarrollo de la Ingeniería de Organización,1675-1685.
Hekmatfar, M., Fatemi Ghomi, S. M. T., Karimi, B. (2011). Two stage reentrant hybrid flow shop with setup times and the criterion of minimizing makespan. Applied Soft Computing Journal, 11, 4530-4539.
Hentous, H., Merabti, B. (2010). A branch and bound heuristic for the flow shop problem. Proceedings - 4th international conference on sensor technologies and applications, SENSORCOMM 2010. Venice: IEEE Computer Society, 352-356.
Hsu, H. M., Hsiung, Y., Chen, Y. Z., Wu, M. C. (2009). A GA methodology for the scheduling of yarn-dyed textile production. Expert Systems with Applications, 36, 12095-12103.
Hussain, K., Najib, M., Salleh, M., Cheng, S., Shi, Y. (2018). Metaheuristic research: a comprehensive survey. Artificial Intelligence Review, 52, 2191-2233.
Lagos, D., Mancilla, R., Leal, P. (2019). Evaluación de la solución obtenida con una metaheurística de secuenciamiento mediante la incorporación de elementos de variabilidad. Revista Técnica de la Facultad de Ingeniería, Univiversidad del Zulia, 1, 209-212.
Mahdavi, I., Mojarad, M.S., Javadi, B., Tajdin, A. (2008). A genetic approach for solving a hybrid flow shop scheduling problem. 2008 IEEE international conference on industrial engineering and engineering management, IEEM 2008. Singapore: IEEE, 1214-1218.
Ocampo, T., Mirledy, E., Grisales, R., Steven, Y. O. V., Echeverri, G. (2006). Algoritmo genético modificado aplicado al problema de secuenciamiento de tareas en sistemas de producción lineal - Flow shop. Scientia Et Technica, 7, 285-290.
Prabhaharan, G., Khan, S.H., Rakesh, L., 2006. Implementation of grasp in flow shop scheduling. The International Journal of Advanced Manufacturing Technology, 30, 1126–1131.
Qiao, P., Sun, C. (2011). Research on hybrid flow-shop scheduling problem based on improved immune particle swarm optimization. 2nd international conference on artificial intelligence, management science and electronic commerce, AIMSEC. Deng Feng: IEEE, 4240-4243.
Resende, M. G. C., González, J. L. (2003). GRASP: Procedimientos de búsquedas miopes aleatorizados y adaptativos. Inteligencia artificial. Revista Iberoamericana de Inteligencia Artificial, 7, 61-76.
Resende, M. G. C., Ribeiro, C. C. (2016). Optimization by GRASP. 1st ed. New York: Springer Science+Business Media.
Salazar Hornig, E., Figueroa Morales, B., 2012. Minimización de la tardanza para el flowshop flexible con setup utilizando heurísticas constructivas y un algoritmo genético. Ingeniare. Revista chilena de ingeniería, 20, 89–98.
Shabtay, D. (2012). The just-in-time scheduling problem in a flow-shop scheduling system. European Journal of Operational Research, 216, 521-532.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
Tang, J., Zhang, G., Lin, B., Zhang, B. (2010). Hybrid genetic algorithm for flow shop scheduling problem. International conference on intelligent computation technology and automation, ICICTA 2010. Changsha: IEEE, 2, 449-452.
Tavares Neto, R.F., Godinho Filho, M. (2013). Literature review regarding ant colony optimization applied to scheduling problems: Guidelines for implementation and directions for future research. Engineering Applications of Artificial Intelligence, 26, 150-161.
Vallada, E., Ruiz, R. (2011). A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research, 211, 612-622.
Villalba, G., Castro, F. De, Saldarriaga, J. G. (2005). Algoritmos de optimización combinatoria (AOC) aplicados al diseño de redes de distribución de agua potable. Revista de Ingeniería Universidad de los Andes, 22, 118-125.
Yalaoui, N., Mahdi, H., Amodeo, L., Yalaoui, F. (2011). A particle swarm optimization under fuzzy logic controller to solve a scheduling problem. International Conference on Communications, Computing and Control Applications (CCCA), Hammamet: IEEE, 1–6.
Zabihzadeh, S.S., Rezaeian, J., 2016. Two meta-heuristic algorithms for flexible flow shop scheduling problem with robotic transportation and release time. Applied Soft Computing Journal, 40, 319–330.
Zhang, S. (2010). Large-scale flow shop scheduling based on genetic algorithm.. 2nd international conference on education technology and computer, ICETC 2010. Shanghai: IEEE, 1, 308-310.
Zobolas, G.I., Tarantilis, C.D., Ioannou, G., 2009. Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Computers & Operations Research, 36, 1249–1267.
Ángel-Bello, F., Álvarez, A., Pacheco, J., Martínez, I. (2011). A heuristic approach for a scheduling problem with periodic maintenance and sequence-dependent setup times. Computers and Mathematics with Applications, 61, 797-808.
Bautista, J., Cano, A., Alfaro, R., Batalla, C. (2013). Algoritmos GRASP para solucionar el problema blocking flow shop. Multiconferencia CAEPIA'13. IX congreso español de metaheurísticas, algoritmos evolutivos y bioinspirados - MAEB 2013. Barcelona: Universitat Politécnica de Catalunya, 443-452.
Bertel, S., Billaut, J.C. (2004). A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculation. Journal of the Operational Research Society, 159, 651-662.
Castillo, T. A., Díaz, C. E., Gómez, J. D., Orduz, E. A., Niño, M. L. (2018). Optimización del makespan en el problema de Job Shop Flexible con restricciones de transporte usando Algoritmos Genéticos. Entre Ciencia e Ingeniería, 12, 105-115.
César, Y., Reyna, F., Jiménez, Y.M., Enrique, Á., León, F., Alberto, L., 2014. Influencia de los parámetros principales de un Algoritmo Genético para el Flow Shop Scheduling. Revista Cubana de Ciencias Informáticas, 8, 99–111.
Chiou, C. W., Chen, W. M., Liu, C. M., Wu, M. C. (2012). A genetic algorithm for scheduling dual flow shops. Expert Systems with Applications, 39, 1306-1314.
Choong, F., Alias, M.Y., 2011. Expert Systems with Applications Metaheuristic methods in hybrid flow shop scheduling problem. Expert Systems With Applications, 38, 10787–10793.
Engin, O., Ceran, G., Yilmaz, M. K. (2011). An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems. Applied Soft Computing Journal, 11, 3056-3065.
Feng, H., Lu, S., Li, X. (2009). Genetic algorithm for hybrid flow-shop scheduling with parrel batch processors. 2009 WASE international conference on information engineering, ICIE 2009. Jinan: IEEE Computer Society, 2, 9-13.
Gómez-Gasquet, P., Andrés, C., Lario, F. C. (2012). An agent-based genetic algorithm for hybrid flowshops with sequence dependent setup times to minimise makespan. Expert Systems with Applications, 39, 8095-8107.
Gómez, P. (2007). Un nuevo algoritmo genético basado en un sistema multiagente para la programación de la producción en un taller de flujo híbrido. XI congreso de ingeniería de organización. Madrid: Asociación para el Desarrollo de la Ingeniería de Organización,1675-1685.
Hekmatfar, M., Fatemi Ghomi, S. M. T., Karimi, B. (2011). Two stage reentrant hybrid flow shop with setup times and the criterion of minimizing makespan. Applied Soft Computing Journal, 11, 4530-4539.
Hentous, H., Merabti, B. (2010). A branch and bound heuristic for the flow shop problem. Proceedings - 4th international conference on sensor technologies and applications, SENSORCOMM 2010. Venice: IEEE Computer Society, 352-356.
Hsu, H. M., Hsiung, Y., Chen, Y. Z., Wu, M. C. (2009). A GA methodology for the scheduling of yarn-dyed textile production. Expert Systems with Applications, 36, 12095-12103.
Hussain, K., Najib, M., Salleh, M., Cheng, S., Shi, Y. (2018). Metaheuristic research: a comprehensive survey. Artificial Intelligence Review, 52, 2191-2233.
Lagos, D., Mancilla, R., Leal, P. (2019). Evaluación de la solución obtenida con una metaheurística de secuenciamiento mediante la incorporación de elementos de variabilidad. Revista Técnica de la Facultad de Ingeniería, Univiversidad del Zulia, 1, 209-212.
Mahdavi, I., Mojarad, M.S., Javadi, B., Tajdin, A. (2008). A genetic approach for solving a hybrid flow shop scheduling problem. 2008 IEEE international conference on industrial engineering and engineering management, IEEM 2008. Singapore: IEEE, 1214-1218.
Ocampo, T., Mirledy, E., Grisales, R., Steven, Y. O. V., Echeverri, G. (2006). Algoritmo genético modificado aplicado al problema de secuenciamiento de tareas en sistemas de producción lineal - Flow shop. Scientia Et Technica, 7, 285-290.
Prabhaharan, G., Khan, S.H., Rakesh, L., 2006. Implementation of grasp in flow shop scheduling. The International Journal of Advanced Manufacturing Technology, 30, 1126–1131.
Qiao, P., Sun, C. (2011). Research on hybrid flow-shop scheduling problem based on improved immune particle swarm optimization. 2nd international conference on artificial intelligence, management science and electronic commerce, AIMSEC. Deng Feng: IEEE, 4240-4243.
Resende, M. G. C., González, J. L. (2003). GRASP: Procedimientos de búsquedas miopes aleatorizados y adaptativos. Inteligencia artificial. Revista Iberoamericana de Inteligencia Artificial, 7, 61-76.
Resende, M. G. C., Ribeiro, C. C. (2016). Optimization by GRASP. 1st ed. New York: Springer Science+Business Media.
Salazar Hornig, E., Figueroa Morales, B., 2012. Minimización de la tardanza para el flowshop flexible con setup utilizando heurísticas constructivas y un algoritmo genético. Ingeniare. Revista chilena de ingeniería, 20, 89–98.
Shabtay, D. (2012). The just-in-time scheduling problem in a flow-shop scheduling system. European Journal of Operational Research, 216, 521-532.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
Tang, J., Zhang, G., Lin, B., Zhang, B. (2010). Hybrid genetic algorithm for flow shop scheduling problem. International conference on intelligent computation technology and automation, ICICTA 2010. Changsha: IEEE, 2, 449-452.
Tavares Neto, R.F., Godinho Filho, M. (2013). Literature review regarding ant colony optimization applied to scheduling problems: Guidelines for implementation and directions for future research. Engineering Applications of Artificial Intelligence, 26, 150-161.
Vallada, E., Ruiz, R. (2011). A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research, 211, 612-622.
Villalba, G., Castro, F. De, Saldarriaga, J. G. (2005). Algoritmos de optimización combinatoria (AOC) aplicados al diseño de redes de distribución de agua potable. Revista de Ingeniería Universidad de los Andes, 22, 118-125.
Yalaoui, N., Mahdi, H., Amodeo, L., Yalaoui, F. (2011). A particle swarm optimization under fuzzy logic controller to solve a scheduling problem. International Conference on Communications, Computing and Control Applications (CCCA), Hammamet: IEEE, 1–6.
Zabihzadeh, S.S., Rezaeian, J., 2016. Two meta-heuristic algorithms for flexible flow shop scheduling problem with robotic transportation and release time. Applied Soft Computing Journal, 40, 319–330.
Zhang, S. (2010). Large-scale flow shop scheduling based on genetic algorithm.. 2nd international conference on education technology and computer, ICETC 2010. Shanghai: IEEE, 1, 308-310.
Zobolas, G.I., Tarantilis, C.D., Ioannou, G., 2009. Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Computers & Operations Research, 36, 1249–1267.
Published
2021-12-29
How to Cite
Paredes Quevedo, J. J., Soto-Chávez, L.-E., Alpala, L. O. and León-Batallas, A. (2021) “Evaluation of Genetic Algorithm and GRASP to Minimize Makespan in Flow Shop Scheduling at Different Instances of Number of Jobs and Iterations: Evaluación del Algoritmo Genético y GRASP para Minimizar el Makespan en la Programación de un Taller de Flujo en Diferentes Instancias Instancias de Número de Trabajos e Iteraciones”, Rev. Téc. Fac. Ing. Univ. Zulia, 45(1), pp. 48 - 57. doi: 10.22209/rt.v45n1a05.
Issue
Section
Artículos de Investigación
Copyright (c) 2021 Juan José Paredes Quevedo, Luis-Enrique Soto-Chávez, Luis Omar Alpala, Alberto León-Batallas
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright
La Revista Técnica de la Facultad de Ingeniería declara que los derechos de autor de los trabajos originales publicados, corresponden y son propiedad intelectual de sus autores. Los autores preservan sus derechos de autoría y publicación sin restricciones, según la licencia pública internacional no comercial ShareAlike 4.0
_2.04__.27_p__._m__.__.png)
