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

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.

作业车间调度问题（Job-shop scheduling problem, JSP）是一类广泛应用于制造等工业领域的数学优化问题，其柔性变体柔性作业车间调度问题（Flexible JSP, FJSP）亦是常见的研究分支。由于二者均属于NP难问题，难以在合理时间内求解所有场景下的最优解，因此开发高效启发式算法以求解JSP与FJSP具有重要研究意义。
求解调度问题的一类方法为构造式启发式算法，即通过启发式规则构建调度方案。近年来，诸多构造式启发式方法结合了深度强化学习（deep reinforcement learning, DRL）与图神经网络（graph neural networks, GNN）。本文提出一种全新的JSP/FJSP求解方法，命名为残差调度法。在该方法中，我们移除已完成的无关机器与作业，使状态空间仅保留剩余（或有效）的机器与作业。
实验结果表明，在主流公开JSP与FJSP基准测试集上，所提方法在所有已知构造式启发式算法中达到当前最优（state-of-the-art, SOTA）水平。此外，我们观察到，即便模型仅针对小尺寸调度问题进行训练，该方法在大尺寸调度问题的完工时间（makespan）指标上仍表现优异。值得注意的是，在针对15台机器、作业数超过100的60个JSP测试实例中，我们的方法在其中49个实例上实现了完工时间差距为零的效果。