Un algoritmo exacto para la secuenciación de piezas en una máquina con tiempos de preparación dependientes de la secuencia

Resumen

Se considera el problema de secuenciar trabajos en una única máquina con tiempos de preparación dependientes de la secuencia. Las piezas se agrupan en familias y los tiempos de preparación están asociados a las familias. El objetivo es minimizar el retraso total. Se propone un algoritmo exacto del tipo Bounded Dynamic Programming (BDP) para su resolución que, en general, requiere la exploración de un número menor de vértices que un procedimiento del tipo branch and bound (o de programación dinámica no acotada). Se define un procedimiento de acotación análogo al utilizado para el problema equivalente sin tiempos de preparación. El procedimiento implementado se ha probado sobre un conjunto de ejemplares con diferente número de trabajos y familias. Los resultados obtenidos muestran que el algoritmo es muy competitivo. Palabras clave: Secuenciación, Retraso total, Bounded Dynamic Programming.