Resumen Técnico: DynaSchedBench

Enunciado del Problema

El campo de la Optimización Combinatoria Neuronal (NCO) para el Problema de Programación de Tareas en Taller Flexible Dinámico (DFJSP) enfrenta una tensión metodológica que obstaculiza el progreso. Los benchmarks estáticos existentes (por ejemplo, Taillard, DMU) fomentan el sobreajuste, donde los agentes memorizan estructuras de instancias específicas en lugar de aprender políticas generalizables. Por el contrario, los intentos de generar instancias dinámicas a menudo dependen de un muestreo procedimental no calibrado, donde la dificultad surge como un subproducto no controlado de semillas aleatorias. Esto introduce una "niebla estocástica" de alta varianza, haciendo imposible distinguir la innovación algorítmica genuina de secuencias favorables de eventos dinámicos. Además, la emergencia de Modelos de Lenguaje Grande (LLM) como agentes de programación carece de un marco de evaluación riguroso para probar sus capacidades de razonamiento frente a solucionadores establecidos en un entorno controlado y estadísticamente sólido.

Metodología: Marco DynaSchedBench

Los autores presentan DynaSchedBench, un marco diagnóstico diseñado para generar instancias de benchmark calibradas y fundamentadas teóricamente para DFJSP. El marco consta de cuatro componentes principales:

1. Calibrador de Espacio de Eventos Secuencial (SESC)

En lugar de optimizar hiperparámetros generativos en un espacio de parámetros (lo cual es computacionalmente costoso y propenso a la inestabilidad), DynaSchedBench emplea SESC. Este módulo opera directamente sobre el flujo de eventos discretos realizado $E$. Aplica una secuencia de transformaciones estructurales locales (operadores) para ajustar el flujo de eventos y que coincida con las métricas objetivo.

• Estrategias de Ajuste: El marco utiliza un catálogo de estrategias que incluye Ajuste de estructura de llegada (corrección de tasa, remuestreo de renovación), Escala de holgura adaptativa (modificación de la rigidez de las fechas límite), Remuestreo isomorfo de tiempos de procesamiento (corrección de la variabilidad preservando la carga de trabajo total) e Ingeniería de cuellos de botella (control fino sobre la pérdida de capacidad).
• Bucle de Calibración: Una búsqueda voraz selecciona operadores que minimizan el vector de error normalizado entre las métricas observadas y las métricas objetivo, preservando al mismo tiempo las métricas que ya se encuentran dentro de la tolerancia.

2. Índice de Estrés de Programación (SSI)

Para cuantificar la dificultad de la instancia, los autores proponen el Índice de Estrés de Programación (SSI). Esta métrica mapea las métricas empíricas crudas en un vector de dificultad de cuatro componentes:

• Congestión ($C$): Basada en aproximaciones de tráfico pesado estilo Kingman, utilizando la utilización natural del cuello de botella y la variabilidad.
• Presión Temporal ($P$): El inverso de la holgura empírica.
• Complejidad Estructural ($K$): Una medida normalizada del número de máquinas y la profundidad de las operaciones.
• Intensidad de Disrupción ($S$): Una medida normalizada de las relaciones de disturbio realizadas (por ejemplo, averías).
  Estos componentes se comprimen logarítmicamente y se promedian para producir una puntuación de dificultad escalar $d \in [0, 100]$.

3. Pila de Simulación y Evaluación Modular

El marco proporciona un entorno compatible con Gym con:

• Simulación basada en instantáneas: Garantiza observaciones inmutables para los agentes, soportando tanto políticas sin memoria como planificadores con visión anticipada.
• Motor basado en trayectorias: Persiste los rastros de ejecución para la verificación reproducible de restricciones (precedencia, no superposición de recursos) y el cálculo de métricas de rendimiento.
• Niveles de Observabilidad: Define tres niveles de acceso a la información para los agentes:
  • L1: Vista local (trabajos listos, disponibilidad de máquinas).
  • L2: L1 + estadísticas locales (longitudes de cola, factores de holgura).
  • L3: L2 + priores estructurales (puntuaciones de cuello de botella, objetivos de diseño).

