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

Sintesi Tecnica: La generalizzazione delle dimensioni implica la robustezza alle interruzioni?

Definizione del Problema
Questo studio affronta il problema della Job-Shop Flexible dinamico e stocastico (FJSP), una sfida di ottimizzazione combinatoria in cui le operazioni devono essere assegnate a macchine idonee nel tempo. A differenza delle versioni deterministiche statiche, questo problema incorpora tre fonti di incertezza: arrivi dinamici di lavori (modellati come un processo di Poisson), tempi di lavorazione stocastici (moltiplicatori log-normali) e guasti alle macchine (tempo al guasto esponenziale con tempi di riparazione log-normali). Sebbene l'Apprendimento per Rinforzo Profondo (DRL) combinato con le Reti Neurali a Grafo (GNN) abbia mostrato potenziale nel generalizzare a dimensioni di istanza più grandi e nel gestire singoli tipi di interruzione, non è stato ancora testato se una singola policy possa ottenere simultaneamente la generalizzazione delle dimensioni (prestazioni ottimali su istanze più grandi di quelle viste durante l'addestramento) e la robustezza multi-interruzione (gestione simultanea di guasti alle macchine, tempi stocastici e arrivi dinamici).

Metodologia
I ricercatori hanno impiegato un protocollo pre-registrato e statisticamente rigoroso per valutare un encoder relazionale Graph Isomorphism Network (GIN) accoppiato con un agente Proximal Policy Optimization (PPO).

• Architettura: La policy utilizza un encoder GIN relazionale che distingue tre tipi di archi (precedenza intra-job, competizione tra macchine ed eleggibilità operazione-macchina) tramite trasformazioni lineari separate prima dell'aggregazione. Questo design si colloca tra rappresentazioni di grafo completamente omogenee e completamente eterogenee. La testa dell'attore produce i logit per le operazioni candidate indipendentemente dalla dimensione dell'istanza, garantendo l'indipendenza del numero di parametri dal numero di operazioni.
• Addestramento e Ricompensa: L'agente è stato addestrato utilizzando MaskablePPO. Per testare la robustezza, lo studio ha valutato due strutture di ricompensa: una ricompensa basata sul potenziale che minimizza il makespan, e una versione estesa che incorpora una "penalità di instabilità" ($\kappa \cdot \Delta_{inst}$) per penalizzare le deviazioni dai tempi di inizio pianificati dopo le interruzioni.
• Disegno Sperimentale: Lo studio ha pre-registrato cinque ipotesi (H1–H5) con regole decisionali congelate per evitare l'HARKing (ipotesi formulate dopo la conoscenza dei risultati).
  • Baseline: La policy è stata confrontata con nove Regole di Dispatching Prioritario (PDR), un Algoritmo Genetico (GA) ottimizzato e un risolutore esatto di Programmazione Vincolata (CP-SAT).
  • Benchmark: La valutazione ha spaziato su 43 istanze delle famiglie Fisher–Thompson e Lawrence (JSSP) e sette istanze Brandimarte (FJSP), oltre a estensioni sintetiche.
  • Protocollo Statistico: I confronti hanno utilizzato test Wilcoxon signed-rank per l'analisi a coppie e test di Friedman–Nemenyi con diagrammi di differenza critica per la classificazione multi-metodo. Le dimensioni dell'effetto sono state riportate ovunque.

Risultati Chiave
Quattro delle cinque ipotesi pre-registrate sono state rigettate, mentre una è stata accettata. I risultati sono riassunti di seguito:

