Estrategias mmas para minimización del makespan en la programación de una máquina con setup

Resumen

En este trabajo se aplica un algoritmo de optimización de colonia de hormigas con límites de feromona superior e inferior denominado Max–Min Ant System, para resolver problemas de programación de una máquina con tiempos de preparación dependientes de la secuencia y minimización de makespan. El estudio presenta y compara tres variantes del Max–Min Ant System, en base a la forma de actualización de feromona aplicadas a un conjunto de pro-blemas de prueba de 100 trabajos. Las variantes de los algoritmos se comparan para deter-minar la mejor de ellas y, también, con una heurística constructiva greedy del Mejor Vecino. Se concluye que adecuadas modificaciones a la estrategia de actualización de feromona mejoran significativamente la calidad de las soluciones, obteniéndose soluciones cercanas al óptimo, dado que las diferencias promedio con respecto de una cota inferior del makespan son menores al 1%.

This paper studied an ant colony optimization algorithm with upper and lower pheromone limits called the Max–Min Ant System is applied to solve the single machine scheduling pro-blem with sequence dependent setup times and makespan minimization. The study presents and compares three variants of the algorithm based on the pheromone update applied to a set of problems of size 100 jobs. The algorithms variants are compared between them and with a constructive greedy heuristic of the best neighbor. We conclude that adequate modifications to the pheromone actualization strategy improve significantly the solution quality, obtaining solution near the optimum due to the average differences less than 1% with respect to a lower bound of the makespan.