引言

车间调度问题（又称“作业车间调度问题”、Job-Shop Scheduling Problem）是一类组合优化（Combinatorial Optimization）问题，在交通运输、制造业等领域的数学建模中应用较多。车间调度问题、以及其它很多组合优化问题都是NP-Hard问题，然而经过多年研究，针对这些问题产生了很多经典的近似求解方法。例如，针对车间调度问题就有基于元启发式算法(Metaheuristics)、约束规划（Constraint Programming）等近似求解方法。

近年来，监督式学习、自监督学习、深度强化学习等深度学习方法开始应用于车间调度问题等组合优化问题的求解。相对于经典的求解方法，当前的基于深度学习的求解方法显现出以下的优点：

• 求解速度快；
• 求解的质量逐渐接近于、甚至在有的情况下优于经典的求解方法。

车间调度问题

【算AI】小编在这里简单回顾一下车间调度问题。常见的一种车间调度问题涉及多个作业（Jobs）在多台机器（Machines）上的执行。其中，每个作业由一系列任务（Operations）组成。这一系列任务需要按特定的顺序执行。这一系列任务中的每个任务需要在特定的一台机器上执行，并消耗特定的时间。车间调度问题属于优化问题，其优化目标通常是通过安排各台机器上的任务执行顺序，使得所有任务完工的总时间为最少。

一个小规模的车间调度问题的示例[1]如下表所示。该示例中有三个作业（j₁、j₂、j₃）和三台机器（m₁、m₂、m₃），每个作业由两到三个任务（o₁₁、o₁₂、....）组成。列表中的数值为每个任务在执行时所消耗的时间。

针对该车间调度问题，以下的两张图[1]分别展示出两个解，也就是两种对于各机器的任务安排。两个解的完工总时间分别为15和11；其中，后一个解按照完工总时间来说是最优解。

任务安排一：

任务安排二：

中大规模的车间调度问题，随着计算精确解的计算量迅速增大，依靠常规的计算硬件在短时间内精确求解很快变得不切实际。

深度学习方法 vs 经典求解方法

来自于西班牙Tecnalia研究中心和西班牙巴斯克大学的研究人员近期发表了一篇论文[2]，该论文的部分内容包括针对车间调度问题的多种近似求解方法的评测。这些近似求解方法包括几种基于深度学习的求解方法，以及一种经典的求解方法——开源运筹学工具OR-Tools中的约束规划求解器CP-SAT（以下简称OR-Tools）。

评测一方面是比较求解的速度。在针对Taillard基准数据集进行评测时，几种基于深度学习的方法求解一个车间调度问题的平均耗时是几秒到十几秒，如以下列表所示。在以下列表中，Size列表示的是车间调度问题的规模（作业数量 x 机器数量）；列表中其它数值的单位为秒。

相比之下，OR-Tools在求解相同的测试实例时，每个测试实例被分配了一小时的最长运行时间；根据另外一篇论文[3]，OR-Tools求解这些测试实例的耗时经常是几十分钟。

评测的另一方面是比较求解的质量。以下的列表显示了在针对Taillard基准数据集进行评测时，几种基于深度学习的方法以及OR-Tools求解车间调度问题的质量（以“所求出的解与最优解之间的差距”来衡量）；该求解质量的数值越小越好。列表中的加粗字体表示基于深度学习的几种求解方法中的最优结果。列表中的首列表示的是车间调度问题的规模（作业数量 x 机器数量）。

从以上的列表可以看出：

• 基于深度学习的部分方法在车间调度问题的求解质量上已经接近于OR-Tools；
• 当车间调度问题的规模较大时，基于深度学习的方法在求解质量上更接近于OR-Tools；
• 当参数为100 x 20时，基于深度学习的个别方法在求解质量上超过了OR-Tools。

结语

就目前而言，基于深度学习的方法来求解车间调度问题，可能比较适用于对求解质量要求不太高、同时对求解时间要求较严的场景。

如何将深度学习与求解车间调度问题、或者其它组合优化问题进一步结合，以及如何将深度学习方法的求解性能进一步提高，还有待于更多的研究。

参考文献

[1] Offline reinforcement learning for job-shop scheduling problems.

https://arxiv.org/abs/2410.15714

[2] Self-Evaluation for Job-Shop Scheduling.

https://arxiv.org/abs/2502.08684

[3] Self-Labeling the Job Shop Scheduling Problem.

https://arxiv.org/abs/2401.11849

封面图：KJ Brix、pexels.co