# Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 46 references that are in the map.
- First posted on arXiv 27 Sep 2023.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [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)
- [Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling](https://mlsanity.com/paper/2211.10936/) (2022)

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

- [Graph Neural Networks for Job Shop Scheduling Problems: A Survey](https://mlsanity.com/paper/2406.14096/) (2024)
- [BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization](https://mlsanity.com/paper/2503.07580/) (2025)
- [Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling](https://mlsanity.com/paper/2502.15791/) (2025)
- [Leveraging Constraint Programming in a Deep Learning Approach for Dynamically Solving the Flexible Job-Shop Scheduling Problem](https://mlsanity.com/paper/2403.09249/) (2024)
- [Offline reinforcement learning for job-shop scheduling problems](https://mlsanity.com/paper/2410.15714/) (2024)
- [REMoH: A Reflective Evolution of Multi-objective Heuristics approach via Large Language Models](https://mlsanity.com/paper/2506.07759/) (2025)
- [Scheduling Distributed Flexible Assembly Lines using Safe Reinforcement Learning with Soft Shielding](https://mlsanity.com/paper/2311.12572/) (2023)
- [Unraveling the Rainbow: can value-based methods schedule?](https://mlsanity.com/paper/2505.03323/) (2025)
- [Generalizing Beyond Suboptimality: Offline Reinforcement Learning Learns Effective Scheduling through Random Solutions](https://mlsanity.com/paper/2509.10303/) (2025)
- [Online Operator Design in Evolutionary Optimization for Flexible Job Shop Scheduling via Large Language Models](https://mlsanity.com/paper/2511.16485/) (2025)
- [Variational Approach for Job Shop Scheduling](https://mlsanity.com/paper/2602.00408/) (2026)
- [Graph-RHO: Critical-path-aware Heterogeneous Graph Network for Long-Horizon Flexible Job-Shop Scheduling](https://mlsanity.com/paper/2604.10073/) (2026)

## Abstract (arXiv)

Job-shop scheduling problem (JSP) is a mathematical optimization problem widely used in industries like manufacturing, and flexible JSP (FJSP) is also a common variant. Since they are NP-hard, it is intractable to find the optimal solution for all cases within reasonable times. Thus, it becomes important to develop efficient heuristics to solve JSP/FJSP. A kind of method of solving scheduling problems is construction heuristics, which constructs scheduling solutions via heuristics. Recently, many methods for construction heuristics leverage deep reinforcement learning (DRL) with graph neural networks (GNN). In this paper, we propose a new approach, named residual scheduling, to solving JSP/FJSP. In this new approach, we remove irrelevant machines and jobs such as those finished, such that the states include the remaining (or relevant) machines and jobs only. Our experiments show that our approach reaches state-of-the-art (SOTA) among all known construction heuristics on most well-known open JSP and FJSP benchmarks. In addition, we also observe that even though our model is trained for scheduling problems of smaller sizes, our method still performs well for scheduling problems of large sizes. Interestingly in our experiments, our approach even reaches zero gap for 49 among 50 JSP instances whose job numbers are more than 150 on 20 machines.