Research map / Graph learning / Graph algorithms and clustering
Learning to Optimize Permutation Flow Shop Scheduling via Graph-Based Imitation Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes graph-based imitation learning (GGCN encoder, attention decoder, behavioral cloning from NEH expert) for permutation flow shop scheduling, reaching lower makespan gaps and fewer parameters than an actor-critic RL baseline on instances up to 1000 jobs.
Problem
Solving large-scale permutation flow shop scheduling (PFSS) to minimize makespan, where heuristics are slow or inaccurate and RL-trained neural solvers converge slowly and are less accurate.
Approach
Replace RL training of a pointer-style encoder-decoder with behavior cloning from the NEH heuristic as expert, and use a gated graph ConvNet (GGCN) with sparsified kNN graph as the job encoder instead of an LSTM.
Key results
- IL model reduces average makespan gap to NEH from 6.8% (RL, 4.9%-8.7%) to 1.3% (0.4%-3.4%) on Gamma generated datasets.
- IL model uses 365k parameters versus 709k+267k for the RL actor-critic (about 37% of their network parameters).
- On Taillard and VRF benchmarks IL beats the RL baseline in gap at most sizes, e.g., 10.7% vs 12.6% at (200,20) Taillard.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use IL instead of RL | PFSS solver · Gamma PFSS-20 to PFSS-1000 | makespan gap: 6.8% (3.7%~17.4%) to 1.3% (0.4%~3.4%) on average | Helped |
| Use IL instead of RL | PFSS solver · Taillard and VRF benchmarks | gap | Helped |
| Replace the LSTM encoder with GGCN (ablation) | IL model · PFSS-20 | makespan: 31.0 -> 30.2 | Helped |
| Replace reinforcement learning with imitation learning (ablation) | GGCN encoder model · PFSS-20 | makespan: 30.6 -> 30.2 | Helped |
| Use MEAN instead of MAX or SUM aggregation (ablation) | GGCN · PFSS-20, PFSS-50, PFSS-100 | makespan: 36.4, 76.6, 139.9; 34.3, 72.1, 133.7; 30.2, 63.7, 118.3 | Helped |
| Use BatchNorm instead of no normalization or LayerNorm (ablation) | GGCN · PFSS-20, PFSS-50, PFSS-100 | makespan: 30.4, 64.1, 119.1; 30.3, 63.9, 118.7; 30.2, 63.7, 118.3 | Helped |
Surprising findings
- Taking the NEH heuristic as expert, the IL model's gap reported against NEH is still around 12% on Taillard instances, showing the learned policy remains far from the expert on some benchmarks.
Limitations
- Machine number must be consistent between training and testing; generalization is shown only across job sizes.
- Expert is the NEH heuristic rather than an exact solver, so IL imitates a heuristic and is bounded by its quality.
- On some benchmark settings (e.g., Taillard (100,20)) the IL gap equals the RL gap, and the RL testing is faster.
Experimental setup
Datasets: Gamma-distributed randomly generated PFSS instances Normal-distributed randomly generated PFSS instances Taillard benchmark VRF benchmark
Benchmarks: Taillard VRF Generated Gamma PFSS-20 to PFSS-1000 Generated Normal PFSS-20 to PFSS-1000 TSP (Gurobi comparison)
Metrics: makespan makespan gap to NEH runtime
Baselines: Random search Iterated local search Iterated greedy NEH Actor-critic (Pan et al.)
Builds on: Pointer network Gated Graph ConvNets Attention model (Kool et al.) NEH heuristic
Closest papers by meaning
- Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling (ICLR 2024 · similarity 0.85)
- Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling (NeurIPS 2025 · similarity 0.85)
- LineFlow: A Framework to Learn Active Control of Production Lines (ICML 2025 · similarity 0.84)
- Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation (NeurIPS 2026 · similarity 0.83)
- MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale (AAAI 2025 · similarity 0.83)
- Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems (AAAI 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.