Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem
Authors:
Open Access
- 24 January 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 12, 14703-14718
Abstract
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 in terms of makespan. Interestingly in our experiments, our approach even reaches zero makespan gap for 49 among 60 JSP instances whose job numbers are more than 100 on 15 machines.Keywords
All Related Versions
Funding Information
- National Science and Technology Council (NSTC) of Taiwan (112-2622-8-A49-021, 111-2221-E-A49-101-MY2, 110-2221-E-A49-067-MY3)
This publication has 28 references indexed in Scilit:
- A graph placement methodology for fast chip designNature, 2021
- Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learningApplied Soft Computing, 2020
- Grandmaster level in StarCraft II using multi-agent reinforcement learningNature, 2019
- Mastering the game of Go with deep neural networks and tree searchNature, 2016
- Human-level control through deep reinforcement learningNature, 2015
- A new hybrid genetic algorithm for job shop scheduling problemComputers & Operations Research, 2012
- An adaptive annealing genetic algorithm for the job-shop planning and scheduling problemExpert Systems with Applications, 2011
- A genetic algorithm for the Flexible Job-shop Scheduling ProblemComputers & Operations Research, 2008
- A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespanApplied Mathematics and Computation, 2006
- Job shop scheduling techniques in semiconductor manufacturingThe International Journal of Advanced Manufacturing Technology, 2004