💻 computer science

A Benchmarking Suite for Flexible Job Shop Scheduling Problems with Worker Flexibility under Uncertainty

Este artículo presenta una suite integral de evaluación que comprende 402 instancias estandarizadas del Problema de Programación de Tareas en Talleres Flexibles, extendidas con flexibilidad de trabajadores e incertidumbre, diseñadas para permitir una comparación rigurosa, reproducible y transversal de diversos solucionadores de optimización mediante métricas unificadas, herramientas de visualización y resultados de referencia.

Autores originales: David Hutter, Thomas Steinberger, Michael Hellwig

Publicado 2026-05-06

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: David Hutter, Thomas Steinberger, Michael Hellwig

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina un piso de fábrica ocupado. Tienes un montón de trabajos por hacer, una flota de máquinas para realizar el trabajo y un equipo de trabajadores para operar esas máquinas. El objetivo es simple: terminar todo lo más rápido posible. Pero en el mundo real, las cosas se complican. Una máquina podría ser más rápida en una tarea que en otra, un trabajador podría ser más rápido en una tarea diferente, y a veces, una máquina se avería o un trabajador se da de baja por enfermedad.

Este artículo presenta un nuevo "Gimnasio" para programas informáticos (llamados solucionadores) que intentan resolver este rompecabezas de programación. Al igual que los atletas necesitan una pista estandarizada para comparar sus velocidades, estos programas de programación necesitan un conjunto justo y consistente de problemas para demostrar cuál es el mejor.

Aquí hay un desglose de lo que construyeron los autores, utilizando analogías simples:

1. El Problema: Una Cocina Caótica

Piensa en el Problema de Programación Flexible de Taller de Trabajo (FJSSP) como la cocina de un restaurante de alta gama.

Los Trabajos: Diferentes pedidos que llegan (por ejemplo, un filete, una ensalada, una sopa).
Las Máquinas: Los hornos, las parrillas y las licuadoras.
El Giro: A diferencia de una cocina simple donde la parrilla solo cocina filetes, aquí, la parrilla también podría cocinar la ensalada si el chef es lo suficientemente rápido. Esto es "flexibilidad de la máquina".

Ahora, añade Flexibilidad de los Trabajadores (FJSSP-W).

Los Trabajadores: Los chefs.
El Nuevo Giro: No solo puede la parrilla cocinar la ensalada, sino que qué chef sostiene la espátula importa. El Chef A podría tardar 5 minutos en asar un filete, mientras que el Chef B tarda 7 minutos. La computadora tiene que averiguar no solo qué máquina usar, sino qué trabajador específico debería operarla para realizar el trabajo lo más rápido posible.

2. La Vieja Forma: Jugando con Reglas Diferentes

Anteriormente, los investigadores que intentaban construir mejores computadoras de programación eran como personas que intentaban comparar corredores en diferentes pistas.

Un investigador probó su programa en una pista pequeña y fácil.
Otro probó el suyo en un campo enorme y fangoso.
Algunos usaron "clima perfecto" (sin averías), mientras que otros usaron "lluvia y viento" (incertidumbre).

Como las pistas de prueba eran tan diferentes, no podías decir si un corredor era realmente más rápido o simplemente tenía un recorrido más fácil. Esto hacía difícil saber qué programa informático era realmente el mejor.

3. La Nueva Solución: Un "Estadio Olímpico" Estandarizado

Los autores crearon un Conjunto de Referencia. Piensa en esto como un enorme estadio olímpico estandarizado con 402 pistas diferentes.

La Colección: Tomaron 402 escenarios de fábrica existentes y los actualizaron todos para incluir la regla de "Flexibilidad de los Trabajadores". Esto crea una enorme biblioteca lista para usar de problemas.
La Estación Meteorológica de "Incertidumbre": Las fábricas reales no son perfectas. Las máquinas se averían y los trabajadores se cansan. Este nuevo conjunto permite a los investigadores inyectar "caos" en la prueba. Pueden simular:
- Ruido en el Tiempo de Procesamiento: Un trabajador podría ser ligeramente más rápido o más lento de lo habitual (como un corredor teniendo un buen o mal día).
- Averías de Máquinas: Una máquina deja de funcionar de repente (como un corredor tropezando).
- Indisponibilidad de Trabajadores: Un trabajador no puede presentarse (como un corredor que se lesiona).

4. Cómo Funciona: El "Marcador"

El conjunto no es solo una lista de problemas; es un kit de herramientas completo:

