Un enfoque basado en diagramas de decisión para el Parallel Machine Scheduling Problem con restricciones probabilísticas
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
El Chance-Constrained Parallel Machine Scheduling Problem (CC-PMSP) asigna trabajos con tiempos de realización inciertos a máquinas, asegurando que las restricciones de disponibilidad de cada máquina se cumplan con una cierta probabilidad. Presentamos una descomposición del problema donde el problema maestro asigna trabajos a máquinas, y los subproblemas ordenan los trabajos en cada máquina mientras verifican la factibilidad de la solución bajo la restricción de probabilidad. Proponemos dos formulaciones diferentes de Diagramas de Decisión (DD) para resolver los subproblemas y generar cortes. La primera formulación emplea DD con una función de costo lineal, mientras que la segunda utiliza una función de costo no lineal para reducir el tamaño del diagrama. Mostramos cómo generar cortes de no-good y de irreducible infeasible subsystem (IIS). Adicionalmente, extendemos los cortes propuestos por Lozano & Smith (2018) para resolver modelos de programación estocástica de dos etapas. Nuestra metodología basada en DD supera a los modelos tradicionales de programación entera (IP) diseñados para resolver el CC-PMSP en varias instancias. Específicamente, nuestro mejor enfoque basado en DD resuelve 55 instancias más que la mejor alternativa IP (de un total de 405) y típicamente logra gaps menores (50% vs. 120% de brecha en promedio).
Description
Tesis (Magíster en Ciencias de la Ingeniería)--Pontificia Universidad Católica de Chile, 2025
Keywords
Diagramas de decisión, Optimización estocástica, Restricciones probabilísticas, Secuenciamiento bajo incertidumbre, Parallel Machine Scheduling Problem