Makespan Minimization on Unrelated Parallel Machines Scheduling Problem with Sequence Dependent Setup Times by a VNS/ACO Hybrid Algorithm
Article Sidebar
The total or partial reproduction of the contents of the journal for educational, research, or academic purposes is authorized as long as the source is cited. For reproduction for other purposes, express authorization from the Sello Editorial Universidad de Medellín is required.
Main Article Content
Abstract
This paper proposes a hybrid heuristic that combines Variable Neighborhood Search (VNS) with Ant Colony Optimization (ACO) to solve the scheduling problem of nonrelated parallel machines with sequence dependent setup times in order to minimize the makespan. The Variable Neighborhood Search is proposed to solve the scheduling problem with a descending scheme in a first phase, with an ACO algorithm, which successively reorder the jobs in the machine with the largest makespan in a second phase. An experimental study was performed using test problems from the literature showing that the second phase of the algorithm improves the solution obtained in the first phase. The results obtained are also compared with other methods in the literature proving to be a competitive method.
Article Details
References
M. Helal, G. Rabadi y A. Al-Salem, 'A tabu search algorithm to minimize the makespan for the unrelated parallel machines scheduling problem with setup times,' International Journal of Operations Research, vol. 3, n.° 3, pp. 182-192, 2006.
G. Rabadi, R. J. Moraga. y A. Al-Salem, 'Heuristics for the unrelated parallel machine scheduling problem with setup times',Journal of Intelligent Manufacturing, vol. 17, n.° 1, pp. 85-97, 2006.
J-P. Arnaout, R. Musa y G. Rabadi, 'A Two-stage Ant Colony Optimization Algorithm to Minimize the Makespan on Unrelated Parallel Machines'part II: Enhancements and Experimentations,' Journal of Intelligent Manufacturing, vol. 25, n.° 1, pp. 43-53, 2014.
E. Vallada y R. Ruiz, 'A Genetic Algorithm for the Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times,' European Journal of Operational Research, vol. 211, n.°3, pp. 612-622, 2011.
K-Ch. Ying, Z-J. Lee y Sh-W. Lin, 'Makespan minimization for scheduling unrelated parallel machines with setup times,' Journal of Intelligent Manufacturing, vol 23, n.° 5, pp. 1795-1803, 2012.
J. Behnamian, M. Zandieh y S. F. Ghomi, 'Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm,' Expert Systems with Applications, vol. 36, n.° 6, pp. 9637-9644, 2009.
M. Mateo, J. Teghem y D. Tuyttens, 'A bi-objective parallel machine problem with eligibility, release dates and delivery times of the jobs,' International Journal of Production Research, vol 56, n.° 3, pp. 1030-1053, 2018.
Y-I. Kim y H-J. Kim, 'Rescheduling of unrelated parallel machines with job-dependent setup times under forecasted machine breakdown,' International Journal of Production Research, Online: junio 2020. https://doi.org/10.1080/00207543.2020.1775910
N. Mladenovic y P. Hansen, 'Variable neighborhood search,' Computers & Operations Research, vol. 24, n.° 11, pp. 1097-1100, 1997.
R. Driessel y L. Mönch, 'Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times,' Computers & Industrial Engineering, vol. 61, n.° 2, pp. 33-345, 2011.
P. Hansen, N. Mladenovic y J. Moreno, 'Búsqueda de entorno variable,' Revista Iberoamericana de Inteligencia Artificial, vol. 7, n.°19, pp. 77-92, 2003.
M. Dorigo, 'Optimization, Learning and Natural Algorithms (in Italian).' Ph.D. Thesis, Dipartimento de Elettronica, Politécnico de Milán (Italy),1992.
E. Salazar y C. Avila, 'Heurística GRASP para la minimización del makespan en máquinas paralelas no relacionadas con tiempos de preparación dependientes de la secuencia,' Ingeniare - Revista Chilena de Ingeniería, vol. 25, n.°3, pp. 524 - 34. 2017.
T. Peñaloza, 'Algoritmo híbrido GRASP/ACO aplicado al problema de minimización de makespan en máquinas paralelas no relacionadas con tiempos de setup dependientes de la secuencia'. Memoria de Título Ingeniería Civil Industrial, Universidad de Concepción (Chile), Julio 2015.
E. Salazar y J. C. Medina, 'Minimización del makespan en máquinas paralelas idénticas con tiempos de preparación dependientes de la secuencia utilizando un algoritmo genético,' Ingeniería, Investigación y Tecnología, vol. 14, n.° 1, pp. 43-51, 2013.
O. H. Ibarra y C. E. Kim, 'Heuristic algorithms for scheduling independent tasks on nonidentical processors,' Journal of the ACM, vol. 24, n.° 2, pp. 280-289, 1977.
M. Dorigo y L. M. Gambardella, 'Ant colony system: a cooperative learning approach to the traveling salesman problem,' IEEE Transactions on Evolutionary Computation, vol. 1, n.° 1, pp. 53-66, 1997.
J-P. Arnaout, G. Rabadi y R. Musa, 'A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times,' Journal of Intelligent Manufacturing, vol.
, n.° 6, pp. 693-701, 2009.
M. Dorigo y T. Stützle, Ant colony optimization, MIT Press, 2004.
E. Salazar, 'Programación de Sistemas de Producción con SPS_Optimizer,' Revista ICHIO, vol. 1, n.°2, pp. 33-46, 2010.