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

Technische Zusammenfassung: Lösung des verteilten flexiblen Werkstattplanungsproblems in der Wolltextilindustrie mittels Quantum Annealing

Problemdefinition
Die vorliegende Arbeit befasst sich mit dem verteilten flexiblen Werkstattplanungsproblem (Distributed Flexible Job Shop Scheduling Problem, DFJSP) im Kontext der Wolltextilindustrie. Im Gegensatz zu herkömmlichen Werkstattplanungsproblemen (JSSP) oder sogar Standard-flexiblen Werkstattplanungsproblemen (FJSP) beinhaltet das DFJSP geografisch verteilte Produktionsstandorte, an denen ein einzelner Produktionsauftrag (Job) erfordert, dass Operationen in verschiedenen Fabriken durchgeführt werden. Dieser spezifische Anwendungsfall, der aus einem realen Wolltextilhersteller stammt, führt eine einzigartige Komplexität ein: Nicht nur sind die Produktionsaufträge über verschiedene Standorte verteilt, sondern auch die einzelnen Produktionsschritte (Operationen) eines einzelnen Jobs können verteilt sein. Folglich muss das Modell auch Versandzeiten zwischen Maschinen berücksichtigen, die sich in verschiedenen Fabriken befinden, zusätzlich zu den Standard-Bearbeitungszeiten und Maschinenbeschränkungen. Das Ziel ist die Minimierung der Durchlaufzeit (Makespan), während Präzedenzbedingungen eingehalten, der Beginn von Operationen sichergestellt und Maschinenüberlappungen verhindert werden. Dieses Problem wird als NP-schwer identifiziert, wobei die Einbeziehung von standortübergreifenden Versandzeiten die kombinatorische Komplexität erheblich steigert.

Methodik
Die Autoren formulieren das erweiterte DFJSP als quadratisches unbeschränktes binäres Optimierungsproblem (Quadratic Unconstrained Binary Optimization, QUBO), das mit einem D-Wave Advantage System 4.1 Quanten-Annealer (QPU) gelöst werden soll.

1. QUBO-Formulierung: Das Problem wird auf binäre Variablen $x_{i,o,m,t}$ abgebildet, die repräsentieren, ob die Operation $o$ des Jobs $i$ auf Maschine $m$ zum Zeitpunkt $t$ beginnt. Die Kostenfunktion $H(x)$ wird als gewichtete Summe von Straffunktionen für Beschränkungen (Präzedenz, einmalige Ausführung der Operation, keine Überlappung) und einer Zielfunktion zur Minimierung der Durchlaufzeit konstruiert.
2. Variablen-Pruning (Variablenreduktion): Um die Problemgröße innerhalb der physikalischen Grenzen der QPU zu handhaben, wenden die Autoren das Variablen-Pruning an. Dies beinhaltet die Berechnung von unteren und oberen Schranken für die Startzeiten von Operationen basierend auf minimalen Vorgängerzeiten und maximalen Durchlaufzeitgrenzen, wodurch binäre Variablen, die ungültigen Zeitplänen entsprechen würden, eliminiert werden.
3. Bestimmung der Parameter: Ein entscheidender methodischer Schritt ist die systematische Berechnung der Lagrange-Parameter ($\alpha, \beta, \gamma$) für die Strafterme. Anstatt sich auf Trial-and-Error zu verlassen, leiten die Autoren diese Gewichte mathematisch basierend auf der maximal möglichen Durchlaufzeit ($t_{max}$) der spezifischen Probleminstanz ab. Dies stellt sicher, dass die Energie jeder gültigen Lösung niedriger ist als die Energie einer ungültigen Lösung.
4. Embedding und Konfiguration: Die logischen QUBO-Variablen werden unter Verwendung von Ketten von Qubits auf die physische QPU-Topologie eingebettet. Die Autoren untersuchen den Einfluss der „Chain Strength“ (Kopplungsstärke zwischen Qubits in einer Kette) auf die Lösungsqualität und bestimmen optimale Werte durch die Analyse des Kompromisses zwischen Systemenergie und dem Prozentsatz gebrochener Ketten.
5. Vergleich: Die Ergebnisse des Quantum Annealing (QA) werden gegen Simulated Annealing (SA) unter Verwendung des D-Wave Ocean SDK getestet. Beide Methoden werden auf Probleminstanzen mit einer Größe von 50 bis 250 Variablen getestet (die maximale einbettbare Größe auf der getesteten QPU), wobei SA auch auf größeren Instanzen (bis zu 400 Variablen) getestet wird, um eine Baseline für die rechnerische Skalierung zu etablieren.

