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

Technische Samenvatting: Impliceert Grootte-generalisatie Robuustheid tegen Verstoringen?

Probleemstelling
Deze studie behandelt het Dynamische en Stochastische Flexibele Job-Shop Probleem (FJSP), een combinatorisch optimalisatievraagstuk waarbij operaties over de tijd aan geschikte machines moeten worden toegewezen. In tegen tegenover statische deterministische versies incorporeert dit probleem drie bronnen van onzekerheid: dynamische job-aankomsten (gemodelleerd als een Poisson-proces), stochastische verwerkingstijden (log-normale multiplicatoren) en machinestoringen (exponentiële tijd-tot-falen met log-normale reparatietijden). Hoewel Deep Reinforcement Learning (DRL) gecombineerd met Graph Neural Networks (GNNs) veelbelovend is gebleken voor het generaliseren naar grotere instantiegroottes en het afhandelen van enkelvoudige typen verstoringen, blijft het ongetest of een enkele policy simultaan grootte-generalisatie (goed presteren op instanties die groter zijn dan die tijdens de training gezien zijn) en multi-verstoring-robuustheid (het gelijktijdig afhandelen van machinestoringen, stochastische tijden en dynamische aankomsten) kan bereiken.

Methodologie
De onderzoekers gebruikten een vooraf geregistreerd, statistisch rigoureus protocol om een relationele Graph Isomorphism Network (GIN) encoder te evalueren, gekoppeld aan een Proximal Policy Optimization (PPO) agent.

• Architectuur: De policy maakt gebruik van een relationele GIN die drie soorten randen onderscheidt (intra-job precedentie, machinecompetitie en operatie-machine geschiktheid) via aparte lineaire transformaties vóór aggregatie. Dit ontwerp bevindt zich tussen volledig homogene en volledig heterogene graafrepresentaties in. De actor-head produceert logits voor kandidaat-operaties ongeacht de instantiegrootte, wat zorgt voor een onafhankelijkheid van het aantal parameters van het aantal operaties.
• Training & Beloning: De agent werd getraind met MaskablePPO. Om robuustheid te testen, evalueerde de studie twee beloningsstructuren: een basis potentieel-gebaseerde beloning die de maaktijd (makespan) minimaliseert, en een uitgebreide versie die een "instabiliteitsstraf" ($\kappa \cdot \Delta_{inst}$) incorporeert om afwijkingen van geplande starttijden na verstoringen te bestraffen.
• Experimenteel Ontwerp: De studie pre-registreerde vijf hypothesen (H1–H5) met bevroren beslisregels om HARKing (hypothesizing after results are known) te voorkomen.
  • Baselines: De policy werd vergeleken met negen Priority Dispatching Rules (PDRs), een getunede Genetic Algorithm (GA) en een exacte Constraint Programming solver (CP-SAT).
  • Benchmarks: Evaluatie besloeg 43 instanties uit de Fisher–Thompson en Lawrence families (JSSP) en zeven Brandimarte instanties (FJSP), plus synthetische extensies.
  • Statistisch Protocol: Vergelijkingen maakten gebruik van Wilcoxon signed-rank tests voor paarwijze analyse en Friedman–Nemenyi tests met critical-difference diagrammen voor multi-methode rangschikking. Effectgroottes werden gedurende het hele proces gerapporteerd.

Belangrijkste Resultaten
Vier van de vijf vooraf geregistreerde hypothesen werden verworpen, terwijl één werd geaccepteerd. De bevindingen worden hieronder samengevat:

