Minimización del makespan para el problema de máquinas paralelas no relacionadas con tiempos de setup dependientes de la secuencia mediante un algoritmo híbrido VNS/ACO*
Barra lateral del artículo
Descargas
Sección
Queda autorizada la reproducción total o parcial de los contenidos de la revista con finalidades educativas, investigativas o académicas siempre y cuando sea citada la fuente. Para poder efectuar reproducciones con otros propósitos, es necesario contar con la autorización expresa del Sello Editorial Universidad de Medellín.
Contenido principal del artículo
Resumen
Se propone una heurística híbrida combinando Variable Neighborhood Search (VNS) y Ant Colony Optimization (ACO) para resolver el problema de programación de máquinas paralelas no relacionadas con tiempos de preparación dependientes de la secuencia con el objetivo de minimizar el makespan. La búsqueda en entornos variables se propone con un esquema descendente resolviendo en una primera etapa el problema de programación de los trabajos a las máquinas, y luego, en una segunda etapa, un algoritmo ACO, reordena sucesivamente los trabajos en la máquina de mayor makespan. Se realizan pruebas experimentales sobre un conjunto de problemas de prueba de la literatura, mostrando que al aplicar la segunda etapa de la metaheurística propuesta se mejoran las soluciones obtenidas en la primera etapa del algoritmo y que al comparar los resultados obtenidos con otros métodos de la literatura resulta ser un método competitivo.
Detalles del artículo
Cómo citar
Referencias
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.