The Price of Optimality Under Uncertainty: A Predictive–Reactive Robustness Analysis of Exact, Metaheuristic, and Dispatching-Rule Scheduling for the Dynamic Job-Shop Problem

Resumen Técnico: El Precio de la Optimalidad bajo la Incertidumbre

Definición del Problema
Este estudio aborda el Problema de Programación de Talleres de Trabajo Dinámicos (JSSP, por sus siglas en inglés) bajo condiciones de incertidumbre. Aunque el JSSP es un problema canónico NP-duro que típicamente se resuelve para minimizar la rampa de finalización ($C_{max}$) en entornos deterministas, los talleres del mundo real están sujetos a tres disrupciones primarias: averías de maquinaria, tiempos de procesamiento estocásticos y la llegada dinámica de nuevos trabajos. La pregunta central de investigación investiga si un programa que es óptimo bajo datos nominales (deterministas) sigue siendo preferible cuando se ejecuta bajo estas disrupciones. Específicamente, el artículo compara la "el precio de la optimalidad": el compromiso entre lograr un programa teóricamente perfecto y mantener la robustez cuando la realidad diverge del plan.

Metodología
El autor emplea una comparación controlada a nivel de paradigma utilizando un entorno de evaluación predictivo-reactivo de eventos discretos. El estudio evalúa tres familias de soluciones distintas a través de dieciséis instancias de referencia de Fisher–Thompson y Lawrence (que van desde $6\times6$ hasta $20\times10$) bajo nueve regímenes de disrupción (tres niveles de severidad cada uno para averías, tiempos estocásticos y llegadas dinámicas).

1. Paradigmas de Solución:

   • Solucionador Exacto (CP-SAT): Un solucionador de programación de restricciones que produce un programa predictivo certificado como óptimo (o casi óptimo). Esto representa el "techo de calidad" para los datos nominales.
   • Metaheurística (Algoritmo Genético - GA): Un algoritmo genético basado en permutaciones con un presupuesto computacional fijo, que produce programas predictivos de alta calidad pero no certificados.
   • Reglas de Prioridad de Despacho (PDRs): Nueve reglas en línea (SPT, LPT, MWKR, LWKR, MOR, LOR, FIFO, EDD, CR) que toman decisiones reactivamente en cada evento sin un programa precalculado.

2. Políticas de Ejecución y Reparación:

   • Los métodos fuera de línea (CP-SAT y GA) utilizan una política de reparación de desplazamiento a la derecha (right-shift). La secuencia de operaciones comprometida es fija; las disrupciones retrasan las operaciones pero no reordenan la secuencia.
   • Las PDRs operan en línea (online), recalculando las prioridades en cada evento.
   • Las llegadas dinámicas se gestionan absorbiendo los nuevos trabajos en los intervalos de máquinas inactivas, una restricción que los programas precalculados no pueden anticipar.

3. Diseño Experimental:

   • Modelos de Disrupción: Las averías de máquinas siguen un proceso de renovación calibrado para objetivos de disponibilidad ($A_k \in \{0.95, 0.80\}$); los tiempos de procesamiento utilizan un multiplicador log-normal de media unitaria ($s \in \{0.10, 0.50\}$); las llegadas dinámicas siguen un proceso de Poisson calibrado para objetivos de utilización ($\rho \in \{0.70, 0.95\}$).
   • Métricas:
     • Índice de Robustez (RI): Degradación relativa de la rampa de finalización bajo disrupción comparada con la propia rampa de finalización nominal del método.
     • Desviación Porcentual Relativa Realizada (RPD): La desviación de la rampa de finalización perturbada contra el óptimo certificado, permitiendo la comparación de calidad de solución entre métodos.
   • Protocolo Estadístico: El análisis incluye 30 réplicas de escenarios por celda (47,520 ejecuciones en total). Las comparaciones por pares utilizan la prueba exacta de Wilcoxon signed-rank; los rankings conjuntos utilizan la prueba de Friedman con análisis post-hoc de Nemenyi.

