Un algoritmo branch-and-bound doble para resolver el problema flow-shop con bloqueos

Resumen

Se resuelve el problema de flow-shop sin espacio de almacenaje intermedio entre máquinas con una función objetivo consistente en minimizar el tiempo total de realización de todas las piezas. Se limita la consideración a soluciones consistentes en una única permutación. Se usa un algoritmo branch-and-bound doble, adecuado para el cálculo paralelo, y heurísticas auxiliares para alcanzar una buena solución inicial. El procedimiento heurístico se divide en dos pasos: la obtención de una permutación y la aplicación de un procedimiento de mejora local. La mejora se aplica sobre la heurística NEH. Ya que el problema de flow-shop con stocks intermedios es una relajación del problema sin ellos, los procedimientos desarrollados para este problema se pueden usar en ambos. Por ejemplo, se puede adaptar la acotación de Nabeshima o Lageweg. Además ambos problemas gozan de la propiedad de reversibilidad. Así, el un procedimiento branch and bound se puede aplicar a las instancias directa e inversa a la vez. El algoritmo de branch-andbound LOMPEN se diseñó inicialmente para ejemplares de flow-shop con buffers y se ha adaptado fácilmente para ejemplares de flow-shop sin buffers. El algoritmo ha demostrado su potencia al determinar soluciones óptimas inéditas en ejemplares de la colección de Taillard. Palabras clave: programación, flow-shop con bloqueos, algoritmos branch-and-bound.