合理的生产调度方案对制造类企业提高生产效率、降低成本具有重大意义。柔性作业车间调度问题（Flexible Job-shop Scheduling Problem, FJSP）是组合优化和生产管理领域的重要研究课题。

图1 生产车间

现有针对FJSP的研究通常假设生产调度模型中的机器可以长时间运转，无需停工，即加工时间连续。然而，这与真实生产场景中必须考虑机器临时性检修或周期性维护导致加工过程间歇性停止的情况不符。此外，出于对聚焦核心业务或者降低生产成本的考虑，工厂会委托第三方代加工产品的部分工序。现有的FJSP模型主要采用成本折算的方式处理外协工序，即将工序外包作为可选项而非强制性约束。

由于现有调度模型尚未考虑上述两种在实际工业场景中常见的约束情形，因此需要建立更真实的FJSP模型以及能求解该复杂调度问题的算法。在求解调度问题的优化算法方面，现有基于学习的优化算法难以处理组合优化问题中结构化信息数据维度不确定的问题。此外，已有算法主要采用直接生成最终解或以贪婪策略展开搜索的寻优方式，所以在优化结果的精确度上难以与传统的元启发式算法相比。

为解决电源设备生产制造行业中的实际调度问题，智能算法研究中心的研究人员对带周期维护及强制外包约束的柔性工作车间调度问题（Flexible Job-shop Scheduling Problem with the Periodic Maintenance and Mandatory Outsourcing constraints，FJSP-PMMO）进行建模，并设计了一个基于强化学习的微搜索算法——自组织神经搜索框架（Self-organizing Neural Scheduler, SoNS）来求解FJSP-PMMO问题[1]。与最新的FJSP模型相比[2-3]，FJSP-PMMO考虑了间歇维护以及外包因素，故每个工件的工序数目以及加工顺序不同，且加工机器数≠工件工序数，解的表示为有向无环图而非顺序序列。在算法层面，SoNS采用机器学习的方法实现了对工件加工工序以及加工位置的自适应选择，替代了同类方法中使用随机策略进行调度的方式，提高了调度的可靠性和准确性。该成果已发表在人工智能领域的国际顶级学术期刊IEEE Transactions on Cybernetics（JCR一区，影响因子19.118）上。

图2 现有的FJSP模型与FJSP-PMMO模型对比

SoNS算法采用有向无环图表示一个加工流程方案，其中有向实线依次连接属于同一作业的工序，有向虚线依次连接分配给同一机器处理的工序，该算法的总体流程如图3所示。

图3 SoNS算法总体流程

该算法1）首先随机生成规模较小的初始候选解集，解集中的每个解为一种调度方案；2）接着标记出当前最好的调度方案，即当前最优解；3）然后在迭代条件尚未满足时，从候选解集中任选两个解，经过交叉等操作生成新的候选解后，采用神经调度器（Neural Scheduler, NS）为选中的解提供改进方向；4）之后将产生的新候选解与当前最好解进行比较，保留较优的解。

图4 SoNS算法伪代码

其中，NS是研究人员设计出能搜寻解较优改进方向的强化学习模型。此模型能将搜索过程中邻域结构构造转化为强化学习的应用场景，以预测候选解的改进方向。NS含有预测工序变动带来潜在奖励值改变的变动工序选择器（Mutation Operator Selector, MOS）和评估变动加工位置好坏的变动位置选择器（Mutation Location Selector, MLS）。这两个选择器均采用多层神经网络结构，通过拟合Q函数和多步改进的最大奖励值，形成一个能改进有效搜索方向的模型，从而为候选解提供改进方向。

图5 NS中的变动工序选择器（上）与变动位置选择器（下）

不同于一般算法中对每个样例数据编码的方式，SoNS算法对每道工序进行编码，并通过一个长短时记忆编码器（Long Short-Term Memory encoder，LSTM）生成表征该工序的特征向量，从而实现了将变维度的结构化输入信息转化为定长嵌入特征向量的效果。大多数学习优化算法总是希望通过学习的方式产生更优解，然而，这种思路在组合优化问题上难以获得成功，因为该类问题输入输出空间度量是不一致的。而SoNS算法通过机器学习确定解搜索的决策子集，使得算法可以在通过LSTM生成定长特征向量后，仅训练一个模型就可以处理不同规模的问题，较好地避开了空间度量不一致的巨坑。

图6 SoNS算法与大多数学习优化算法对比