El Filtro: Puedes elegir tipos específicos de pistas (por ejemplo, "Muéstrame solo las fábricas con 10 máquinas y alta flexibilidad de trabajadores"). Esto ayuda a los investigadores a probar partes específicas de sus programas.
La Línea Base: El conjunto viene con una puntuación de "Estándar de Oro". Te dice el mejor tiempo posible logrado hasta ahora por programas de primer nivel. Si tu nuevo programa no puede superar esta puntuación, no está listo para los Juegos Olímpicos.
Los Visuales: Convierte los resultados en gráficos y diagramas fáciles de leer, para que puedas ver de un vistazo qué programa es el "Campeón Olímpico".

5. La Primera Carrera: ¿Quién Ganó?

Los autores probaron varios programas informáticos diferentes en este nuevo estadio para ver cómo funcionaba:

El Solucionador "Codicioso": Es como un corredor que simplemente elige la siguiente pista disponible sin pensar hacia adelante. Fue el más lento.
El Solucionador "MILP" (Programación Lineal Entera Mixta): Es un corredor muy estricto y matemático que intenta calcular cada posibilidad individual. Fue preciso pero se quedó atascado en las pistas grandes y complejas (agotando la memoria).
El Solucionador "CP" (Programación por Restricciones): Este corredor fue el ganador claro. Manejó la complejidad de asignar trabajadores y máquinas mucho mejor que los demás.
El Solucionador "GA" (Algoritmo Genético): Este corredor fue un fuerte segundo lugar, utilizando un método inspirado en la evolución (prueba y error) para encontrar buenas soluciones.

Por Qué Esto Importa

Antes de este artículo, los investigadores gritaban al vacío, cada uno afirmando que su programa era el mejor basándose en sus propias pruebas pequeñas y únicas. Este artículo construye un lenguaje común y un campo de juego justo.

Permite a los científicos decir: "Mi programa es mejor que el tuyo porque ambos corrimos en las mismas 402 pistas exactas, bajo las mismas condiciones climáticas exactas". Esto ayuda a que todo el campo avance más rápido, lo que lleva a un software mejor que eventualmente puede ayudar a que las fábricas reales funcionen con más eficiencia, incluso cuando las cosas salen mal.

En resumen: Construyeron un "gimnasio" estandarizado, justo y caótico donde las computadoras de programación pueden finalmente competir en igualdad de condiciones para ver quién es realmente el mejor organizando una fábrica ocupada.

Resumen Técnico: Una Suite de Referencia para Problemas de Programación de Tareas en Taller Flexible con Flexibilidad de Trabajadores bajo Incertidumbre

Definición del Problema
El artículo aborda el Problema de Programación de Tareas en Taller Flexible (FJSSP) y su extensión, el Problema de Programación de Tareas en Taller Flexible con Flexibilidad de Trabajadores (FJSSP-W). Mientras que el FJSSP clásico implica asignar operaciones a máquinas elegibles para minimizar una función de costo (típicamente el tiempo de finalización), el FJSSP-W integra además la asignación de la fuerza laboral. En este problema extendido, una operación debe asignarse no solo a una máquina específica, sino también a un trabajador elegible, donde la combinación específica máquina-trabajador determina el tiempo de procesamiento.

Una brecha significativa identificada en la literatura es la falta de un entorno de referencia estandarizado y sistemático para estos problemas, particularmente al incorporar incertidumbre (por ejemplo, tiempos de procesamiento estocásticos, fallos de máquinas y indisponibilidad de trabajadores). La investigación existente a menudo depende de conjuntos de instancias fragmentados y ad hoc o de casos reales específicos que dificultan la comparación entre dominios de solucionadores de diferentes paradigmas de optimización (Programación Matemática, Programación por Restricciones y Optimización Basada en Simulación).

Metodología y Construcción de la Referencia
Los autores proponen una suite de referencia integral y de código abierto implementada en Python. La metodología involucra tres componentes principales:

