Avaliação do Algoritmo Genético e GRASP para Minimizar o Makespan na Programação de uma Oficina de Fluxo em Diferentes Instâncias de Número de trabalhos e Iterações
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
Palavras-chave:
anova, algoritmo genético, GRASP, makespan, oficina de fluxo
Resumo
Neste artigo, algoritmos meta-heurísticos são propostos para o problema de programação de produção de uma oficina de fluxo, considerado um problema não polinomial completo devido à sua complexidade. O estudo do problema é relevante dada a sua utilidade na prática, por exemplo, em fábricas com linhas de montagem ou no planejamento de cadeias produtivas colaborativas. Assim, o objetivo deste estudo consistiu em avaliar dois algoritmos meta-heurísticos, GRASP e um algoritmo genético. Um projeto experimental foi proposto para determinar quais fatores (método, numero de trabalhos e iterações) têm um efeito estatisticamente significativo no tempo de conclusão do cronograma de produção. De acordo com os resultados, observou-se que há incidência tanto da primeira, segunda e terceira ordem dos fatores, permitindo caracterizar o desempenho dos dois algoritmos, em ambientes gerados pela interação dos três fatores analisados.
Downloads
Não há dados estatísticos.
Referências
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.
Publicado
2021-12-29
Como Citar
Paredes Quevedo, J. J., Soto-Chávez, L.-E., Alpala, L. O. e León-Batallas, A. (2021) «Avaliação do Algoritmo Genético e GRASP para Minimizar o Makespan na Programação de uma Oficina de Fluxo em Diferentes Instâncias de Número de trabalhos e Iterações: 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», Revista Técnica de la Facultad de Ingeniería. Universidad del Zulia, 45(1), pp. 48 - 57. doi: 10.22209/rt.v45n1a05.
Edição
Secção
Artículos de Investigación
Direitos de Autor (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)
