Cross-Size Generalization for GNN Job Shop Scheduling
Studied why GNN schedulers trained with reinforcement learning collapse on larger Job Shop instances: a GIN trained on 10×10 instances scores 136% above the best known schedules on Taillard 15×15. Tested the hypothesis that the cause is node degree in the disjunctive graph, which grows with the number of jobs. A 5-seed factorial showed that degree-normalized (mean) aggregation and machine-hub routing are two paths to the same ~26% error ceiling, letting a single policy trained on 10×10 instances generalize zero-shot to instances up to 20× larger, on par with the published L2D model. Built the research framework in plain PyTorch: GNN encoders (SAGE, GCN, GIN, GAT, PNA) and critic-free GRPO plus PPO trainers, benchmarked against dispatching rules on the FT, LA and TA sets. A Rice team project with Kerstin Sun and Cheng Han Lin.
Error on larger instances 136% → ~26% · zero-shot to 20× larger problems · 5 seeds