Recopilación y Extensión de Instancias:
- La suite se basa en una colección curada de 402 instancias distintas de FJSSP extraídas de diez fuentes establecidas (por ejemplo, Brandimarte, Hurink, Kacem).
- Estas instancias se extienden sistemáticamente para crear instancias de FJSSP-W. El proceso de extensión asigna un conjunto de trabajadores ( $W$ ) a cada combinación máquina-operación.
- Lógica de Asignación de Trabajadores: Para cada par operación-máquina, se muestrea un número aleatorio de trabajadores elegibles. Los tiempos de procesamiento para estas nuevas combinaciones se generan muestreando desde una distribución centrada alrededor del tiempo de procesamiento original de la máquina (rango predeterminado: 90% a 110% del tiempo base).
- Caracterización: La suite documenta características específicas de la instancia, incluyendo el número de trabajos ( $n$ ), máquinas ( $m$ ), trabajadores ( $w$ ), operaciones ( $N$ ), flexibilidad ( $\beta$ ) y variedad de duración ( $d_v$ ), permitiendo un filtrado basado en características.
Modelado de Incertidumbre mediante Simulación de Eventos Discretos (DES):
- El entorno soporta la simulación de tres tipos de incertidumbre: variabilidad en los tiempos de procesamiento, fallos de máquinas e indisponibilidad de trabajadores.
- Tiempos de Procesamiento: Modelados utilizando distribuciones Beta para simular velocidades de trabajo inconsistentes.
- Fallos de Máquinas: Modelados utilizando distribuciones Exponenciales para la ocurrencia (promediando una falla por programa) y distribuciones Weibull para la duración (mínimo 10% del tiempo de finalización libre de ruido).
- Indisponibilidad de Trabajadores: También modelada con distribuciones Exponenciales (frecuencia más baja) y Weibull (duración más larga, mínimo 50% del tiempo de finalización libre de ruido).
- Las soluciones se representan como Grafos Acíclicos Dirigidos (DAG) para facilitar la traversión y simulación de estos eventos estocásticos.
Marco de Evaluación:
- La suite proporciona APIs para cargar instancias, traducir codificaciones (por ejemplo, entre FJSSP y FJSSP-W) y evaluar el rendimiento.
- Métricas: El objetivo principal es minimizar el tiempo de finalización. Para las simulaciones de incertidumbre, el tiempo de finalización robusto ( $C_r$ ) se calcula como el tiempo de finalización real promedio sobre múltiples ejecuciones de simulación.
- Análisis Estadístico: El marco incluye herramientas para el ranking estadístico (pruebas de Friedman y Nemenyi) y visualización (por ejemplo, diagramas de Nemenyi) para comparar rigurosamente el rendimiento de los solucionadores.

Contribuciones Clave

Colección de Referencia Estandarizada: La creación de un portafolio fijo de 402 instancias de FJSSP-W, asegurando la reproducibilidad y la comparabilidad entre estudios.
Suite de Código Abierto: Un entorno basado en Python que soporta múltiples paradigmas de optimización (MILP, CP, Algoritmos Evolutivos) proporcionando representaciones de modelo y funciones de evaluación necesarias.
Integración de Incertidumbre: Un método sistemático para inyectar estocasticidad en las instancias del problema, permitiendo el desarrollo y la evaluación de estrategias de optimización robusta.
Resultados de Referencia: Provisión de resultados "mejor conocidos" derivados de solucionadores de última generación (Gurobi, IBM CPLEX/OR-Tools y Algoritmos Genéticos) bajo un límite de tiempo estandarizado (20 minutos) y configuración de hardware.

Resultados Experimentales
Los autores demostraron la suite comparando cuatro solucionadores en las 402 instancias de FJSSP-W:

Programación por Restricciones (CP): Superó significativamente a otros enfoques, logrando una desviación relativa ( $\delta_{rel}$ ) de menos de 0.25 en más del 80% de las instancias.
Algoritmo Genético (GA): Rindió bien, superando significativamente a los enfoques MILP y Greedy, aunque quedó por detrás de CP.
Programación Lineal Entera Mixta (MILP): Luchó con la escala del problema; muchas instancias no pudieron resolverse dentro del límite de tiempo debido a restricciones de memoria y conteo de variables.
Algoritmo Greedy: Sirvió como línea base, obteniendo el peor rendimiento.

En las simulaciones de robustez (utilizando la instancia Fattahi20), el marco visualizó con éxito la degradación de los programas bajo incertidumbre, calculando el tiempo de finalización robusto y el cociente de robustez ( $R$ ) para evaluar la estabilidad del programa.

Significado y Afirmaciones
El artículo afirma que este trabajo sienta las bases para el desarrollo dirigido de algoritmos y la evaluación consistente del rendimiento en la investigación de programación de producción. Al abordar la fragmentación en las prácticas actuales de referencia, la suite permite:

Comparación Justa: Evaluación rigurosa y reproducible entre diferentes solucionadores y subdominios de problemas.
Desarrollo de Algoritmos: Soporte para el desarrollo de operadores para grupos específicos de problemas mediante el filtrado de instancias.
Evaluación de Robustez: La capacidad de evaluar cómo los solucionadores manejan las incertidumbres del mundo real, yendo más allá de la optimización determinista.

Los autores enfatizan que, aunque la suite está diseñada principalmente para Optimización Basada en Simulación (SBO) y Algoritmos Evolutivos, su provisión de representaciones de modelo para MILP y CP permite la comparación entre paradigmas. Abogan por el uso del conjunto de instancias fijo para asegurar la reproducibilidad científica y solicitan transparencia en la presentación de parámetros experimentales y especificaciones de hardware para facilitar la investigación futura.