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

Technical Summary: Does Size Generalization Imply Disruption Robustness?

Problem Statement
This study addresses the Dynamic and Stochastic Flexible Job-Shop Problem (FJSP), a combinatorial optimization challenge where operations must be assigned to eligible machines over time. Unlike static deterministic versions, this problem incorporates three sources of uncertainty: dynamic job arrivals (modeled as a Poisson process), stochastic processing times (log-normal multipliers), and machine breakdowns (exponential time-to-failure with log-normal repair times). While Deep Reinforcement Learning (DRL) combined with Graph Neural Networks (GNNs) has shown promise in generalizing to larger instance sizes and handling single types of disruption, it remains untested whether a single policy can simultaneously achieve size generalization (performing well on instances larger than those seen in training) and multi-disruption robustness (handling simultaneous machine breakdowns, stochastic times, and dynamic arrivals).

Methodology
The researchers employed a pre-registered, statistically rigorous protocol to evaluate a relational Graph Isomorphism Network (GIN) encoder paired with a Proximal Policy Optimization (PPO) agent.

• Architecture: The policy utilizes a relational GIN that distinguishes three edge types (intra-job precedence, machine competition, and operation-machine eligibility) via separate linear transformations before aggregation. This design sits between fully homogeneous and fully heterogeneous graph representations. The actor head produces logits for candidate operations regardless of instance size, ensuring parameter count independence from the number of operations.
• Training & Reward: The agent was trained using MaskablePPO. To test robustness, the study evaluated two reward structures: a base potential-based reward minimizing makespan, and an extended version incorporating an "instability penalty" ($\kappa \cdot \Delta_{inst}$) to penalize deviations from planned start times after disruptions.
• Experimental Design: The study pre-registered five hypotheses (H1–H5) with frozen decision rules to avoid HARKing (hypothesizing after results are known).
  • Baselines: The policy was compared against nine Priority Dispatching Rules (PDRs), a tuned Genetic Algorithm (GA), and an exact Constraint Programming solver (CP-SAT).
  • Benchmarks: Evaluation spanned 43 instances from the Fisher–Thompson and Lawrence families (JSSP) and seven Brandimarte instances (FJSP), plus synthetic extensions.
  • Statistical Protocol: Comparisons utilized Wilcoxon signed-rank tests for pairwise analysis and Friedman–Nemenyi tests with critical-difference diagrams for multi-method ranking. Effect sizes were reported throughout.

Key Results
Four of the five pre-registered hypotheses were rejected, while one was accepted. The findings are summarized below:

1. Static Competitiveness (H1 - Rejected): The GNN-PPO policy did not outperform the best dispatching rule on static instances. The policy's Mean Relative Percentage Deviation (RPD) was 24.82%, compared to 18.96% for the best PDR (FIFO). It lost on all FJSP instances and only won on 18.6% of JSSP instances.
2. Size Generalization (H2 - Accepted): The policy successfully generalized to instance sizes 1.5× to 3.0× larger than the training set. While its absolute RPD remained uncompetitive compared to the best PDR, its rank among ten methods was not significantly worse than the best PDR's rank in any size tier. This indicates a transfer of relative competitiveness rather than absolute solution quality.
3. Multi-Disruption Robustness (H3 - Rejected): The policy failed to be robust under nine distinct disruption regimes (combinations of breakdowns, stochastic times, and arrivals). In all regimes, the policy's Robustness Index (RI) was significantly worse than the best PDRs. The "dynamic arrivals" axis was particularly detrimental, as it represented a distribution shift (mid-episode job insertions) unseen during training.
4. Disruption-Aware Reward (H4 - Rejected): Augmenting the reward with an instability penalty ($\kappa > 0$) did not improve robustness. Instead, it caused a collapse in nominal (undisturbed) performance, increasing RPD by 46.6 to 106.0 percentage points. The study diagnoses this failure as a result of training exclusively on domain-randomized disruption episodes without ever exposing the agent to undisturbed (nominal) episodes.
5. Decision Latency (H5 - Rejected under strict threshold): While the policy's decision latency (4–11 ms) was orders of magnitude faster than CP-SAT on large, hard instances, it failed the strict pre-registered threshold (being <1% of CP-SAT's time) for 42 out of 43 instances. This failure was largely driven by small instances where CP-SAT solved the problem almost instantaneously, creating a mathematical artifact in the ratio.

Significance and Claims
The paper's central contribution is not a positive result in terms of solution quality, but a diagnosed, statistically rigorous characterization of the limits of GNN-PPO scheduling policies. The authors argue that size generalization and multi-disruption robustness are separable properties, not a "package deal" that emerges automatically from the same architecture.

• Architectural Transfer vs. Competitiveness: The study provides empirical evidence that size-invariant architectures can transfer rank-relative competitiveness (a policy can remain "as good as" the best heuristic relative to others as size increases) even if the base policy is not competitively strong in absolute terms.
• The Cost of Joint Objectives: The rejection of H3 and H4 suggests that a policy cannot simultaneously optimize for robustness across multiple disruption types and maintain nominal performance without specific architectural or training regime adjustments. The "instability penalty" failed because the training regime (domain randomization without nominal exposure) was incompatible with the reward design.
• Methodological Rigor: By pre-registering hypotheses and decision rules, the study offers a defensible negative result, countering the trend of unexplained failures in DRL scheduling literature. It identifies concrete mechanisms for failure (e.g., the specific impact of excluding nominal episodes from training) rather than attributing poor performance to vague "distribution shifts."

The authors conclude that practitioners should not infer disruption robustness from size-generalization claims alone. Instead, these capabilities should be treated as independent design axes requiring separate evaluation and engineering. The study suggests a potential hybrid deployment strategy where a fast, reactive GNN policy serves as an immediate fallback during disruptions, while slower, higher-quality solvers (GA or CP-SAT) run in parallel to generate optimized schedules.