Evaluation of bioinspired algorithms for the solution of the job scheduling problem.
DOI:
https://doi.org/10.33304/revinv.v11n1-2018011Keywords:
Bio-Inspired Algorithms, Job Shop Scheduling, Metaheuristics, Combinatorial Optimization, SchedulingAbstract
In this research we used bio-inspired metaheuristics, as artificial immune systems and ant colony algorithms that are based on a number of characteristics and behaviors of living things that are interesting in the computer science area. This paper presents an evaluation of bio-inspired solutions to combinatorial optimization problem, called the Job Shop Scheduling or planning work, in a simple way the objective is to find a configuration or job stream that has the least amount of time to be executed in machine settings. The performance of the algorithms was characterized and evaluated for reference instances of the job shop scheduling problem, comparing the quality of the solutions obtained with respect to the best known solution of the most effective methods. The solutions were evaluated in two aspects, first in relation of quality of solutions, taking as reference the makespan and secondly in relation of performance, taking the number evaluations performed by the algorithm to obtain the best solution.Downloads
References
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.
