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

Evaluation of Genetic Algorithm and GRASP to Minimize Makespan in Flow Shop Scheduling at Different Instances of Number of Jobs and Iterations

• Juan José Paredes Quevedo Facultad Ciencias e Ingeniería, Universidad Estatal de Milagro (UNEMI), Km 1.5 vía Km 26, Ciudadela Universitaria Milagro 09150, Ecuador https://orcid.org/0000-0002-9689-1957
• Luis-Enrique Soto-Chávez Universidad de Guayaquil, Facultad de Ingeniería Industrial, Guayaquil, Ecuador https://orcid.org/0000-0001-8854-6881
• Luis Omar Alpala Programa de Ingeniería Industrial, Grupo de Investigación Eslinga, Universidad Cooperativa de Colombia-Pasto (Nariño-Colombia) Código Postal 52002 http://orcid.org/0000-0002-8436-7090
• Alberto León-Batallas Facultad Ciencias e Ingeniería, Universidad Estatal de Milagro (UNEMI), Km 1.5 vía Km 26, Ciudadela Universitaria Milagro 09150, Ecuador https://orcid.org/0000-0001-6643-4694

DOI: https://doi.org/10.22209/rt.v45n1a05

Palabras clave: anova, algoritmo genético, GRASP, makespan, taller de flujo

Resumen

En este artículo se plantean algoritmos meta-heurísticos para el problema de programación de producción de un taller de flujo, considerado como un problema no polinómico completo debido a su complejidad. El estudio de la problemática es relevante dada su utilidad en la práctica, por ejemplo, en fábricas con líneas de ensamblaje o en la planificación de cadenas de suministro colaborativas. De esta manera, el objetivo del presente estudio consistió en evaluar dos algoritmos meta-heurísticos, GRASP y algoritmo genético. Se planteó un diseño experimental para determinar cuáles factores (método, número de trabajos y número de iteraciones) tienen un efecto estadísticamente significativo en el tiempo de finalización de programación de producción. Según los resultados se pudo observar que existe incidencia tanto de primer como de segundo y tercer orden de los factores, permitiendo caracterizar el desempeño de los dos algoritmos en entornos generados por la interacción de los tres factores analizados.

Citas

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.