编者按
本次解读的文章揭橥于IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS，原文择要总结如下：本文考虑了众所周知的灵巧作业车间调度问题，并通过提出一种新颖的深度强化学习（DRL）方法来端到端地学习高质量的优先级调度规则（PDR） 来办理这些问题。操作选择和机器分配被组合为一个复合决策。此外，基于一种新颖的调度状态异构图表示，提出了一种基于异构图神经网络的体系构造来捕获操作和机器之间的繁芜关系。实验表明，所提出的方法优于传统的 PDR，并且打算效率高，纵然在演习中未见过的更大规模和不同属性的实例上也是如此。
1 弁言本文重点先容灵巧的作业车间调度问题 (FJSP)，它是作业车间调度问题 (JSP) 的众所周知的推广，在云制造中具有广泛的运用。与 JSP 不同，FJSP 许可在一组可选机器中的任何机器上处理操作。
关键研究问题：1）如何制订调度过程以结合机器分配；2）如何设计表示方案和神经架构以从原始调度状态中提取有用信息。针对研究问题 1)：本文提出了一种用于基于 PDR 的 FJSP 调度的马尔可夫决策过程（MDP）公式，个中一个动作是选择一个合格的操作-机器 (O-M) 对，这样就可以同时做出操作选择和机器分配决策。针对研究问题 2)，通过扩展具有机器节点的 FJSP 的析取图，本文提出了一种新颖的异构图构造来表示 MDP 状态，从而可以捕获操作和机器之间的繁芜关系。
此外，本文提出了一种两阶段图神经网络（GNN）来得到异构图中节点的特色嵌入，在此根本上利用近端策略优化（PPO）设计和演习策略网络。与现有的基于 DRL 的调度方法中利用的 GNN 不同，本文提出的 GNN 专门用于 FJSP 的异构图，它捕获了不仅是操作的状态，还有机器和 O-M 关系的状态。
2 FJSP问题3 析取图4 方法概述
在本文中，办理FJSP被认为是一个顺序决策过程，它迭代地采纳调度动作，将一个操作分配给每个状态的兼容机器，直到所有操作都被调度。所提出方法的事情流程如图2所示。在每次迭代中，调度状态首先转换为异构图构造。然后，将具有两阶段嵌入过程的异构图神经网络（HGNN）运用于异构图，以提取操作和机器的特色嵌入，决策网络利用这些嵌入来天生动作概率分布，从中采样调度操作。
5 马尔科夫决策过程
6 异构图
7 异构图神经网络8 策略演习
9 实验结果为了进行测试，利用贪婪策略和采样策略对策略进行测试，分别命名为DRL-G 和DRL-S。对付每个演习规模，表1报告了从与演习相同的分布中抽取的 100 个测试实例的 OR-Tools 办理方案的均匀落成韶光和差距。对付基于 PDR 的方法，所提出的方法（在两种策略中）在四种演习规模中始终优于所有基线 PDR。为了进行更详细的比较，将所提出的方法作为参考来打算每个基线 PDR 的差距，箱线图如图5所示。可以不雅观察到，所提出的方法在近 75% 的实例上超过了 MWKR。
本文进一步考验了所提出的大小不可知策略在推广到未见过的大型实例方面的能力。为此，在 20 × 10 实例上演习的策略直接在 30 × 10 和 40 × 10 实例上运行，结果总结在表2中。可以不雅观察到，所提出方法的上风在这些大型实例上仍旧保持，表明在小型和中型实例长进修的模式在办理大型实例时仍旧有效。
本文在基准实例上评估演习策略在传统研究中常常利用的两个公共基准上的泛化性能。表3总结了却果。
与最近在mk基准上报告结果的方法比较，所提出的方法明显优于它（在 20×5 实例上演习的策略除外），显示了 HGNN 在提取丰富状态信息方面的上风更好的决策。
参考文献•Song W, Chen X, Li Q, et al. Flexible Job-Shop Scheduling via Graph Neural Network and Deep Reinforcement Learning[J]. IEEE Transactions on Industrial Informatics, 2022, 19(2): 1600-1610.
•F. Ni et al., “A multi-graph attributed reinforcement learning based optimization algorithm for large-scale hybrid flow shop scheduling problem,” in Proc. 27th ACM SIGKDD Conf. Knowl. Discov. Data Mining, 2021, pp. 3441–3451.
作者信息•Wen Song, Institute of Marine Science and Technology, Shandong University, Qingdao, China.
•Xinyang Chen, School of Control Science and Engineering, Shandong University, Jinan, China.
•Qiqiang Li, School of Control Science and Engineering, Shandong University, Jinan, China.
•Zhiguang Cao, Singapore Institute of Manufacturing Technology, Singapore.