此外，不同于目前学习优化方法中将FJSP建模为纯随机的马尔可夫决策过程，SoNS算法采用基于搜索的求解方式，用机器学习方法实现了有效决策子集的定位，降低了同类研究方法中以随机方式确定有效决策子集的盲目性，提高了搜索的准确性。

表1展示了不使用神经调度器的算法版本（SoNS_ns）、不采用自组织框架的算法版本（SoNS_so）以及完整版SoNS在DP-PMMO用例集上的消融性实验结果。

表1 SoNS、SoNS_ns及SoNS_so在DP-PMMO测试集上的消融性实验对比

表1结果表明，神经调度器显著提升了SoNS算法的性能。同时，不采用自组织框架的算法SoNS_ns在43.8%（137/313）的测试用例上性能显著差于完整版算法，在剩余56.2%（176/313）的测试用例上性能差异不显著。

表2展示了SoNS同其他前沿调度算法在DP-PMMO测试集上的对比结果。数值实验采用柔性作业车间调度领域广泛采用的四个测试集BRData、HUData、DPData和BCData，共313个测试用例，其中用例提供的初始信息有任务数量、各任务工序数量、机器数量、各工序可加工机器集合以及加工时长等。非参数Krusal-Wallis检验被用于比较对比算法和自组织神经调度器求得的结果。实验结果显示，SoNS分别在211、219、254、184、192个测试用例上优于VNS-GA、HEA[4]、MAE[5]、hGA[6]、TL-PSO[7]算法。

表2 SoNS同其他前沿调度算法在DP-PMMO测试集上的性能对比

实验结果表明，SoNS的性能可在统计意义上超过前沿的元启发式算法。这是因为自组织微搜索框架通过强化学习模型确定了可能含有最优解的微小邻域结构，使得算法只需将算力部署在最具搜索潜力的区域，从而节省了在微小邻域结构范围以外搜索的算力开支。

目前，智能算法研究中心研发的支持工序任务量拆分的智能排产方法已申请国家专利和美国专利，并获得国家专利授权。此外，我们的生产调度算法和智能排产方法已应用于国内多家电子与电池生产企业的工件加工调度系统，实现了将排产时间从手动排产的3-10天降低到自动排产的3秒-10分钟。智能排产方法针对49张订单制定生产计划，生成的结果包含265次机台调度，生产时间跨度2个月，总耗时3.265秒，100%符合所有实际生产场景的约束。

图7 支持工序任务量拆分的智能排产方法

参考文献

[1] J. Su, H. Huang, G. Li, X. Li and Z. Hao, "Self-organizing neural scheduler for the flexible job shop problem with periodic maintenance and mandatory outsourcing constraints," IEEE Transactions on Cybernetics, doi: 10.1109/TCYB.2022.3158334.

[2] D. Bai, X. Bai, J. Yang, X. Zhang, T. Ren, C. Xie and B. Liu, "Minimization of maximum lateness in a flowshop learning effect scheduling with release dates," Computers & Industrial Engineering, vol. 158, pp. 1-16, 2021.

[3] Z. Pan, L. Wang, J. Wang and J. Lu, "Deep reinforcement learning based optimization algorithm for permutation flow-shop scheduling," IEEE Transactions on Emerging Topics in Computational Intelligence, doi: 10.1109/TETCI.2021.3098354.

[4] X. Li and L. Gao, "An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem," International Journal of Production Economics, vol. 174, pp. 93-110, 2016.

[5] J. Ding, Z. Lu, C. Li, L. Shen, L. Xu, and F. Glover, "A two-individual based evolutionary algorithm for the flexible job shop scheduling problem," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, 2019, pp. 2262-2271.

[6] A. Turkyılmaz and S. Bulkan, "A hybrid algorithm for total tardiness minimisation in flexible job shop: genetic algorithm with parallel VNS execution," International Journal of Production Research, vol. 53, no. 6, pp. 1832-1848, 2015.

[7] R. Zarrouk, I. E. Bennour, and A. Jemai, "A two-level particle swarm optimization algorithm for the flexible job shop scheduling problem," Swarm Intelligence, vol. 13, no. 2, pp. 145-168, 2019.

[8] 支持工序任务量拆分的智能排产方法（201810409715.0） 授权公告号：CN108776862B，美国专利申请号：US 17/052,426，发明人：黄翰、苏俊鹏、李学强、郝志峰

总编：黄翰

责任编辑：袁中锦

文字：苏俊鹏、遆雅琪

图片：遆雅琪、袁中锦

校稿：何莉怡

时间：2022年8月15日