1. Competitività Statica (H1 - Rigettata): La policy GNN-PPO non ha superato la migliore regola di dispatching nelle istanze statiche. Il Mean Relative Percentage Deviation (RPD) della policy era del 24,82%, rispetto al 18,96% del miglior PDR (FIFO). Ha perso in tutte le istanze FJSP e ha vinto solo nel 18,6% delle istanze JSSP.
2. Generalizzazione delle Dimensioni (H2 - Accettata): La policy si è generalizzata con successo a dimensioni di istanza da 1,5× a 3,0× maggiori rispetto al set di addestramento. Sebbene il suo RPD assoluto sia rimasto non competitivo rispetto al miglior PDR, il suo rango tra dieci metodi non era significativamente peggiore del rango del miglior PDR in qualsiasi livello di dimensione. Ciò indica un trasferimento di competitività relativa piuttosto che di qualità assoluta della soluzione.
3. Robustezza Multi-Interruzione (H3 - Rigettata): La policy non è stata in grado di essere robusta sotto nove distinti regimi di interruzione (combinazioni di guasti, tempi stocastici e arrivi). In tutti i regimi, l l'Indice di Robustezza (RI) della policy è stato significativamente peggiore rispetto ai migliori PDR. L'asse degli "arrivi dinamici" è stato particolarmente deleterio, poiché rappresentava uno shift della distribuzione (inserimenti di lavori a metà episodio) non visto durante l'addestramento.
4. Ricompensa Consapevole delle Interruzioni (H4 - Rigettata): L'aggiunta della penalità di instabilità ($\kappa > 0$) alla ricompensa non ha migliorato la robustezza. Al contrario, ha causato un crollo delle prestazioni nominali (senza disturbi), aumentando l'RPD di 46,6 - 106,0 punti percentuali. Lo studio diagnostica questo fallimento come risultato del fatto che l'agente è stato addestrato esclusivamente su episodi di interruzione con randomizzazione del dominio, senza mai essere esposto ad episodi nominali (senza interruzioni).
5. Latenza Decisionale (H5 - Rigettata sotto soglia rigorosa): Sebbene la latenza decisionale della policy (4–11 ms) fosse di ordini di grandezza più veloce di CP-SAT su istanze grandi e difficili, essa ha fallito la soglia pre-registrata rigorosa (essere <1% del tempo di CP-SAT) per 42 istanze su 43. Questo fallimento è stato guidato principalmente da piccole istanze in cui CP-SAT risolveva il problema quasi istantaneamente, creando un artefatto matematico nel rapporto.

Significatività e Rivendicazioni
Il contributo centrale del documento non è un risultato positivo in termini di qualità della soluzione, ma una caratterizzazione diagnostica e statisticamente rigorosa dei limiti delle policy di scheduling GNN-PPO. Gli autori sostengono che la generalizzazione delle dimensioni e la robustezza multi-interruzione siano proprietà separabili, non un "pacchetto completo" che emerge automaticamente dalla stessa architettura.

• Trasferimento Architetturale vs. Competitività: Lo studio fornisce prove empiriche che le architetture invarianti rispetto alla dimensione possono trasferire la competitività relativa al rango (una policy può rimanere "buona quanto" il miglior euristica rispetto ad altri all'aumentare della dimensione) anche se la policy di base non è competitivamente forte in termini assolti.
• Il Costo degli Obiettivi Congiunti: Il rigetto di H3 e H4 suggerisce che una policy non può ottimizzare simultaneamente la robustezza attraverso molteplici tipi di interruzione e mantenere le prestazioni nominali senza aggiustamenti specifici all'architettura o al regime di addestramento. La "penalità di instabilità" è fallita perché il regime di addestramento (randomizzazione del dominio senza esposizione nominale) era incompatibile con il design della ricompensa.
• Rigore Metodologico: Pre-registrando ipotesi e regole decisionali, lo studio offre un risultato negativo difendibile, contrastando la tendenza ai fallimenti non spiegati nella letteratura del deep reinforcement learning applicato allo scheduling. Identifica meccanismi concreti di fallimento (ad esempio, l'impatto specifico dell'esclusione degli episodi nominali dall'addestramento) invece di attribuire le scarse prestazioni a vaghi "shift di distribuzione".

Gli autori concludono che i professionisti non dovrebbero inferire la robustezza alle interruzioni dalle sole affermazioni di generalizzazione delle dimensioni. Invece, queste capacità dovrebbero essere trattate come assi di progettazione indipendenti che richiedono valutazione e ingegneria separata. Lo studio suggerisce una potenziale strategia di implementazione ibrida in cui una policy GNN rapida e reattiva funge da fallback immediato durante le interruzioni, mentre solver più lenti e di alta qualità (GA o CP-SAT) girano in parallelo per generare programmi ottimizzati.