4. Evaluación de Agentes LLM

El marco evalúa agentes basados en LLM utilizando varios modos de prompting (Directo, Cadena de Pensamiento, Aumentado con herramientas) y estrategias de refinamiento (Reflexión, Mejor de N). Mide el rendimiento a través del makespan normalizado ($C_{max}$) en relación con la mejor programación observada y rastrea el consumo de tokens para evaluar las compensaciones entre costo y rendimiento.

Resultados Clave

Rendimiento de Calibración

• Eficiencia y Estabilidad: SESC supera significativamente a las líneas base evolutivas (Optimización Multiobjetivo y Enfoques Híbridos) en eficiencia computacional y estabilidad. SESC logra un tiempo de ejecución de calibración mediano de 0.2 segundos, en comparación con 57.9 segundos para MOO y 185.8 segundos para Híbrido.
• Precisión: SESC demuestra una estabilidad algorítmica superior con una pérdida normalizada media más baja ($\tilde{\ell}_2 \approx 0.0539$) y una dispersión mínima de semilla a semilla en comparación con las líneas base.
• Correlación de Dificultad: La puntuación SSI está positivamente correlacionada con la brecha de programación entre un programador aleatorio y la mejor heurística fija ($\rho = 0.563$), validando su utilidad como proxy para la dificultad de programación.

Hallazgos sobre Programación con LLM

• La Paradoja de la Observabilidad: Proporcionar a los agentes priores estructurales completos (L3) degrada el rendimiento en comparación con resúmenes estadísticos concisos (L2). Los agentes L2 CoT lograron un makespan excedente normalizado medio de 0.7%, mientras que los agentes L3 CoT se degradaron a 1.66%. Esto sugiere que los LLM actuales luchan por destilar señales útiles del ruido estructural de alta dimensión.
• Ineficiencia de la Sondeo Activo: Las estrategias aumentadas con herramientas (L1+Herramienta) incurrieron en un aumento de tres veces en el consumo de tokens sin mejorar el rendimiento sobre el L1 CoT estándar, destacando un "cuello de botella de integración de información".
• Paridad Heurística: A pesar de un sobrecosto sustancial de tokens y estrategias de razonamiento avanzadas (Reflexión, Mejor de N), los LLM no logran superar consistentemente a las fuertes Reglas de Despacho por Prioridad (PDR) diseñadas a mano. Los LLM superiores (por ejemplo, Qwen3-8B) se desempeñaron estadísticamente de manera indistinguible de las mejores heurísticas fijas (por ejemplo, LIFO+LIT), caracterizándolos como aproximadores heurísticos robustos en lugar de optimizadores superiores.

Significado y Afirmaciones

El artículo afirma resolver la crisis de evaluación en la programación dinámica al proporcionar un marco principiado para generar benchmarks controlados distribucionalmente. Su significado principal radica en:

1. Rigor Metodológico: Reemplazar el muestreo no calibrado con un proceso de calibración determinista en el espacio de eventos que permite la estratificación sistemática de la dificultad de la instancia.
2. Insight Diagnóstico: Descubrir la "Paradoja de la Observabilidad", que desafía la suposición de que más información (priores estructurales) conduce a una mejor toma de decisiones en agentes basados en LLM para problemas combinatorios.
3. Expectativas Realistas: Establecer que los LLM actuales, incluso con prompting avanzado y uso de herramientas, actúan principalmente como aproximadores robustos de heurísticas clásicas en lugar de optimizadores transformadores, sugiriendo la necesidad de pivotar la investigación hacia la planificación de trayectorias de múltiples pasos en lugar del despacho reactivo.

Los autores concluyen que, sin tales entornos calibrados, el campo no puede evaluar de manera confiable las capacidades de razonamiento de los agentes emergentes, y que la generación actual de LLM está limitada por el techo de rendimiento de las heurísticas clásicas en contextos de programación dinámica.