Heurística GRASP para la minimización del makespan en máquinas paralelas no relacionadas con tiempos de preparación dependientes de la secuencia

GRASP approach for the unrelated parallel machines scheduling problem with makespan minimization and sequence dependent setup times

Se propone un algoritmo GRASP (Greedy Randomized Adaptative Search Procedures) para resolver el problema de la programación de trabajos en un sistema de máquinas paralelas no relacionadas con tiempos de preparación dependientes de la secuencia y minimización del makespan. Se evalúan cuatro procedimientos en la fase de búsqueda local de GRASP utilizando una representación secuencial y matricial de las soluciones. La efectividad y eficiencia de las alternativas propuestas se comparan con otras heurísticas de la literature sobre un conjunto de problemas de prueba, superando uno de los procedimientos propuestos el rendimiento promedio.

INTRODUCCIÓN

En este estudio se considera el problema de la programación de n trabajos en un sistema de m máquinas paralelas no relacionadas con tiempos de setup dependientes de la secuencia y minimización del makespan. En un problema de programación de trabajos, el makespan corresponde al intervalo de tiempo en el que se procesan todos los trabajos a programar. Disponer de recursos productivos en paralelo otorga flexibilidad para el procesamiento de trabajos y permite mejorar la capacidad de respuesta de un sistema productivo. Por otro lado, las actividades de preparación de máquinas (tiempos de setup) que usualmente son requeridas cuando se pasa del proceso de un trabajo al siguiente, pueden llegar a ser un problema crítico en la programación de trabajos afectando la productividad del sistema, en particular, cuando estos son tiempos que dependen de la secuencia de proceso. Problemas de este tipo son comunes en la industria de la producción de pintura y de plástico (donde se requiere una completa limpieza entre la producción de una orden de producción y otra), como también en la industria de la producción de textiles, de vidrios, de químicos, de papel, y de servicios [1].

La importancia de considerar los tiempos de setup dependientes de la secuencia en problemas de programación de producción se ha hecho notoria en las últimas décadas [2-3].

El trabajo [4] fue uno de los primeros en abordar el problema de máquinas paralelas no relacionadas con tiempos de setup dependientes de la secuencia y minimización del makespan, proponiendo la heurística PH (heurística de partición). Luego, en [1] se propone para su resolución un algoritmo de búsqueda tabú que usa dos fases en los esquemas de perturbación, uno que actúa dentro de una sola máquina y otro que lo hace entre las máquinas, superando los resultados obtenidos por la heurística PH.

En [5] el problema se resuelve utilizando una metaheurística para la búsqueda aleatoria priorizada llamada Meta-Raps, que es una estrategia que usa tanto una heurística de construcción como una heurística de mejora para generar soluciones de alta calidad, mostrando también mejores resultados que la heurística PH.