Evaluación de algoritmos bioinspirados para la solución del problema de planificación de trabajos

Edson Flórez, Nelson Díaz, Wilfredo Gómez, Lola Bautista, Darío Delgado

Resumen


En el presente trabajo se utilizaron Metaheurísticas de inspiración biológica, como sistemas inmunes artificiales y los algoritmos de colonias de hormigas que se basan en características y comportamientos de los seres vivos aplicables en el área computacional. Se presenta una evaluación de soluciones bioinspiradas para el problema de optimización combinatoria de planificación de trabajos, denominado Job shop Scheduling, cuyo objetivo es encontrar una configuración o secuencia de trabajos que requiera la menor cantidad de tiempo para ser ejecutada en las máquinas disponibles. El desempeño de los algoritmos fue caracterizado y evaluado para instancias de referencia del problema de Job Shop Scheduling, comparando la calidad de las soluciones obtenidas respecto a la mejor solución conocida (BKS por sus siglas en inglés) de los métodos más eficaces. Las soluciones fueron valoradas en dos aspectos, en calidad tomando como referente el makespan, que corresponde al tiempo que tardan en realizarse todos los trabajos, y como métrica de desempeño se tomó el número de evaluaciones que realiza el algoritmo para obtener la mejor solución.

Palabras clave


Algoritmos Bioinspirados; Job Shop Scheduling; Metaheurísticas; Optimización Combinatoria; Planificación de Tareas

Texto completo:

PDF HTML

Referencias


M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, 1979, p. 340.

C. A. C. Coello, D. R. Cortés, and N. C. Cortés, “Job Shop Scheduling using the Clonal Selection Principle,” Mexico DF, 2004.

A. Manne, “On the Job-Shop Scheduling Problem,” Oper. Res., vol. vol. 8, no. no. 2, pp. 219–223, 1960.

M. R. Garey, D. S. Johnson, and R. Sethi, “The Complexity of Flowshop and Jobshop Scheduling,” Math. Oper. Res., vol. 1, no. 2, pp. 117–129, 1976.

F. Ghedjati, “Heuristics and a hybrid meta-heuristic for a generalized job-shop scheduling problem,” IEEE Congr. Evol. Comput., pp. 1–8, Jul. 2010.

C. Blum and A. Roli, “Metaheuristics in Combinatorial Optimization : Overview and Conceptual Comparison,” vol. 35, no. 3, pp. 268–308, 2003.

S. Thomsen, “Metaheuristics combined with branch & bound.,” Copenhagen, Denmark, 1997.

M. G. C. Resende and C. C. Ribeiro, “Greedy randomized adaptive search procedures: Advances, hybridizations, and applications,” in Handbook of Metaheuristics, Springer, 2010, pp. 283–319.

D. De Inform, T. Universidad, and S. Mar, “Estado del Arte del Job Shop Scheduling Problem Introducci ´ on Definici ´ on del Problema,” pp. 1–8, 2006.

M.Tupia, “Un algoritmo GRASP para resolver el problema de la programación de tareas dependientes en máquinas diferentes (task scheduling),” San Marcos, 2005.

S. Binato, W. J. Hery, and D. M. Loewenstern, “A grasp for job shop scheduling,” no. March, pp. 1–17, 2000.

M. Ventresca and B. M. Ombuki, “Ant Colony Optimization for Job Shop Scheduling Problem,” no. February, 2004.

Z. Problemler, Y. Ba, and N. D. E. Yen, “A NEW APPROACH TO SOLVE FLOWSHOP SCHEDULING PROBLEMS BY ARTIFICIAL IMMUNE SYSTEMS,” vol. 8, no. 1, pp. 12–27, 2007.

T. Witkowski, P. Antczak, and A. Antczak, “Solving the Flexible Open-Job Shop Scheduling Problem with GRASP and Simulated Annealing,” Artif. Intell. Comput. Intell., vol. vol. 2, p. 437,442,2010