1. Statische Competitiviteit (H1 - Verworpen): De GNN-PPO policy presteerde niet beter dan de beste dispatching rule op statische instanties. De gemiddelde relatieve procentuele afwijking (RPD) van de policy was 24,82%, vergeleken met 18,96% voor de beste PDR (FIFO). De policy verloor op alle FJSP-instanties en won slechts op 18,6% van de JSSP-instanties.
2. Grootte-generalisatie (H2 - Geaccepteerd): De policy generaliseerde succesvol naar instantiegroottes die 1,5× tot 3,0× groter waren dan de trainingsset. Hoewel de absolute RPD onconcurrerend bleef vergeleken met de beste PDR, was de rang van de policy onder tien methoden niet significant slechter dan de rang van de beste PDR in enig grootte-niveau. Dit wijst op een transfer van relatieve competitiviteit in plaats van absolute oplossingskwaliteit.
3. Multi-verstoring-robuustheid (H3 - Verworpen): De policy slaagde er niet in robuust te zijn onder negen verschillende verstoringsregimes (combinaties van storingen, stochastische tijden en aankomsten). In alle regimes was de Robustness Index (RI) van de policy significant slechter dan die van de beste PDRs. De "dynamische aankomsten" as was bijzonder schadelijk, omdat dit een distributieverschuiving vertegenwoordigde (job-inserties halverwege de episode) die niet tijdens de training was gezien.
4. Verstoringsbewuste Beloning (H4 - Verworpen): Het aanvullen van de beloning met een instabiliteitsstraf ($\kappa > 0$) verbeterde de robuustheid niet. In plaats daarvan veroorzaakte het een instorting van de nominale (onverstoorde) prestaties, waarbij de RPD met 46,6 tot 106,0 procentpunten toenam. De studie diagnosticeert dit falen als een gevolg van het uitsluitend trainen op domein-gerandomiseerde verstorings-episodes zonder ooit de agent bloot te stellen aan onverstoorde (nominale) episodes.
5. Beslissingslatentie (H5 - Verworpen onder strikte drempelwaarde): Hoewel de beslissingslatentie van de policy (4–11 ms) ordes van grootte sneller was dan CP-SAT op grote, complexe instanties, voldeed de policy niet aan de strikte vooraf geregistreerde drempelwaarde (zijn <1% van de tijd van CP-SAT) voor 42 van de 43 instanties. Dit falen werd grotendeels gedreven door kleine instanties waarbij CP-SAT het probleem bijna onmiddellijk oploste, wat een wiskundig artefact creëerde in de ratio.

Significantie en Claims
De centrale bijdrage van het artikel is niet een positief resultaat in termen van oplossingskwaliteit, maar een gediagnosticeerde, statistisch rigoureuze karakterisering van de grenzen van GNN-PPO scheduling policies. De auteurs stellen dat grootte-generalisatie en multi-verstoring-robuustheid scheidbare eigenschappen zijn, en geen "pakketje" dat automatisch voortkomt uit dezelfde architectuur.

• Architecturale Transfer vs. Competitiviteit: De studie levert empirisch bewijs dat grootte-invariante architecturen rang-relatieve competitiviteit kunnen overdragen (een policy kan relatief gezien "even goed als" de beste heuristiek blijven naarmate de grootte toeneemt), zelfs als de basispolicy niet competitief sterk is in absolute termen.
• De Kosten van Gecombineerde Doelstellingen: De verwerping van H3 en H4 suggereert dat een policy niet tegelijkertijd kan optimaliseren voor robuustheid over meerdere typen verstoringen en de nominale prestaties kan behouden zonder specifieke architecturale of trainingsregime aanpassingen. De "instabiliteitsstraf" faalde omdat het trainingsregime (domein-randomisatie zonder blootstelling aan nominale scenario's) incompatibel was met het beloningsontwerp.
• Methodologische Rigor: Door hypothesen en beslisregels vooraf te registreren, biedt de studie een verdedigbaar negatief resultaat, wat ingaat tegen de trend van onverklaarde mislukkingen in de DRL-scheduling literatuur. Het identificeert concrete mechanismen voor falen (bijv. de specifieke impact van het uitsluiten van nominale episodes tijdens de training) in plaats van het falen toe te schrijven aan vage "distributieverschuivingen".

De auteurs concluderen dat praktijkgebruikers niet de conclusie mogen trekken dat verstorings-robuustheid volgt uit claims over grootte-generalisatie alleen. In plaats daarvan moeten deze capaciteiten als onafhankelijke ontwerpaspecten worden behanden die afzonderlijke evaluatie en engineering vereisen. De studie suggereert een potentiële hybride implementatiestrategie waarbij een snelle, reactieve GNN-policy dient als onmiddellijke fallback tijdens verstoringen, terwijl langzamere, kwalitatief betere solvers (GA of CP-SAT) parallel draaien om geoptimaliseerde schema's te generen.