Production scheduling with sequence-dependent setups and job release times

Abstract

This paper studies a short-term production scheduling problem inspired from real-life manufacturing systems consisting on the scheduling a set of jobs (production orders) on both a single machine and identical parallel machines with the objective of minimizing the makespan or maximum completion time of all jobs. Jobs are subject to release dates and there are sequence-dependent machine setup times. Since this problem is known to be strongly NP-hard even for the single machine case, this paper proposes a heuristic algorithm to solve it. The algorithm uses a strategy of random generation of various execution sequences, and then selects the best of such schedules. Experiments are performed using random-generated data and show that the heuristic performs very well compared against the optimal solution and lower bounds, and requiring short computational time.

Este artículo estudia un problema de programación de la producción en el corto plazo inspirado de sistemas de fabricación reales en los cuales se tiene un conjunto de tareas (órdenes de producción) tanto en una configuración de una máquina como en máquinas paralelas idénticas con el objetivo de minimizar el lapso de fabricación o tiempo máximo de terminación de todos los trabajos. Las tareas están sujetas a fechas de disponibilidad diferentes y existen tiempos de preparación de las máquinas dependientes de la secuencia de procesamiento. Puesto que este problema es conocido como fuertemente NP-completo, incluso para el caso de una máquina simple, este artículo propone un algoritmo heurístico para resolverlo. El algoritmo emplea una estrategia de generación aleatoria de varias secuencias de procesamiento de los trabajos y luego selecciona el mejor de estos programas. Se desarrollaron experimentos computacionales empleando datos generados aleatoriamente. Los resultados muestran que el procedimiento propuesto se desempeña muy bien comparado con la solución óptima o con cotas inferiores, requiriendo un menor tiempo de cálculo.