一种用于动态灵活作业车间调度问题的深度强化学习算法，该算法结合了异构图和分层注意力机制

《Engineering Applications of Artificial Intelligence》：A deep reinforcement learning algorithm with heterogeneous graph and hierarchical attention mechanism for dynamic flexible job shop scheduling problem

　　摘要
动态灵活作业车间调度（DFJSS）在具有动态事件（如订单变更和随机新作业插入）的制造系统中广泛存在。尽管精确算法、启发式算法和元启发式算法已广泛应用于调度问题，但在DFJSS中实时自适应决策仍然具有挑战性，因为新插入的作业会改变当前车间状态，增加机器分配和操作排序的复杂性。为了解决这个问题，本文提出了一种基于异构图和分层注意力机制的深度强化学习框架（DRL-HGHAM）。在所提出的框架中，作业、操作和机器被表示为异构图中的不同类型的节点，它们之间的关系类型用于描述优先级约束、机器适用性和资源竞争。然后采用分层注意力机制从异构图中提取与决策相关的局部和语义信息。基于学习到的状态嵌入，强化学习代理从五个设计的候选规则中选择一个合适的调度规则来生成调度决策。在包含随机新作业插入的DFJSS实例上的实验结果表明，与测试的基线方法相比，DRL-HGHAM在延迟性能方面表现更好，并且具有良好的可扩展性。

引言
作业车间调度（JSS）问题是制造企业中的一个挑战性问题，因为它需要确定在有限的资源（如机器）上执行一系列作业的最佳顺序，以最小化总延迟或其他性能指标（Geurtsen等人，2023；Wang等人，2022）。随着制造业向更高水平的智能和灵活性发展，传统的JSS方法越来越难以应对复杂生产环境带来的挑战（Dauzère-Pérès等人，2024）。因此，出现了灵活JSS（FJSS）问题（An等人，2023），通过允许每个操作在多个替代机器上执行来引入机器灵活性，从而提高了调度灵活性并增加了复杂性（Gao等人，2019）。然而，现实世界的生产环境特征是动态不确定性的存在，例如机器故障、紧急订单插入和加工时间波动。在这种情况下，动态FJSS（DFJSS）（Zhang等人，2021）提供了一种更实用和现实的方法，并已成为一个重要的研究课题（Li等人，2024）。在这些干扰中，本研究重点关注随机新作业插入，这是一种常见的动态事件，会改变当前的车间状态并需要及时的调度调整。

传统的DFJSS解决方案通常分为精确算法、启发式算法和元启发式算法。精确算法，包括分支定界（B&B）（Brucker等人，1994）和整数线性规划（ILP）（Yan等人，2022），能够为小规模实例获得最优解，但随着问题规模的增加，它们的计算负担会迅速增加。启发式算法，如优先调度规则（PDRs）（Durasevi?和Jakobovi?，2018），通过遵循预定义的规则高效生成可行调度，但其固定的决策逻辑限制了它们对变化车间状态的适应性。元启发式算法，如遗传算法（GA）和禁忌搜索算法（TS）（Li和Gao，2020），提供了更强的全局搜索能力；然而，在动态作业插入的情况下重复搜索或重新调度可能会导致高计算成本。总体而言，这些方法在同时满足实时响应性和动态适应性方面面临困难，并且缺乏有效的方法来捕捉作业、操作和机器之间的复杂交互。

DFJSS的内在复杂性源于两个相互交织的来源。组合爆炸性源于机器灵活性（每个操作有多个候选机器）和优先级约束（作业内的操作遵循部分顺序）。对于一个有??个作业的问题，每个作业??有???个操作，每个操作平均有ˉ??个替代机器，可能的调度数量大约为∏????=1(ˉ??)???，随着问题规模的增加而呈超指数增长。非静态性由随机作业插入引入：系统的状态分布和最优调度策略会随时间变化，使得精确算法（例如分支定界）和元启发式算法（例如遗传算法）所假设的静态环境失效。传统方法要么依赖于完全枚举（精确算法），要么依赖于固定规则（启发式算法），要么依赖于离线优化（元启发式算法），这些方法都无法有效适应非静态、组合爆炸性的环境。因此，在动态环境中高效解决DFJSS仍然是一个重要的研究挑战。为了应对这些挑战，越来越需要先进的技术来建模DFJSS中的复杂依赖性和动态行为。

