Solving Distributed Flexible Job Shop Scheduling Problems in the Wool Textile Industry with Quantum Annealing

Resumen Técnico: Resolución de Problemas de Programación de Talleres Flexibles Distribuidos en la Industria Textil de Lana mediante Recocido Cuántico

Definición del Problema
El artículo aborda el Problema de Programación de Talleres Flexibles Distribuidos (DFJSP, por sus siglas en inglés) en el contexto de la industria textil de lana. A diferencia de los Problemas de Programación de Talleres (JSSP) tradicionales o incluso de los Problemas de Programación de Talleres Flexibles (FJSP) estándar, el DFJSP involucra sitios de producción geográficamente dispersos donde un único pedido de producción (trabajo) puede requerir que las operaciones se realicen en diferentes fábricas. Este caso de uso específico, derivado de un fabricante de textiles de lana del mundo real, introduce una complejidad única: no solo los pedidos de producción están distribuidos entre los sitios, sino que los pasos de producción individuales (operaciones) de un solo trabajo también pueden estar distribuidos. En consecuencia, el modelo debe contabilizar los tiempos de envío entre máquinas ubicadas en diferentes fábricas, además de los tiempos de procesamiento estándar y las restricciones de las máquinas. El objetivo es minimizar la fecha de finalización (makespan o tiempo total de finalización) cumpliendo al mismo tiempo con las restricciones de precedencia, asegurando que las operaciones comiencen una sola vez y evitando la superposición de máquinas. Se identifica este problema como NP-duro, y la inclusión de los tiempos de envío entre fábricas aumenta significativamente la complejidad combinatoria.

Metodología
Los autores formulan el DFJSP extendido como un problema de Optimización Binaria Cuadrática Sin Restricciones (QUBO) para ser resuelto mediante un recocido cuántico en un sistema D-Wave Advantage 4.1 (QPU).

1. Formulación QUBO: El problema se mapea a variables binarias $x_{i,o,m,t}$, que representan si la operación $o$ del trabajo $i$ comienza en la máquina $m$ en el tiempo $t$. La función de costo $H(x)$ se construye como una suma ponderada de funciones de penalización para las restricciones (precedencia, ejecución única de la operación, no superposición) y una función objetivo para minimizar el makespan.
2. Poda de Variables: Para gestionar el tamaño del problema dentro de los límites físicos de la QPU, los autores emplean la poda de variables. Esto implica calcular límites inferiores y superiores para los tiempos de inicio de las operaciones basándose en los tiempos mínimos de los predecesores y los límites máximos de makespan, eliminando así las variables binarias que corresponden a cronogramas inválidos.
3. Determinación de Parámetros: Un paso metodológico crítico implica el cálculo sistemático de los parámetros de Lagrange ($\alpha, \beta, \gamma$) para los términos de penalización. En lugar de depender del ensayo y error, los autores derivan estos pesos matemáticamente basándose en el makespan máximo ($t_{max}$) de la instancia específica del problema. Esto asegura que la energía de cualquier solución válida sea menor que la energía de cualquier solución inválida.
4. Incrustación y Configuración: Las variables lógicas del QUBO se incrustan en la topología física de la QPU mediante cadenas de qubits. Los autores investigan el impacto de la "fuerza de la cadena" (la fuerza de acoplamiento entre los qubits en una cadena) en la calidad de la solución, determinando valores óptimos mediante el análisis del compromiso entre la energía del sistema y el porcentaje de cadenas rotas.
5. Comparación: Los resultados del recocido cuántico (QA) se comparan con el Recocido Simulado (SA) utilizando el SDK D-Wave Ocean. Ambos métodos se prueban en instancias de problemas que van desde 50 hasta 250 variables (el tamaño máximo incrustable en la QPU probada), con el SA también probado en instancias más grandes (hasta 400 variables) para establecer una línea base de escalabilidad computacional.

Contribuciones Clave
El artículo describe tres contribuciones principales:

1. Modelo DFJSP Extendido con QA: Los autores presentan la primera aplicación conocida del Recocido Cuántico a un DFJSP extendido donde tanto los pedidos de producción como los pasos de producción individuales están distribuidos entre fábricas, modelando explícitamente los tiempos de envío entre sitios.
2. Cálculo Sistemático de Parámetros: El artículo detalla un método para determinar los parámetros de Lagrange y la configuración de la QPU (específicamente la fuerza de la cadena) basados en la formulación matemática del problema, alejándose de los enfoques heurísticos de ensayo y error.
3. Evaluación Económica y de Desempeño: El estudio evalúa el potencial de una ventaja de velocidad al usar QA para la programación distribuida específica de la industria, comparando la calidad de la solución y el tiempo de cálculo frente al SA clásico.

Resultos

• Calidad de la Solución: Para instancias de problemas de hasta 150 variables, el QA produjo soluciones consistentes y válidas (sin restricciones rotas), aunque el Recocido Simulado (SA) generalmente devolvió soluciones con una energía ligeramente menor (mejor optimalidad). A medida que el tamaño del problema aumentó a 200 y 250 variables, las soluciones de QA comenzaron a exhibir restricciones rotas (1 y 2 violaciones, respectivamente), lo que llevó a valores de energía más altos. Esta degradación se atribuye a la creciente dificultad de incrustar problemas lógicos más grandes en el grafo físico de la QPU, lo que resulta en cadenas más largas y una mayor tasa de rotura de cadenas.
• Makespan: Las soluciones de QA para la mayoría de los tamaños de problemas se situaron en la mitad inferior del rango de makespan posible, lo que indica cronogramas de producción viables. Sin embargo, para la instancia de 250 variables, el makespan se situó en la mitad superior del rango.
• Tiempo Computacional: El SA demostró tiempos de cálculo más rápidos para instancias de problemas pequeños. Sin embargo, el tiempo de CPU del SA creció exponencialmente con el tamaño del problema. En contraste, el tiempo de acceso a la QPU para el QA aumentó a un ritmo decreciente (logarítmico). Si bien el hardware actual limita el QA a la incrustación de problemas de hasta 250 variables, la tendencia sugiere que, para instancias más grandes (extrapoladas más allá de las 300 variables), el QA podría ofrecer potencialmente una ventaja de velocidad significativa sobre el SA.

Significancia y Reivindicaciones
El artículo sostiene que, si bien el hardware actual de recocido cuántico enfrenta limitaciones para incrustar problemas a gran escala y alcanzar mínimos globales en comparación con las heurísticas clásicas para instancias pequeñas, posee un potencial significativo para los desafíos específicos de DFJSP de la industria textil de lana. Los autores afirman que el QA ofrece una alternativa prometedora para la programación distribuida a gran escala debido a su favorable escalamiento del tiempo de computación en relación con el tamaño del problema. Concluyen que, con futuras mejoras de hardware (más qubits, mejor conectividad y estabilidad), el QA podría proporcionar una ventaja definitiva de velocidad para problemas de más de aproximadamente 300 variables, convirtiéndolo en una herramienta viable para la planificación de la producción multifábrica compleja y del mundo real. El trabajo enfatiza que la aplicación exitosa del QA depende en gran medida de una cuidadosa formulación del problema, específicamente de la derivación matemática de los pesos de penalización y la optimización de los parámetros de incrustación.