Algorítmo de búsqueda de entorno variable para minimizar la tardanza total ponderada en una máquina de procesamiento por lotes

Resumen

En este artículo se presentan los resultados de una investigación desarrollada para resolver el problema de programación de producción, en un sistema en el cual el objetivo principal es cumplir con las fechas de entrega. Cada trabajo está descrito por su tiempo de proceso, su fecha de liberación, su fecha de entrega, su importancia relativa con respecto a los otros trabajos y su peso. La máquina de procesamiento por lotes (MPL) puede procesar múltiples trabajos simultáneamente, siempre y cuando el peso total de éstos no exceda la capacidad máxima de la máquina. El tiempo de proceso del lote es el tiempo máximo de proceso de los trabajos que lo componen. De la misma forma, el tiempo de liberación de un lote es el tiempo máximo de liberación de los trabajos que lo componen. Teniendo en cuenta que el problema es NP–Completo, en este artículo se propone un heurístico de búsqueda de entorno variable para minimizar la tardanza total ponderada en una MPL. Los experimentos computacionales realizados para establecer la calidad de las soluciones encontradas demostraron que, en un tiempo de cómputo restringido a un máximo de 30 minutos, el heurístico propuesto encuentra soluciones considerablemente mejores que las encontradas mediante la implementación de un modelo de programación entera mixta, disponible en la literatura e implementado en un software comercial de optimización.

This paper presents the results of a research project conducted to solve a production sche-duling problem observed in a system in which meeting customer due dates is the primary objective. Each job to be scheduled is defined by its processing time, ready time, due date, weight and size. The Batch Processing Machine (BPM) can process several jobs simulta-neously as a batch as long as its capacity is not violated. The processing time of a batch is the largest processing time among the jobs in the batch, and the batch ready time is the largest ready time among the jobs in the batch. Given that the problem is NP-hard we propose a Variable Neighborhood Search (VNS) heuristic to minimize the total weighted tardiness on a single BPM. The computational experiments conducted to assess the quality of the solutions found show that in a computational time restricted to a maximum of 30 minutes, the proposed heuristic finds solutions considerably better than the solutions obtained after implementing a mixed integer programming model available in the literature in a commercial solver.