RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States

Die Arbeit stellt \textsc{ReSched} vor, ein minimalistisches Deep-Reinforcement-Learning-Framework, das den Flexible Job Shop Scheduling Problem durch eine auf vier essenziellen Merkmalen basierende Zustandsdarstellung und eine angepasste Transformer-Architektur löst und dabei sowohl klassische Heuristiken als auch aktuelle neuronale Methoden übertreift.

Das Wesentliche

Das große Problem: Der chaotische Werkstatt-Alltag

Stellen Sie sich eine riesige, hochmoderne Fabrik vor. Hier gibt es viele verschiedene Aufträge (Jobs), die aus mehreren Schritten bestehen. Jeder Schritt muss von einer bestimmten Maschine erledigt werden. Das Tückische daran: Nicht jede Maschine kann jeden Schritt machen, und manche Schritte können auf mehreren verschiedenen Maschinen erledigt werden.

Das Ziel ist es, einen perfekten Fahrplan zu erstellen:

1. Welche Maschine macht welchen Schritt?
2. In welcher Reihenfolge?

Das Ziel ist es, die Gesamtzeit zu minimieren, bis alle Aufträge fertig sind (man nennt das „Makespan"). Wenn der Plan schlecht ist, stehen Maschinen herum oder warten aufeinander – das kostet Geld und Zeit.

Das alte Problem: Zu komplizierte Landkarten

Bisher haben Computerprogramme (basierend auf künstlicher Intelligenz) versucht, diesen Plan zu erstellen, indem sie sich eine riesige, überladene Landkarte des Problems gemalt haben.

• Sie haben sich Dutzende von Details gemerkt: „Wie lange war Maschine X schon in Betrieb?", „Welche Maschine wurde vor 10 Minuten benutzt?", „Wie viele Schritte fehlen noch?"
• Das war wie ein Navigator, der nicht nur die aktuelle Straße kennt, sondern auch den Wetterbericht von gestern, die Geschichte der Straße und die Stimmung des Fahrers speichert.
• Das Ergebnis: Die Programme waren sehr komplex, schwer zu trainieren und funktionierten oft nur gut in genau der Situation, für die sie gebaut wurden.

Die Lösung: RESCHED – Der minimalistische Navigator

Die Forscher haben sich gefragt: „Brauchen wir wirklich all diese Informationen?" Ihre Antwort: Nein.

Sie haben RESCHED entwickelt. Das ist wie ein neuer, schlanker Navigator, der nur das Wesentliche sieht.

1. Die vier magischen Zutaten (Der vereinfachte Zustand)

Statt sich 20+ Details zu merken, schaut RESCHED nur auf vier Dinge, die wirklich wichtig sind, um die nächste Entscheidung zu treffen:

1. Wann ist die Maschine frei? (Wie lange muss ich warten?)
2. Wann ist der nächste Auftragsschritt fertig? (Wann kann ich weitermachen?)
3. Wie lange dauert der Schritt? (Die reine Arbeitszeit.)
4. Was ist die schnellste mögliche Zeit? (Eine Art „Best-Case-Schätzung".)

Die Analogie: Stellen Sie sich vor, Sie sind ein Koch in einer Küche mit vielen Herden.

• Alte Methode: Der Koch schaut auf eine Tafel, auf der steht: „Herr Müller kam um 8 Uhr rein, die Pfanne war 2015 gekauft, und der Nachbar hat gestern gekocht."
• RESCHED-Methode: Der Koch schaut nur: „Ist der Herd frei? Wie lange braucht das Steak? Ist das Fleisch schon gewürzt?"
• Durch diesen Fokus auf das „Hier und Jetzt" muss der Computer nicht mehr die ganze Vergangenheit im Kopf behalten. Das macht ihn schneller und flexibler.

2. Der neue Gehirn-Typ: Der Transformer (Die Super-Leser)

Früher nutzten diese Programme spezielle Netzwerke, die wie ein strenges Lineal waren (Graph Neural Networks). Sie konnten nur bestimmte Muster erkennen.
RESCHED nutzt stattdessen einen Transformer (die gleiche Technologie, die auch Chatbots wie ich nutzen).

• Die Metapher: Ein Transformer ist wie ein Super-Manager, der in einer riesigen Halle steht. Er kann mit jedem einzelnen Mitarbeiter (Maschine) und jedem einzelnen Auftrag gleichzeitig sprechen.
• Er versteht sofort, wer auf wen wartet.
• Er hat zwei spezielle Ohren:
  • Ein Ohr hört zu, wie die Aufträge untereinander abhängen (Reihenfolge).
  • Das andere Ohr hört zu, welche Maschine gerade frei ist und wie sie sich verhält.
• Besonders clever: Der Manager passt sich an. Wenn es 100 Aufträge und nur 5 Maschinen gibt (was oft der Fall ist), verteilt er seine Aufmerksamkeit so, dass die wenigen Maschinen nicht von der Flut an Aufträgen „ertränkt" werden.

Warum ist das so toll?

1. Es funktioniert überall: Da das System nicht auf unnötige Details spezialisiert ist, kann es nicht nur in der Fabrik (FJSP), sondern auch in anderen Szenarien helfen, z. B. wenn Aufträge auf einer einzigen Maschine laufen müssen (JSSP) oder wenn sie in einer festen Reihenfolge durch verschiedene Stationen gehen (FFSP). Es ist wie ein Schweizer Taschenmesser statt eines einzelnen Messers.
2. Es lernt schneller: Weil es weniger „Müll" (überflüssige Daten) verarbeiten muss, findet es schneller gute Lösungen.
3. Es ist robust: Selbst wenn die Fabrik plötzlich doppelt so groß ist wie beim Training, findet RESCHED immer noch einen sehr guten Plan. Die alten Systeme scheiterten oft, wenn die Probleme zu groß wurden.

Zusammenfassung in einem Satz

RESCHED ist wie ein kluger, minimalistischer Disponent, der statt sich in endlose Listen von Details zu verlieren, einfach nur auf die vier wichtigsten Signale schaut und mit einem modernen, flexiblen Gehirn (Transformer) sofort den besten Weg für alle Maschinen findet – egal wie groß oder komplex die Fabrik ist.

Das Ergebnis: Schnellere Produktion, weniger Wartezeiten und ein Computer, der wirklich „versteht", was er tut, statt nur auswendig gelernte Regeln abzuspulen.

Technische Zusammenfassung

1. Problemstellung: Flexible Job Shop Scheduling Problem (FJSP)

Das Flexible Job Shop Scheduling Problem (FJSP) ist ein fundamentales kombinatorisches Optimierungsproblem mit Anwendungen in der Fertigung, Edge-Computing und Logistik. Im Gegensatz zum klassischen Job Shop Scheduling Problem (JSSP), bei dem jede Operation fest einer Maschine zugeordnet ist, erlaubt das FJSP, dass jede Operation von einer Menge kompatibler Maschinen bearbeitet werden kann.

Die Lösung erfordert zwei gekoppelte Entscheidungen:

1. Zuweisung: Welche Maschine bearbeitet welche Operation?
2. Sequenzierung: In welcher Reihenfolge werden die Operationen auf jeder Maschine bearbeitet?

Das Ziel ist die Minimierung der Makespan (der maximalen Fertigstellungszeit aller Operationen).

Herausforderungen bestehender Ansätze:
Bisherige Deep Reinforcement Learning (DRL)-Ansätze leiden unter zwei Hauptproblemen:

• Komplexe Zustandsdarstellungen: Sie verlassen sich auf stark ingenieurtechnisch aufbereitete Merkmale (oft >20 handgefertigte Features) und historische Abhängigkeiten, was die Modellierungskomplexität erhöht.
• Starre Architekturen: Die meisten Methoden nutzen Graph Neural Networks (GNNs) oder Graph Attention Networks (GATs). Diese haben inhärente Induktionsverzerrungen, die das Erfassen langreichweitiger Abhängigkeiten erschweren und oft tief gestapelte Schichten erfordern. Zudem führen manuelle Heuristiken zur Einschränkung des Aktionsraums oft zu einer Verschlechterung der Generalisierungsfähigkeit.

2. Methodik: Das RESCHED-Framework

RESCHED ist ein minimalistisches DRL-Framework, das die Formulierung des Problems und das Modell-Design neu denkt.

A. Minimalistische Zustandsdarstellung (State Representation)

Der Kern von RESCHED ist die Reduktion des Zustandsraums auf das Wesentliche, basierend auf einer subproblem-basierten Perspektive (jeder Schritt löst ein Teilproblem).

• Markov-Eigenschaft: Die Autoren zeigen, dass für die optimale Entscheidung nur der aktuelle Zustand relevant ist, nicht die gesamte Historie.
• Vier essenzielle Merkmale: Der Zustand wird auf nur vier Features reduziert:
  1. Verfügbarkeitszeit der Operation (Operation Available Time).
  2. Verfügbarkeitszeit der Maschine (Machine Available Time).
  3. Bearbeitungsdauer (Duration) als Kanteneigenschaft.
  4. Minimale Bearbeitungsdauer über alle kompatiblen Maschinen (als Proxy für die Schwierigkeit).
• Struktur statt Features: Abhängigkeiten (Operation-zu-Operation, O2O) und Zuweisungsmöglichkeiten (Operation-zu-Maschine, O2M) werden nicht als Features, sondern explizit als Graph-Struktur kodiert.
• Relative Zeit: Um Generalisierungsprobleme durch wachsende absolute Zeitwerte zu vermeiden, werden alle Verfügbarkeitszeiten relativ zum globalen Minimum normalisiert.
• Rückwärtige Kanten: Anstatt bidirektionaler Kanten werden nur rückwärtige Kanten (von einer Operation zu ihren Nachfolgern) verwendet, um redundante historische Informationen zu eliminieren.

B. Transformer-basierte Architektur

Statt GNNs wird ein Transformer als Backbone verwendet, der speziell an die Anforderungen des Scheduling angepasst wurde. Die Architektur besteht aus zwei komplementären Zweigen:

1. Operations-Zweig (Self-Attention mit RoPE):

   • Modelliert die Abhängigkeiten innerhalb eines Auftrags (O2O).
   • Nutzt Rotary Positional Embeddings (RoPE), um die relative Reihenfolge von Operationen innerhalb eines Jobs zu erfassen, ohne zusätzliche lernbare Parameter. Dies ist effizienter als indexbasierte Positionskodierung.

2. Maschinen-Zweig (Cross-Attention mit Edge-in-Attention):

   • Aggregiert Informationen von Operationen zu Maschinen.
   • Edge-in-Attention: Die Bearbeitungsdauer (Kantenfeature) wird direkt in die Value-Vektoren eingebettet, anstatt nur die Attention-Gewichte zu beeinflussen. Dies stellt sicher, dass Kanteneigenschaften die aggregierte Repräsentation direkt beeinflussen.
   • Self-based Cross-Attention: Da die Anzahl der Operationen oft um eine Größenordnung höher ist als die der Maschinen (z. B. 10:1), führt dies zu einer Informationsüberflutung der Maschinenknoten. Der neue Mechanismus erlaubt es jedem Maschinenknoten, auch auf seine eigene Repräsentation zu achten (Self-Attention innerhalb des Cross-Attention-Blocks), um kritische Maschineninformationen vor dem „Verwässern" durch zu viele Operationen zu schützen.

C. Entscheidungsfindung und Training

• Aktion: Auswahl eines gültigen Paares (Operation, Maschine).
• Belohnung (Reward): Basierend auf der negativen Differenz der geschätzten unteren Schranke der Makespan vor und nach der Aktion.
• Algorithmus: Das Framework nutzt den einfachen REINFORCE-Algorithmus (ohne Critic-Netzwerk), um den Einfluss der Architektur und des Zustands von algorithmischen Verbesserungen zu isolieren. (Eine PPO-Variante wurde ebenfalls getestet und bestätigt die Robustheit).

3. Schlüsselbeiträge

1. Neue MDP-Formulierung: Entwicklung einer kompakten Zustandsdarstellung mit nur vier essenziellen Features, die redundante Merkmale, historische Abhängigkeiten und Hilfsvariablen eliminiert.
2. Dual-Branch Transformer: Einführung einer maßgeschneiderten Transformer-Architektur mit RoPE für intra-Job-Abhängigkeiten und einem neuartigen Cross-Attention-Modul, das Kantenfeatures direkt integriert und das Ungleichgewicht zwischen Operationen und Maschinen durch Self-Connections ausgleicht.
3. State-of-the-Art (SOTA) Leistung: Demonstration, dass RESCHED sowohl handgefertigte Heuristiken als auch führende DRL-Baselines auf FJSP-Benchmarks übertrifft.
4. Starke Generalisierung: Das Modell generalisiert robust auf verschiedene Problemgrößen und Varianten (JSSP und Flexible Flow Shop Scheduling Problem - FFSP), ohne dass eine architekturspezifische Anpassung nötig ist.

4. Ergebnisse

• FJSP-Leistung: Auf synthetischen Datensätzen (SD1, SD2) und etablierten Benchmarks (Brandimarte, Hurink) übertrifft RESCHED klassische Dispatching-Regeln (PDRs) und aktuelle DRL-Methoden (HGNN, DANIEL, DOAGNN). Auf schwierigen SD2-Instanzen reduziert es die Lücke zu DANIEL um bis zu 30 %.
• Generalisierung:
  • JSSP: Trainiert nur auf synthetischen 10x10 Instanzen, erzielt RESCHED auf dem Taillard-Benchmark (bis zu 100x20) bessere Ergebnisse als spezialisierte JSSP-Modelle (L2D, RL-GNN).
  • FFSP: Trainiert nur auf Größe 20, erreicht RESCHED die besten Ergebnisse auf Instanzen bis Größe 100, übertrifft damit das spezialisierte MatNet.
• Effizienz: Die Inferenzzeit ist vergleichbar mit anderen DRL-Ansätzen und deutlich schneller als exakte Solver (wie OR-Tools) oder genetische Algorithmen, bei gleichzeitig höherer Lösungsqualität.
• Robustheit: Die Ergebnisse sind über verschiedene Zufallssamen hinweg stabil (Variation < 1 %).

5. Bedeutung und Fazit

RESCHED beweist, dass für komplexe kombinatorische Optimierungsprobleme wie das FJSP keine extrem komplexen, stark ingenieurtechnisch aufbereiteten Zustandsdarstellungen oder spezialisierte Graph-Netzwerke erforderlich sind. Stattdessen ermöglicht eine minimalistische, aber ausreichende Zustandsdarstellung in Kombination mit einer ausdrucksstarken, generischen Transformer-Architektur eine überlegene Leistung und Generalisierungsfähigkeit.

Der Ansatz verschiebt den Fokus von der manuellen Feature-Engineering hin zu einer rein datengetriebenen, strukturellen Modellierung. Dies macht RESCHED zu einem vielversprechenden generischen Framework, das leicht auf andere Scheduling- und Ressourcenallokationsprobleme (z. B. Task Offloading in Edge Computing) übertragen werden kann, ohne die Architektur ändern zu müssen. Die Arbeit legt nahe, dass die Kombination aus einfacher MDP-Formulierung und modernen Transformer-Mechanismen der vielversprechendste Weg für skalierbare, lernbasierte Scheduling-Systeme ist.