Browsing by Author "Casassus, Nicolás"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Un enfoque basado en diagramas de decisión para el Parallel Machine Scheduling Problem con restricciones probabilísticas
    (2025) Casassus, Nicolás; Angulo, Gustavo; Castro Anich, Margarita Paz; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    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).