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

Technische Samenvatting: Het oplossen van gedistribueerde flexibele job shop scheduling problemen in de woltextielindustrie met quantum annealing

Probleemdefinitie
Het artikel behandelt het Distributed Flexible Job Shop Scheduling Problem (DFJSP) binnen de context van de woltextielindustrie. In tegen tegenstelling tot traditionele Job Shop Scheduling Problems (JSSP) of zelfs standaard Flexible Job Shop Scheduling Problems (FJSP), omvat het DFJSP geografisch verspreide productielocaties waar een enkele productieorder (job) vereist dat operaties op verschillende fabrieken worden uitgevoerd. Dit specifieke gebruiksgeval, afgeleid van een echte woltextielfabrikant, introduceert een unieke complexiteit: niet alleen zijn productieorders verdeeld over locaties, maar ook individuele productiestappen (operaties) van een enkele job kunnen verdeeld zijn. Gevolgelijk moet het model rekening houden met verzendtijden tussen machines die zich in verschillende fabrieken bevinden, naast de standaard verwerkingstijden en machinebeperkingen. Het doel is om de maaktijd (totale doorlooptijd) te minimaliseren terwijl precedentregels worden nageleefd, wordt gegarandeerd dat operaties slechts één keer starten, en overlap van machines wordt voorkomen. Dit probleem wordt geïdentificeerd als NP-hard, en de inclusie van transporttijden tussen fabrieken verhoogt de combinatorische complexiteit aanzienlijk.

Methodologie
De auteurs formuleren het uitgebreide DFJSP als een Quadratic Unconstrained Binary Optimization (QUBO) probleem dat opgelost kan worden met een D-Wave Advantage System 4.1 quantum annealer (QPU).

1. QUBO-formulering: Het probleem wordt in kaart gebracht met binaire variabelen $x_{i,o,m,t}$, die representeren of operatie $o$ van job $i$ start op machine $m$ op tijdstip $t$. De kostenfunctie $H(x)$ wordt geconstrueerd als een gewogen som van straffuncties voor beperkingen (precedentie, operatie-één-keer, geen-overlap) en een objectieffunctie voor het minimaliseren van de maaktijd.
2. Variabele Pruning (Snoeien): Om de omvang van het probleem binnen de fysieke limieten van de QPU te beheren, passen de auteurs variabele pruning toe. Dit houdt in dat er onder- en bovengrenzen worden berekend voor de starttijden van operaties op basis van minimale voorgangerstijden en maximale maaktijdlimieten, waardoor binaire variabelen die overeenkomen met ongeldige schema's worden geëlimineerd.
3. Bepaling van Parameters: Een cruciale methodologische stap is de systematische berekening van Lagrange-parameters ($\alpha, \beta, \gamma$) voor de straftermen. In plaats van te vertrouwen op trial-and-error, leiden de auteurs deze gewichten wiskundig af op basis van de maximale mogelijke maaktijd ($t_{max}$) van de specifieke probleeminstantie. Dit zorgt ervoor dat de energie van een geldige oplossing lager is dan de energie van een ongeldige oplossing.
4. Embedding en Configuratie: De logische QUBO-variabelen worden op de fysieke QPU-topologie ingebed met behulp van ketens van qubits. De auteurs onderzoeken de impact van "chain strength" (de koppelingssterkte tussen qubits in een keten) op de kwaliteit van de oplossing, waarbij optimale waarden worden bepaald door de afweging tussen systeemenergie en het percentage gebroken ketens te analyseren.
5. Vergelijking: De resultaten van de quantum annealing (QA) worden vergeleken met Simulated Annealing (SA) met behulp van de D-Wave Ocean SDK. Beide methoden worden getest op probleeminstanties variërend van 50 tot 250 variabelen (de maximale inpasbare grootte op de geteste QPU), waarbij SA ook wordt getest op grotere instanties (tot 4u 400 variabelen) om een baseline voor computationele schaling vast te stellen.

Belangrijkste Bijdragen
Het artikel beschrijft drie primaire bijdragen:

1. Uitgebreid DFJSP-model met QA: De auteurs presenteren de eerste bekende toepassing van Quantum Annealing op een uitgebreid DFJSP waarbij zowel productieorders als individuele productiestappen over fabrieken verdeeld zijn, waarbij de transporttijden tussen locaties expliciet worden gemodelleerd.
2. Systematische Parameterberekening: Het artikel beschrijft een methode voor het bepalen van Lagrange-parameters en QPU-configuratie-instellingen (specifiek chain strength) op basis van de wiskundige formulering van het probleem, waarmee wordt afgeweken van heuristische trial-and-error benaderingen.
3. Economische en Prestatie-evaluatie: De studie evalueert het potentieel voor een snelheidsvoordeel bij het gebruik van QA voor industrie-specifieke gedistribueerde planning, waarbij de kwaliteit van de oplossing en de rekentijd wordt vergeleken met klassieke SA.

Resultaten

• Oplossingskwaliteit: Voor probleeminstanties tot 150 variabelen produceerde QA consistente, geldige oplossingen (geen geschonden beperkingen), hoewel Simulated Annealing (SA) over het algemeen oplossingen met iets lagere energie (betere optimaliteit) teruggaf. Naarmate de probleemomvang toenam naar 200 en 250 variabelen, begonnen de QA-oplossingen defecten te vertonen (respectievelijk 1 en 2 schendingen), wat leidde tot hogere energiewaarden. Deze degradatie wordt toegeschreven aan de toenemende moeilijkheid om grotere logische problemen in de fysieke QPU-grafiek in te passen, wat resulteert in langere ketens en een hoger percentage ketenbreuken.
• Maaktijd: QA-oplossingen voor de meeste probleemomvangten vielen binnen de onderste helft van het mogelijke maaktijd-bereik, wat duidt op levensvatbare productieplanningen. Echter, voor de instantie met 250 variabelen lag de maaktijd in de bovenste helft van het bereik.
• Rekentijd: SA vertoonde snellere rekentijden voor kleine probleeminstanties. Echter, de CPU-tijd van SA groeide exponentieel met de probleemomvang. In contrast hiermee nam de QPU-toegangstijd voor QA toe met een afnemend (logaritmisch) tempo. Hoewel de huidige hardware beperkt is tot het inpassen van problemen tot 250 variabelen voor QA, suggereert de trend dat QA voor grotere instanties (geëxtrapoleerd voorbij 300 variabelen) potentieel een aanzienlijk snelheid voordeel kan bieden ten opzichte van SA.

Betekenis en Claims
Het artikel claimt dat hoewel de huidige quantum annealing hardware te maken heeft met beperkingen bij het inpassen van grootschalige problemen en het bereiken van globale minima vergeleken met klassieke heuristieken voor kleine instanties, het aanzienlijk potentieel heeft voor de specifieke DFJSP-uitdagingen van de woltextielindustrie. De auteurs stellen dat QA een veelbelovend alternatief biedt voor grootschalige gedistribueerde planning vanwege de gunstige schaling van de rekentijd ten opzichte van de probleemomvang. Zij concluderen dat met toekomstige hardwareverbeteringen (meer qubits, betere connectiviteit en stabiliteit), QA een definitief snelheidsvoordeel kan bieden voor probleeminstanties die ongeveer 300 variabelen overschrijden, waardoor het een levensvatbaar hulpmiddel wordt voor complexe, real-world multi-factory productieplanning. Het werk benadrukt dat het succesvolle gebruik van QA sterk afhangt van zorgvuldige probleemformulering, specif