# Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling

arXiv: https://arxiv.org/abs/2211.10936 · HTML: https://mlsanity.com/paper/2211.10936/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 48 references that are in the map.
- First posted on arXiv 20 Nov 2022.

## Builds on (most cited first, 23 of 23)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Overcoming Exploration in Reinforcement Learning with Demonstrations](https://mlsanity.com/paper/1709.10089/) (2017)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Learning by Playing - Solving Sparse Reward Tasks from Scratch](https://mlsanity.com/paper/1802.10567/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)
- [Efficient Active Search for Combinatorial Optimization Problems](https://mlsanity.com/paper/2106.05126/) (2021)
- [Matrix Encoding Networks for Neural Combinatorial Optimization](https://mlsanity.com/paper/2106.11113/) (2021)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning](https://mlsanity.com/paper/2106.01086/) (2021)
- [ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning](https://mlsanity.com/paper/2106.03051/) (2021)
- [A Reinforcement Learning Environment For Job-Shop Scheduling](https://mlsanity.com/paper/2104.03760/) (2021)
- [Learning to generalize Dispatching rules on the Job Shop Scheduling](https://mlsanity.com/paper/2206.04423/) (2022)

## Built on by (most cited first, 20 of 20)

- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [Self-Labeling the Job Shop Scheduling Problem](https://mlsanity.com/paper/2401.11849/) (2024)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Learning to Reduce Search Space for Generalizable Neural Routing Solver](https://mlsanity.com/paper/2503.03137/) (2025)
- [BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization](https://mlsanity.com/paper/2503.07580/) (2025)
- [Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem](https://mlsanity.com/paper/2309.15517/) (2023)
- [DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems](https://mlsanity.com/paper/2406.19705/) (2024)
- [Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling](https://mlsanity.com/paper/2502.15791/) (2025)
- [Learning Topological Representations with Bidirectional Graph Attention Network for Solving Job Shop Scheduling Problem](https://mlsanity.com/paper/2402.17606/) (2024)
- [Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization](https://mlsanity.com/paper/2407.17206/) (2024)
- [Towards Efficient Constraint Handling in Neural Solvers for Routing Problems](https://mlsanity.com/paper/2602.16012/) (2026)
- [Offline reinforcement learning for job-shop scheduling problems](https://mlsanity.com/paper/2410.15714/) (2024)
- [GATES: Cost-aware Dynamic Workflow Scheduling via Graph Attention Networks and Evolution Strategy](https://mlsanity.com/paper/2505.12355/) (2025)
- [A Learning Method with Gap-Aware Generation for Heterogeneous DAG Scheduling](https://mlsanity.com/paper/2603.23249/) (2026)
- [Efficient and Trustworthy Block Propagation for Blockchain-enabled Mobile Embodied AI Networks: A Graph Resfusion Approach](https://mlsanity.com/paper/2502.09624/) (2025)
- [Generalizing Beyond Suboptimality: Offline Reinforcement Learning Learns Effective Scheduling through Random Solutions](https://mlsanity.com/paper/2509.10303/) (2025)
- [Variational Approach for Job Shop Scheduling](https://mlsanity.com/paper/2602.00408/) (2026)
- [Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling](https://mlsanity.com/paper/2603.02846/) (2026)
- [Scheduling That Speaks: An Interpretable Programmatic Reinforcement Learning Framework](https://mlsanity.com/paper/2605.18454/) (2026)
- [DynaSchedBench: Calibrated Dynamic Scheduling Benchmarks and Observability Paradox in LLM-based Scheduling Agents](https://mlsanity.com/paper/2605.27566/) (2026)

## Abstract (arXiv)

Recent studies in using deep reinforcement learning (DRL) to solve Job-shop scheduling problems (JSSP) focus on construction heuristics. However, their performance is still far from optimality, mainly because the underlying graph representation scheme is unsuitable for modelling partial solutions at each construction step. This paper proposes a novel DRL-guided improvement heuristic for solving JSSP, where graph representation is employed to encode complete solutions. We design a Graph Neural-Network-based representation scheme, consisting of two modules to effectively capture the information of dynamic topology and different types of nodes in graphs encountered during the improvement process. To speed up solution evaluation during improvement, we present a novel message-passing mechanism that can evaluate multiple solutions simultaneously. We prove that the computational complexity of our method scales linearly with problem size. Experiments on classic benchmarks show that the improvement policy learned by our method outperforms state-of-the-art DRL-based methods by a large margin.