S. R. Lawrence, “Resource-Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques,” Carnegie-Mellon University, 1984.

D. Applegate y W. Cook, “A study of the Job shop scheduling problem.pdf,” ORSA J. Comput., vol. 3, pp. 149–156, 1991.

A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing. Springer Berlin Heidelberg, 2003.

M. Dorigo and G. Di Caro, “Ant colony optimization: a new meta-heuristic,” in Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on, 1999, vol. 2, p. -1477 Vol. 2.

J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Neural Networks, 1995. Proceedings., IEEE International Conference on, 1995, vol. 4, pp. 1942–1948 vol.4.

E. Flórez, W. Gómez, and L. Bautista, “AN ANT COLONY OPTIMIZATION ALGORITHM FOR JOB SHOP SCHEDULING PROBLEM.,” Int. J. Artif. Intell. Appl., vol. 4, no. 4, 2013.

L. N. De Castro, C. Brazil, and F. J. Von Zuben, “The Clonal Selection Algorithm with Engineering Applications 1,” no. July, pp. 36–37, 2000.

W. A. Gómez Bueno, M. I. Cuadrado Morad, and H. Arguello Fuentes, “Algoritmo Basado en Una Red Inmune Artificial para La Alineación de Patrones de Puntos,” Rev. La Esc. Colomb. Ing., vol. v.86, pp. 25 – 33, 2012.

U. Garain, M. P. Chakraborty, and D. Dasgupta, “Recognition of Handwritten Indic Script using Clonal Selection Algorithm,” in Artificial Immune Systems, 2006, pp. 256–266.

N. C. Cortes and C. A. C. Coello, “Multiobjective Optimization using Ideas from the Clonal Selection Principle,” in Genetic and Evolutionary Computation—GECCO 2003, 2003, pp. 158–170.

F. O. de França, F. J. Von Zuben, and L. N. de Castro, “An artificial immune network for multimodal function optimization on dynamic environments,” Proc. 2005 Conf. Genet. Evol. Comput. - GECCO ’05, p. 289, 2005.

L. N. de Castro and F. J. Von Zuben, “Learning and optimization using the clonal selection principle,” IEEE Trans. Evol. Comput., vol. 6, no. 3, pp. 239–251, Jun. 2002.

J. Brownlee, “OAT HowTo : High-Level Domain , Problem , and Algorithm Implementation,” no. December, pp. 1–6, 2007.

N. E. D. DIAZ and L. J. L. Martínez, “Implementación de un Algoritmo Inmune Artificial Aplicado en el Área de Planificación de Recursos,” Universidad Industrial de Santander, 2012.

N. Diaz, J. Luna, W. Gomez, and L. Bautista, “Algoritmo Inmune de Selección Clonal para el problema de Job Shop Scheduling,” in IV Congreso Internacional de Computación e Informática, 2013.

D. Cortés Rivera, “Un Sistema Inmune Artificial para resolver el problema del Job Shop Scheduling,” CINVESTAV, 2004.

M. H. Parga, M. H. Vargas, J. J. Arango, Construcción de una herramienta de análisis y evaluación soportada en el diseño de Información. I+ D REVISTA DE INVESTIGACIONES, 1(1), 28–34, 2013.

D. A. B. Gómez, and G. I. R. Lozano, Incidencia de la ética en la productividad, a la luz de los planteamientos de García-Echevarría, Gómez-Pérez, Guédez, y Morris. Estudio de caso en 4 empresas. I+ D REVISTA DE INVESTIGACIONES, 10(2), 62–78, 2017.




DOI: https://doi.org/10.33304/revinv.v11n1-2018011

Enlaces de Referencia

  • Por el momento, no existen enlaces de referencia




Universidad de Investigación y Desarrollo - UDI Calle 9 N° 23-55 PBX +57 76 352525 Ext 214 Bucaramanga, Santander, Colombia. Email: revistadeinvestigaciones@udi.edu.co