Hauptbeiträge
Die Arbeit skizziert drei primäre Beiträge:

1. Erweitertes DFJSP-Modell mit QA: Die Autoren präsentieren die erste bekannte Anwendung von Quantum Annealing auf ein erweitertes DFJSP, bei dem sowohl Produktionsaufträge als auch einzelne Produktionsschritte über Fabriken verteilt sind und standortübergreifende Versandzeiten explizit modelliert werden.
2. Systematische Parameterberechnung: Die Arbeit beschreibt eine Methode zur Bestimmung von Lagrange-Parametern und QPU-Konfigurationseinstellungen (speziell der Chain Strength) basierend auf der mathematischen Formulierung des Problems und bewegt sich damit weg von heuristischen Trial-and-Error-Ansätzen.
3. Ökonomische und Leistungsbewertung: Die Studie bewertet das Potenzial für einen Geschwindigkeitsvorteil bei der Nutzung von QA für die industrie-spezifische verteilte Planung durch den Vergleich der Lösungsqualität und der Berechnungszeit mit klassischem SA.

Ergebnisse

• Lösungsqualität: Für Probleminstanzen bis zu 150 Variablen lieferte QA konsistente, gültige Lösungen (keine gebrochenen Beschränkungen), obwohl Simulated Annealing (SA) im Allgemeinen Lösungen mit etwas niedrigerer Energie (besserer Optimalität) lieferte. Als die Problemgröße auf 200 und 250 Variablen anstieg, begannen die QA-Lösungen gebrochene Beschränkungen aufzuweisen (1 bzw. 2 Verletzungen), was zu höheren Energiewerten führte. Diese Verschlechterung wird der zunehmenden Schwierigkeit zugeschrieben, größere logische Probleme auf den physischen QPU-Graphen einzubetten, was zu längeren Ketten und einer höheren Rate an Kettenbrüchen führt.
• Durchlaufzeit (Makespan): Die QA-Lösungen für die meisten Problemgrößen lagen in der unteren Hälfte des möglichen Durchlaufzeitbereichs, was auf lebensfähige Produktionspläne hindeutet. Für die 250-Variablen-Instanz lag die Durchlaufzeit jedoch in der oberen Hälfte des Bereichs.
• Rechenzeit: SA zeigte schnellere Berechnungszeiten für kleine Probleminstanzen. Jedoch wuchs die CPU-Zeit von SA exponentiell mit der Problemgröße. Im Gegensatz dazu stieg die QPU-Zugriffszeit für QA mit einer abnehmenden (logarithmischen) Rate. Während die aktuelle Hardware QA auf die Einbettung von Problemen bis zu 250 Variablen begrenzt, deutet der Trend darauf hin, dass QA für größere Instanzen (extrapoliert über 300 Variablen hinaus) potenziell einen signifikanten Geschwindigkeitsvorteil gegenüber SA bieten könnte.

Bedeutung und Behauptungen
Die Arbeit behauptet, dass die aktuelle Hardware für Quantum Annealing zwar vor Herausforderungen bei der Einbettung großskaliger Probleme und dem Erreichen globaler Minima im Vergleich zu klassischen Heuristiken für kleine Instanzen steht, sie aber ein erhebliches Potenzial für die spezifischen DFJSP-Herausforderungen der Wolltextilindustrie besitzt. Die Autoren führen an, dass QA eine vielversprechende Alternative für die großskalige verteilte Planung darstellt, da es eine günstige Skalierung der Rechenzeit im Verhältnis zur Problemgröße bietet. Sie kommen zu dem Schluss, dass QA mit zukünftigen Hardware-Verbesserungen (mehr Qubits, bessere Konnektivität und Stabilität) einen definitiven Geschwindigkeitsvorteil für Probleminstanzen mit etwa über 300 Variablen bieten könnte, was es zu einem lebensfähigen Werkzeug für die komplexe, reale Multi-Fabrik-Produktionsplanung macht. Die Arbeit betont, dass der erfolgreiche Einsatz von QA stark von einer sorgfältigen Problemformulierung abhängt, insbesondere von der mathematischen Ableitung der Strafgewichte und der Optimierung der Embedding-Parameter.