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

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.