Modelos de programación lineal entera mixta para la secuenciación de máquinas paralelas no relacionadas con tiempos de cambio

Abstract

[ES] Este trabajo estudia el problema de secuenciación en máquinas paralelas no relacionadas con tiempos de cambio dependientes de la máquina y de la secuencia de proceso de los trabajos. Se estudiarán diversas soluciones al problema propuestas a lo largo del tiempo que incluyen modelos de programación lineal entera mixta, modelos heurísticos, matheurísticos y de programación por restricciones. Tras esto, se propondrá un modelo exacto que se comparará con los métodos exactos existentes más relevantes de la literatura. Para esto, se hará uso de un cluster de cómputo en el que se estudiará el desempeño de los diferentes modelos mediante conjuntos de datos extraídos de trabajos anteriores de la literatura. Se ha decidido incluir el modelo de programación por restricciones en la comparación debido a su creciente interés. Para ello, se ha trabajado con el entorno de desarrollo integrado (IDE) de CPLEX y con la librería CP enfocada a la programación por restricciones. Los resultados obtenidos se han comparado con los resultados de las técnicas basadas en modelos de programación entera mixta y reafirman las bondades del enfoque basado en programación por restricciones.

[EN] This work studies the unrelated parallel machines scheduling problem (UPMS) with setup times for every job, which are machine and sequence dependent. It will cover some of the solutions proposed over the time for the problem, which includes models based on mixed integer linear programming, heuristics, matheuristics and constraint programming. After this, a new exact model is proposed. It will be compared with some of the most relevant state of the art exact models. To this end, a computational cluster will be used to test the performance of the different models by means of data instances extracted from previous works from the literature. Due to its growing interest, a constraint programming model has been included in this work. To this end, I have worked with the CPLEX integrated development environment (IDE) and the CP library, which is focused on constraint programming. The results from the constraint programming model have been compared with the ones of mixed integer linear programming and reaffirm the goodnesses of the constraint programming approach.