Research map / Graph learning / Graph algorithms and clustering
Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling
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 a DRL-guided improvement heuristic for JSSP that learns to pick N5 swap moves over complete disjunctive-graph solutions, using a GNN with topological and context-aware modules, a message-passing makespan evaluator, and n-step REINFORCE.
Problem
Job-shop scheduling (JSSP) solved by DRL construction heuristics that represent partial solutions poorly and are far from optimal; hand-crafted improvement heuristics need full neighbourhood evaluation and are short-sighted.
Approach
Learn a policy that directly selects N5 neighbourhood moves on complete disjunctive graphs, with a GNN combining GIN-based topology embedding and GAT-based context embedding over job and machine subgraphs, plus a batch-parallel message-passing evaluator equivalent to CPM.
Key results
- Ours-500 reaches e.g. 9.3% gap on Taillard 15x15 versus 15.3% for ScheduleNet and 20.1% for RL-GNN under 500 steps.
- With 5000 steps, the method is the only one exceeding CP-SAT on Taillard 100x20 (3.0% gap vs CP-SAT's 3.9%).
- On extremely large instances (200x40 to 1000x40), Ours-500 beats CP-SAT with gaps of -24.31%, -20.56%, and -15.99%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the learned improvement policy instead of ScheduleNet | JSSP solver · Taillard 15×15 | Gap: 15.3% -> 9.3% | Helped |
| Use the learned improvement policy instead of ScheduleNet | JSSP solver · ABZ 10×10 | Gap: 6.1% -> 2.8% | Helped |
| Use the learned improvement policy instead of ScheduleNet | JSSP solver · FT 6×6 | Gap: 7.3% -> 0.0% | Helped |
| Use the learned improvement policy instead of BI | JSSP solver · LA 10×5 | Gap: 4.2% -> 2.1% | Helped |
| Use the learned improvement policy instead of L2D | JSSP solver · SWV 20×10 | Gap: 41.4% -> 29.6% | Helped |
| Use the learned improvement policy instead of ScheduleNet | JSSP solver · ORB 10×10 | Gap: 20.0% -> 8.2% | Helped |
| Use the learned improvement policy instead of ScheduleNet | JSSP solver · YN 20×20 | Gap: 18.4% -> 12.4% | Helped |
| Apply the learned improvement policy for 500 steps against CP-SAT | JSSP solver · 200×40, 500×60, and 1000×40 | Gap to CP-SAT: -24.31%, -20.56%, -15.99% | Helped |
| Add CAM to TPM (ablation) | DRL-guided improvement policy · JSSP 10×10 training | Convergence | Helped |
| Add TPM to CAM (ablation) | DRL-guided improvement policy · JSSP 10×10 training | Convergence | Helped |
| Use two attention heads in CAM instead of one (ablation) | DRL-guided improvement policy · JSSP 10×10 training | Convergence speed | Helped |
| Use two attention heads in CAM instead of one (ablation) | DRL-guided improvement policy · JSSP 10×10 training | Converged objective value | No clear effect |
Surprising findings
- Tabu search with the same N5 neighbourhood achieves a 1.9% smaller gap than the learned method at 5000 steps, though the learned method is faster.
- Greedy improvement stops improving after 500 steps due to cycling, whereas the learned policy keeps improving at larger step counts.
Limitations
- Trails a well-tuned tabu search at equal step budgets in solution quality.
- Uses a fixed N5 neighbourhood and has not been combined with more powerful improvement frameworks.
- Hyperparameters were empirically tuned on small problems and reported hardware is modest (a single 2070S GPU).
Experimental setup
Datasets: synthetic JSSP instances (randomly generated, five training sizes)
Benchmarks: Taillard ABZ FT LA SWV ORB YN
Metrics: average gap to best-known makespan run time per instance
Baselines: L2D RL-GNN ScheduleNet CP-SAT greedy best-improvement first-improvement tabu search
Builds on: REINFORCE Graph Isomorphism Network Graph Attention Network N5 neighbourhood
Closest papers by meaning
- Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling (NeurIPS 2025 · similarity 0.92)
- Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning (NeurIPS 2020 · similarity 0.91)
- RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States (ICLR 2026 · similarity 0.88)
- Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization (ICML 2025 · similarity 0.86)
- Learning to Optimize Permutation Flow Shop Scheduling via Graph-Based Imitation Learning (AAAI 2024 · similarity 0.85)
- Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems (AAAI 2025 · similarity 0.84)
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.