近年来，随着深度学习技术的快速发展，图神经网络（GNN）及其变体（如异构图注意力机制（HGAM）在处理复杂关系数据方面展示了显著的潜力（Zhao等人，2024）。HGAM通过建模各种类型的节点和边，有效捕捉了机器、操作和作业之间的复杂交互关系。GNN和注意力机制的最新进展表明，利用结构化数据表示和自适应学习能力为解决复杂优化问题提供了巨大潜力。特别是，异构图神经网络（HGNN）在其他复杂领域中展示了强大的建模能力，但其在动态灵活作业车间调度中的应用仍然很大程度上未被探索。尽管取得了上述进展，现有的DFJSS方法仍面临两个关键限制。传统的精确、启发式和元启发式方法要么假设静态环境，要么需要昂贵的重新调度，这使得它们在随机作业插入的情况下无效。此外，基于DRL的最新方法通常使用同构图表示，无法完全捕捉作业、操作和机器之间的异构关系，或缺乏优先考虑关键特征的注意力机制。为了填补这一研究空白，本文的核心目标是开发一个集成异构图表示和分层注意力机制的DRL框架。该框架旨在学习一种能够持续适应动态新作业插入并最小化总延迟的反应式调度策略，而无需任何离线重新优化。

本研究的主要贡献，包括方法创新和实际应用，总结如下：
•开发了一种异构图表示，以明确建模作业、操作、机器及其类型关系。与直接应用图卷积的现有异构图基础调度方法不同，DRL-HGHAM将这种表示与分层注意力机制结合在一起，以捕捉局部节点交互和全局跨类型语义。
•提出了一种分层注意力机制，包括用于局部特征聚合的节点级注意力和用于跨类型特征融合的语义级注意力，这使得DRL-HGHAM区别于现有的单层注意力基方法。
•设计了一个规则选择动作空间，代理从五个互补的调度规则中选择，而不是直接生成操作-机器分配，从而在保持动态作业插入下的自适应调度能力的同时降低了决策复杂性。基于这些设计，所提出的框架为动态制造系统提供了一种有效的在线决策方法，支持对意外作业插入的及时响应。

本文的其余内容结构如下：第2节回顾了解决DFJSS问题的相关工作。第3节介绍了FJSS和DFJSS的概况。第4节详细介绍了所提出的DRL-HGHAM的设计。第5节提供了实验设置和结果分析。最后，第6节总结了本文。

数学模型
本文考虑的FJSS问题在操作优先级和机器适用性约束下协调生产任务和机器资源。每个作业由一系列操作组成，每个操作可以在几个符合条件的机器之一上进行处理，每个操作的处理时间取决于机器。数学公式中使用的符号在表1中进行了总结。上述公式主要涉及两个核心调度决策：机器分配和操作选择。

DRL-HGHAM用于DFJSS
本节详细介绍了基于DRL的异构图分层注意力机制（DRL-HGHAM），如图1所示。该框架包括三个关键组成部分：1）异构图（HG）表示，它捕捉了DFJSS环境中作业、机器和操作之间的复杂关系；2）分层注意力机制（HAM）用于从异构图中提取关键信息并将其编码为低维表示；3）强化学习算法（DRL）用于根据提取的信息生成调度决策。

基于仿真的实验验证在DFJSS研究中是常用的方法。本研究设计了训练、测试和验证实例，问题规模表示为|??|×|??|。对于训练和验证，使用了10000个10×15规模的合成实例，其中处理时间???????均匀分布为???[1,19]。详细的生产配置参数在表2中总结。

结论与未来工作
本文探讨了使用HG、HAM和DRL技术对DFJSS问题的建模和优化。DJSSP的复杂性特征是异构图，DRL被集成以应对动态事件的不确定性。HG和HAM在复杂调度问题中显示出显著的优势，因为它们具有强大的建模能力和动态特征捕捉能力，以及强大的泛化性能和决策优化能力。

作者贡献声明
Fuqing Zhao：调查、资金获取、形式分析、概念化。
Zongsi Fu：撰写原始草稿、方法论、形式分析。

利益冲突声明
作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。

致谢
本工作部分得到了中国国家自然科学基金（项目编号62473182）的支持；部分得到了甘肃省教育厅产业支持项目（项目编号2024CYZC-15）的支持；以及部分得到了兰州市科学技术计划（项目编号2025-3-019）的支持。

Fuqing Zhao | Zongsi Fu
兰州理工大学计算机与通信学院，中国兰州730050