Does Size Generalization Imply Disruption Robustness? A Pre-Registered Study of GNN–PPO Scheduling Policies for the Dynamic Flexible Job-Shop Problem

Technische Zusammenfassung: Bedeutet Größen-Generalisierung eine Robustheit gegenüber Störungen?

Problemstellung
Diese Studie befasst sich mit dem dynamischen und stochastischen flexiblen Job-Shop-Problem (FJSP), einer kombinatorischen Optimierungsaufgabe, bei der Operationen über die Zeit hinweg Maschinen zugewiesen werden müssen. Im Gegensatz zu statischen, deterministischen Versionen beinhaltet dieses Problem drei Quellen der Unsicherheit: dynamische Job-Ankünfte (modelliert als Poisson-Prozess), stochastische Bearbeitungszeiten (Log-Normal-Multiplikatoren) und Maschinenausfälle (exponentielle Zeit bis zum Ausfall mit Log-Normal-Reparaturzeiten). Während Deep Reinforcement Learning (DRL) in Kombination mit Graph Neural Networks (GNNs) vielversprechende Ergebnisse bei der Generalisierung auf größere Instanzgrößen und beim Umgang mit einzelnen Arten von Störungen gezeigt hat, bleibt ungeklärt, ob eine einzige Policy gleichzeitig Größen-Generalisierung (gut abschneiden bei Instanzen, die größer sind als die im Training gesehenen) und Multi-Störungs-Robustheit (Umgang mit gleichzeitigen Maschinenausfällen, stochastischen Zeiten und dynamischen Ankünften) erreichen kann.

Methodik
Die Forscher verwendeten ein vorregistriertes, statistisch rigoroses Protokoll, um einen relationalen Graph Isomorphism Network (GIN) Encoder zu evaluieren, der mit einem Proximal Policy Optimization (PPO) Agenten gekoppelt ist.

• Architektur: Die Policy nutzt einen relationalen GIN, der drei Kantenarten (Intra-Job-Präzedenz, Maschinenkonkurrenz und Operations-Maschinen-Eignung) durch separate lineare Transformationen vor der Aggregation unterscheidet. Dieses Design liegt zwischen einer vollständig homogenen und einer vollständig heterogenen Graphrepräsentation. Der Actor-Head erzeugt Logits für Kandidaten-Operationen unabhängig von der Instanzgröße, was eine Unabhängigkeit der Parameteranzahl von der Anzahl der Operationen gewährleistet.
• Training & Belohnung: Der Agent wurde mittels MaskablePPO trainiert. Um die Robustheit zu testen, evaluierte die Studie zwei Belohnungsstrukturen: eine Basis-Potential-Belohnung zur Minimierung der Makespan und eine erweiterte Version, die eine „Instabilitätsstrafe“ ($\kappa \cdot \Delta_{inst}$) enthält, um Abweichungen von geplanten Startzeiten nach Störungen zu bestrafen.
• Experimentelles Design: Die Studie evaluierte fünf vorregistrierte Hypothesen (H1–H5) mit eingefrorenen Entscheidungsregeln, um HARKing (Hypothesizing After the Results are Known) zu vermeiden.
  • Baselines: Die Policy wurde gegen neun Priority Dispatching Rules (PDRs), einen optimierten Genetischen Algorithmus (GA) und einen exakten Constraint-Programming-Solver (CP-SAT) verglichen.
  • Benchmarks: Die Evaluierung umfasste 43 Instanzen aus den Fisher–Thompson- und Lawrence-Familien (JSSP) sowie sieben Brandimarte-Instanzen (FJSP) plus synthetische Erweiterungen.
  • Statistisches Protokoll: Vergleiche wurden mittels Wilcoxon-Vorzeichen-Rang-Tests für Paaranalysen und Friedman–Nemenyi-Tests mit Critical-Difference-Diagrammen für das Multi-Methoden-Ranking durchgeführt. Effektstärken wurden durchgehend berichtet.

Wichtigste Ergebnisse
Vier der fünf vorregistrierten Hypothesen wurden abgelehnt, eine wurde akzeptiert. Die Ergebnisse lassen sich wie folgt zusammenfassen:

1. Statische Wettbewerbsfähigkeit (H1 – Abgelehnt): Die GNN-PPO-Policy konnte auf statischen Instanzen nicht die beste Dispatching-Rule übertreffen. Die mittlere relative prozentuale Abweichung (RPD) der Policy betrug 24,82 %, verglichen mit 18,96 % für die beste PDR (FIFO). Sie verlor bei allen FJSP-Instanzen und gewann nur bei 18,6 % der JSSP-Instanzen.
2. Größen-Generalisierung (H2 – Akzeptiert): Die Policy generalisierte erfolgreich auf Instanzgrößen, die 1,5× bis 3,0× größer waren als der Trainingssatz. Obwohl ihre absolute RPD im Vergleich zur besten PDR unwettbewerbsfähig blieb, war ihr Rang unter zehn Methoden nicht signifikant schlechter als der Rang der besten PDR in irgendeiner Größenklasse. Dies deutet auf einen Transfer relativer Wettbewerbsfähigkeit statt absoluter Lösungsqualität hin.
3. Multi-Störungs-Robustheit (H3 – Abgelehnt): Die Policy erwies sich unter neun verschiedenen Störungsregimen (Kombinationen aus Ausfällen, stochastischen Zeiten und Ankünften) als nicht robust. In allen Regimen war der Robustheitsindex (RI) der Policy signifikant schlechter als der der besten PDRs. Die Achse der „dynamischen Ankünfte“ war besonders schädlich, da sie eine Verteilungsverschiebung (Job-Einfügungen während der Episode) darstellte, die während des Trainings nicht gesehen wurde.
4. Störungsbewusste Belohnung (H4 – Abgelehnt): Die Ergänzung der Belohnung um eine Instabilitätsstrafe ($\kappa > 0$) verbesserte die Robustheit nicht. Stattdessen führte dies zu einem Kollaps der nominalen (ungestörten) Performance, wobei die RPD um 46,6 bis 106,0 Prozentpunkte anstieg. Die Studie diagnostiziert dieses Scheitern als Folge eines Trainings, das ausschließlich auf domänen-randomisierten Störungs-Episoden basierte, ohne jemals den Agenten ungestörten (nominalen) Episoden auszusetzen.
5. Entscheidungslatenz (H5 – Abgelehnt unter strengem Schwellenwert): Während die Entscheidungslatenz der Policy (4–11 ms) um Größenordnungen schneller war als CP-SAT bei großen, schwierigen Instanzen, verfehlte sie den strengen vorregistrierten Schwellenwert (weniger als 1 % der Zeit von CP-SAT) bei 42 von 43 Instanzen. Dieses Scheitern wurde primlich durch kleine Instanzen getrieben, bei denen CP-SAT das Problem nahezu instantan löste, was ein mathematisches Artefakt im Verhältnis erzeugte.

Bedeutung und Ansprüche
Der zentrale Beitrag des Papers ist kein positives Ergebnis hinsichtlich der Lösungsqualität, sondern eine diagnostizierte, statistisch rigorose Charakterisierung der Grenzen von GNN-PPO-Scheduling-Policies. Die Autoren argumentieren, dass Größen-Generalisierung und Multi-Störungs-Robustheit trennbare Eigenschaften sind und nicht automatisch aus derselben Architektur als „Paketlösung“ hervorgehen.

• Architektonischer Transfer vs. Wettbewerbsfähigkeit: Die Studie liefert empirische Belege dafür, dass größeninvariante Architekturen rangbezogene Wettbewerbsfähigkeit übertragen können (eine Policy kann im Vergleich zu anderen „so gut wie“ die beste Heuristik bleiben, wenn die Größe zunimmt), selbst wenn die Basis-Policy in absoluten Begriffen nicht wettbewerbsfähig stark ist.
• Die Kosten gemeinsamer Ziele: Die Ablehnung von H3 und H4 legt nahe, dass eine Policy nicht gleichzeitig für Robustheit gegenüber mehreren Störungsarten optimieren und die nominale Performance beibehalten kann, ohne spezifische architektonische oder Trainingsregime-Anpassungen vorzunehmen. Die „Instabilitätsstrafe“ scheiterte, weil das Trainingsregime (Domänen-Randomisierung ohne nominale Exposition) inkompatibel mit dem Belohnungsdesign war.
• Methodische Rigorosität: Durch die Vorregistrierung von Hypothesen und Entscheidungsregeln bietet die Studie ein verteidigbares negatives Ergebnis, das dem Trend unerklärlicher Ausfälle in der DRL-Scheduling-Literatur entgegenwirkt. Sie identifiziert konkrete Mechanismen des Scheiterns (z. B. die spezifische Auswirkung des Ausschlusses nominaler Episoden aus dem Training), anstatt schlechte Performance lediglich auf vage „Verteilungsverschiebungen“ zurückzuführen.

Die Autoren kommen zu dem Schluss, dass Praktiker nicht allein aus Ansprüchen der Größen-Generalisierung auf eine Störungs-Robustheit schließen sollten. Stattdessen sollten diese Fähigkeiten als unabhängige Design-Achsen behandelt werden, die eine separate Evaluierung und Entwicklung erfordern. Die Studie schlägt eine potenzielle hybride Deployment-Strategie vor, bei der eine schnelle, reaktive GNN-Policy als unmittelbarer Fallback während Störungen dient, während langsamere, qualitativ hochwertigere Solver (GA oder CP-SAT) parallel laufen, um optimierte Zeitpläne zu erstellen.