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

Sintesi Tecnica: Risoluzione dei Problemi di Pianificazione della Produzione Distribuita e Flessibile nel Settore Tessile della Lana tramite Quantum Annealing

Definizione del Problema
Il documento affronta il Problema di Pianificazione della Produzione Distribuita e Flessibile (Distributed Flexible Job Shop Scheduling Problem - DFJSP) nel contesto dell'industria tessile della lana. A differenza dei tradizionali problemi di pianificazione della produzione (JSSP) o anche dei problemi di pianificazione flessibile standard (FJSP), il DFJSP coinvolge siti di produzione geograficamente dispersi dove un singolo ordine di produzione (job) può richiedere che le operazioni siano eseguite in fabbriche diverse. Questo caso d'uso specifico, derivato da un produttore reale di tessuti di lana, introduce una complessità unica: non solo gli ordini di produzione sono distribuiti tra i siti, ma anche i singoli passaggi produttivi (operazioni) di un singolo lavoro possono essere distribuiti. Di conseguenza, il modello deve tenere conto dei tempi di spedizione tra le macchine situate in fabbriche diverse, oltre ai tempi di lavorazione standard e ai vincoli delle macchine. L'obiettivo è minimizzare il makespan (tempo totale di completamento) garantendo al contempo i vincoli di precedenza, assicurando che le operazioni inizino una sola volta e prevenendo sovrapposizioni tra le macchine. Questo problema è identificato come NP-hard, e l'inclusione dei tempi di spedizione inter-fabbrica aumenta significativamente la complessità combinatoria.

Metodologia
Gli autori formulano l'esteso DFJSP come un problema di Ottimizzazione Binaria Quadratica Non Vincolata (Quadratic Unconstrained Binary Optimization - QUBO) per essere risolto utilizzando un quantum annealer D-Wave Advantage System 4.1 (QPU).

1. Formulazione QUBO: Il problema viene mappato su variabili binarie $x_{i,o,m,t}$, che rappresentano se l'operazione $o$ del lavoro $i$ inizia sulla macchina $m$ al tempo $t$. La funzione di costo $H(x)$ è costruita come una somma pesata di funzioni di penalità per i vincoli (precedenza, operazione-una-volta, assenza di sovrapposzioni) e una funzione obiettivo per la minimizzazione del makespan.
2. Potatura delle Variabili (Variable Pruning): Per gestire la dimensione del problema entro i limiti fisici della QPU, gli autori impiegano la potatura delle variabili. Ciò comporta il calcolo dei limiti inferiori e superiori per i tempi di inizio delle operazioni basati sui tempi minimi dei predecessori e sui limiti massimi del makespan, eliminando così le variabili binarie che corrispondono a programmi non validi.
3. Determinazione dei Parametri: Un passaggio metodologico critico riguarda il calcolo sistematico dei parametri di Lagrange ($\alpha, \beta, \gamma$) per i termini di penalità. Invece di affidarsi a tentativi ed errori, gli autori derivano questi pesi matematicamente in base al makespan massimo ($t_{max}$) dell'istanza specifica del problema. Ciò garantisce che l'energia di qualsiasi soluzione valida sia inferiore all'energia di qualsiasi soluzione non valida.
4. Embedding e Configurazione: Le variabili logiche QUBO vengono incorporate nella topologia fisica della QPU utilizzando catene di qubit. Gli autori investigano l'impatto della "forza della catena" (la forza di accoppiamento tra i qubit in una catena) sulla qualità della soluzione, determinando i valori ottimali analizzando il compromesso tra l'energia del sistema e la percentuale di catene interrotte.
5. Confronto: I risultati del quantum annealing (QA) sono messi a confronto con il Simulated Annealing (SA) utilizzando il D-Wave Ocean SDK. Entrambi i metodi sono testati su istanze di problemi che vanno da 50 a 250 variabili (la dimensione massima incorporabile sulla QPU testata), con il SA testato anche su istanze più grandi (fino a 400 variabili) per stabilire una linea di base per la scalabilità computazionale.

Contributi Chiave
Il documento delinea tre contributi primari:

1. Modello DFJSP Esteso con QA: Gli autori presentano la prima applicazione nota del Quantum Annealing a un esteso DFJSP in cui sia gli ordini di produzione che i singoli passaggi produttivi sono distribuiti tra le fabbriche, modellando esplicitamente i tempi di spedizione inter-sito.
2. Calcolo Sistematico dei Parametri: Il documento dettaglia un metodo per determinare i parametri di Lagrange e le impostazioni di configurazione della QPU (specificamente la forza della catena) basandosi sulla formulazione matematica del problema, allontanandosi dagli approcci euristici basati su tentativi ed errori.
3. Valutazione Economica e delle Prestazioni: Lo studio valuta il potenziale di un vantaggio di velocità nell'uso del QA per la pianificazione distribuita specifica del settore, confrontando la qualità della soluzione e il tempo di calcolo rispetto al SA classico.

Risultati

• Qualità della Soluzione: Per istanze di problemi fino a 150 variabili, il QA ha prodotto soluzioni valide e coerenti (nessuna violazione dei vincoli), sebbene il Simulated Annealing (SA) abbia generalmente restituito soluzioni con un'energia leggermente inferiore (migliore ottimalità). All'aumentare della dimensione del problema a 200 e 250 variabili, le soluzioni QA hanno iniziato a presentare vincoli violati (1 e 2 violazioni, rispettivamente), portando a valori di energia più elevati. Tale degradazione è attribuita alla crescente difficoltà di incorporare problemi logici più grandi sul grafo fisico della QPU, che risulta in catene più lunghe e in un tasso più elevato di interruzione delle catene.
• Makespan: Le soluzioni QA per la maggior parte delle dimensioni dei problemi rientravano nella metà inferiore dell'intervallo di makespan possibile, indicando programmi di produzione validi. Tuttavia, per l'istanza a 250 variabili, il makespan si trovava nella metà superiore dell'intervallo.
• Tempo Computazionale: Il SA ha dimostrato tempi di calcolo più rapidi per le piccole istanze di problemi. Tuttavia, il tempo di CPU del SA è cresciuto esponenzialmente con la dimensione del problema. Al contrario, il tempo di accesso alla QPU per il QA è aumentato con un tasso decrescente (logaritmico). Sebbene gli attuali limiti dell'hardware limitino il QA all'incorporazione di problemi fino a 250 variabili, la tendenza suggerisce che, per istanze più grandi (estrapolate oltre le 300 variabili), il QA potrebbe potenzialmente offrire un significativo vantaggio di velocità rispetto al SA.

Significatività e Rivendicazioni
Il documento afferma che, sebbene l'attuale hardware di quantum annealing affronti limitazioni nell'incorporare problemi su larga scala e nel raggiungere minimi globali rispetto alle euristiche classiche per piccoli casi, esso detiene un potenziale significativo per le sfide specifiche del DFJSP dell'industria tessile della lana. Gli autori sostengono che il QA offra un'alternativa promettente per la pianificazione distribuita su larga scala grazie al suo favorevole scaling del tempo di calcolo rispetto alla dimensione del problema. Concludono che, con i futuri miglioramenti dell'hardware (più qubit, migliore connettività e stabilità), il QA potrebbe fornire un vantaggio definitivo in termini di velocità per problemi che superano le circa 300 variabili, rendendolo uno strumento valido per la complessa pianificazione della produzione multi-fabbrica del mondo reale. Il lavoro sottolinea che il successo dell'applicazione del QA dipende fortemente da una rigorosa formulazione del problema, specificamente dalla derivazione matematica dei pesi di penalità e dall'ottimizzazione dei parametri di embedding.