Resultados Clave
El estudio reporta una inversión decisiva entre la calidad nominal y la robustez:

1. Desempeño Nominal: Como era de esperar, el solucionador exacto (CP-SAT) domina, logrando un RPD medio de 3.08% por encima del óptimo, seguido por el GA (6.28%). Las mejores reglas de despacho (MWKR, MOR) quedan significativamente rezagadas (12.07% y 14.15%).
2. Ranking de Robustez: El ranking se invierte bajo disrupción. El solucionador exacto y el GA son los métodos menos robustos (rangos de Friedman 10.14 y 9.82, respectivamente), mientras que todas las reglas de despacho son significativamente más robustas (rangos 3.95–5.77). La compacidad óptima del solucionador exacto deja poco margen para absorber retrasos, lo que provoca que cada disrupción se propague totalmente.
3. Cruce de Calidad Realizada:
   • Averías de Máquinas: Las reglas MWKR y MOR superan al solucionador exacto en calidad realizada (42.97% y 43.20% RPD frente a 46.07% para CP-SAT).
   • Tiemos de Procesamiento Estocásticos: El solucionador exacto mantiene una estrecha ventaja, pero la ventaja nominal se reduce de ~9% a <3%.
   • Llegadas Dinámicas: Las reglas en línea dominan por completo. El solucionador exacto y el GA se convierten en los dos peores métodos (175.30% y 177.02% RPD) porque un programa comprometido no puede planificar para trabajos que llegan después de que el programa fue generado.

Contribuciones Clave

1. Comparación de Robustez a Nivel de Paradigma: El estudio proporciona la primera comparación directa entre un solucionador exacto, una metaheurística y un conjunto completo de reglas de despacho sobre un entorno predictivo-reactivo común y estadísticamente controlado.
2. Evidencia de la Inversión de la Optimalidad–Robustez: Cuantifica que el programa óptimo exacto es simultáneamente el mejor método nominal y el menos robusto, donde el ranking de robustez esencialmente revierte el ranking de calidad nominal.
3. Identificación de Umbrales de Disrupción: El artículo identifica que, más allá de los niveles de disrupción leves, la ventaja nominal del solucionador exacto se erosiona y se invierte, siendo las reglas de despacho simples (específicamente MWKR y MOR) las que entregan programas realizados superiores.
4. Clarificación Metodológica: El estudio destaca la distinción entre degradación relativa (RI) y calidad realizada (RPD). Demuestra que confiar únicamente en el RI puede ser engañoso, ya que las reglas con programas nominales pobres (como EDD) parecen "robustas" simplemente porque tienen menos espacio para degradarse, mientras que reglas como MWKR combinan un desempeño nominal competitivo con una degradación gradual.

Significancia y Reivindicaciones
El artículo concluye que la optimalidad exacta y la robustez ante disrupciones son objetivos conflictivos en el taller de trabajo dinámico. El "precio de la optimalidad" es alto: un programa óptimamente compacto es estructuralmente frágil porque carece del margen necesario para absorber la incertidumbre.

El autor argumenta que, para entornos propensos a disrupciones, una regla de despacho simple y libre de computación (específicamente MWKR o MOR) no es meramente un plan de contingencia, sino frecuentemente la política desplegada superior. Estas reglas acten como mecanismos de equilibrio de carga que naturalmente redirigen el esfuerzo alrededor de las disrupciones sin replanificar la maquinaria. El estudio sugiere una política contingente a la disrupción: la resolución exacta es valiosa solo en regímenes casi deterministas; a medida que la disrupción se intensifica, el caso para los solucionadores exactos se debilita rápidamente y las reglas en línea se convierten en la opción óptima para el desempeño realizado. Los hallazgos desafían la intuición derivada de los benchmarks deterministas, sugiriendo que en entornos dinámicos, la adaptabilidad en línea "suficientemente buena" a menudo supera la planificación "perfecta" fuera de línea.