《Expert Systems with Applications》：Hub-centric Heterogeneous Graph Reinforcement Learning for Integrated Automated Guided Vehicle Dispatching and Unrelated Parallel Machine Scheduling with Finite-Buffer Constraints
编辑推荐：
•提出了一种以枢纽为中心的异构图模型，其中自动导引车（AGV）连接订单、等待区和缓冲区。•设计了一种基于优先级的动作掩码，确保调度决策无死锁。•设计了一种基于最小空闲时间差的增量奖励机制。引言工业4.0和智能制造的快速发展加速了柔性制造系统（FMS）的采用，这类系统以自动化物
- •
提出了一种以枢纽为中心的异构图模型，其中自动导引车（AGV）连接订单、等待区和缓冲区。
- •
设计了一种基于优先级的动作掩码，确保调度决策无死锁。
- •
设计了一种基于最小空闲时间差的增量奖励机制。
引言
工业4.0和智能制造的快速发展加速了柔性制造系统（FMS）的采用，这类系统以自动化物料搬运、可重构生产资源和智能控制架构为特征（Koren & Shpitalni, 2010）。在这样的系统中，自动导引车（AGV）在各生产阶段之间运送工件，而并行机器则提供了处理多种产品类型所需的处理灵活性（Vis, 2006）。随着制造系统日益集成化和动态化，有效协调AGV调度和机器调度对于提高吞吐量和缩短生产周期至关重要。与传统的以机器为中心的调度问题不同，集成的AGV—机器调度涉及运输、处理和中间存储决策之间的强相互依赖性。AGV的路径直接影响工件到达机器的时间，进而影响机器利用率、队列演变和下游取件需求。当施加有限缓冲容量约束时，这种耦合变得更加复杂。在这样的环境中，如果由于相应的下游缓冲区已满而无法释放已完工工件，机器就可能被阻塞（Hall & Sriskandarajah, 1996）。此外，在非相关并行机器设置中，处理时间同时取决于机器和工件类型，这大大增加了分配决策的复杂性（Pinedo, 2016）。由产品类型切换引起的额外准备操作进一步复杂化了排序和资源协调。因此，带有有限缓冲约束的集成AGV调度和非相关并行机器调度构成了一项极具挑战性的优化问题。值得区分本研究所考虑的两个决策过程。AGV调度指的是短期的、事件驱动的运营决策，将可用的AGV分配给特定的运输任务。机器调度指的是将工件分配给非相关并行机器并确定其加工顺序。本文所考虑的问题整合了这两个决策层次：顺序的AGV调度和取件决策影响工件到达、机器队列和缓冲区占用，并与调度决策相互作用，共同决定最终的集成调度方案。
现有的解决方案在处理该问题上仍显不足。传统的分解方法通常将AGV调度与机器调度分开，独立或迭代地求解这两个子问题（Bilge & Ulusoy, 1995）。尽管这类策略在计算上是可行的，但它们往往无法捕捉运输决策与处理决策之间的紧密耦合，从而导致次优的调度方案。精确的数学规划模型可以更忠实地表示集成问题，但由于搜索空间的迅速增长，对于现实规模的实例来说在计算上是难以承受的（Deroussi, Gourgand, & Tchernev, 2008）。元启发式方法，包括遗传算法和模拟退火，在中等规模问题上显示出了前景，但其可扩展性通常有限，而且其性能通常取决于在不同场景下的大量参数调优（Ulusoy, Sivrikaya-?erifo?lu, & Bilge, 1997）。这些局限性促使人们开发更具适应性和可扩展性的解决方案范式。
深度强化学习（DRL）的近期进展为求解制造领域复杂的组合优化问题开辟了新的机遇（Zhang et al., 2020）。通过在与仿真环境的反复交互中学习调度策略，DRL智能体可以在不显式枚举解空间的情况下发现有效的决策规则。同时，图神经网络（GNN）作为一种强大的表示学习工具，在结构化调度问题中崭露头角，因为它们可以自然地编码作业、机器和辅助资源之间的相互作用（Song, Chen, Li, & Cao, 2022）。然而，大多数现有的基于GNN的调度研究依赖于同构图表示，将异构实体嵌入到统一的关系结构中，对它们的操作角色缺乏区分。这样的表示不足以应对本文所考虑的集成调度问题，在该问题中，订单、AGV、等待区和缓冲区在功能语义和交互模式上都有显著差异。图1展示了本研究中考虑的一个代表性的汽车零部件生产车间。在此环境中，订单作为任务源，其特征为类型和数量；AGV作为移动运输资源，具有动态位置和装载状态。同时，机器执行与类型相关的处理，缓冲区则限制了已完工工件的释放和临时存储。这些实体之间的相互作用本质上是异构且非对称的。例如，AGV在取件时与订单交互，在未分配或被阻塞时在等待区空闲，并在已完工工件取件期间访问缓冲区。这些交互类型传达着不同的操作含义，例如运输距离和潜在的准备影响，因此应该被显式建模，而不是合并为统一的边结构。此外，有限缓冲约束可能会触发阻塞传播，甚至当已完工工件不能及时移除时导致死锁。尽管可以在事后纳入死锁检测和恢复策略，但这会增加控制复杂性并可能降低系统性能。一种更可取的方法是将死锁预防直接嵌入调度策略本身。另一个主要挑战在于策略学习。在具有大动作空间和复杂异步动态的集成调度问题中，DRL训练往往受到稀疏且延迟的奖励信号的阻碍，因为最大完工时间（makespan）仅在回合结束时才能被完全观察到。此外，当策略函数和价值函数共享表示参数时，梯度干扰可能会损害优化稳定性并减缓收敛。当需要同时协调运输、处理和缓冲管理时，这些问题变得更加突出。
为了解决上述挑战，本文提出了HCHGNN-PPO，一个将枢纽中心异构图神经网络与近端策略优化（PPO）相结合的框架，用于带有有限缓冲约束的集成AGV调度和非相关并行机器调度。本研究的主要贡献总结如下：
- I.
本研究探讨了一个集成调度问题，同时考虑AGV调度、非相关并行机器调度和有限缓冲约束。与通常仅处理该决策结构部分内容的现有研究不同，本研究显式捕捉了在共享AGV资源下调度与已完工工件取件之间的竞争，以及由有限缓冲容量引起的阻塞和死锁风险。
- II.
开发了一种枢纽中心异构图表示及相应的HCHGNN编码器，用于建模和学习订单、AGV、等待区和缓冲区之间的非对称交互。将AGV视为连接任务源和处理资源的枢纽节点，使所提出的方法能够更准确地反映制造系统的物理协调结构，同时通过类型特定的消息传递和异构图注意力机制促进结构化状态提取。
- III.
所提出的框架整合了基于优先级的动作掩码、以最大完工时间为导向的增量奖励以及解耦的演员—评论家架构。动作掩码强制执行即时可行性并优先清除缓冲区，以减少缓冲区引起的阻塞和死锁风险，而奖励和学习架构则改进了信用分配和优化稳定性。
本文其余部分组织如下。第2节回顾相关文献。第3节从数学上形式化集成调度问题。第4节详细介绍了所提出的HCHGNN-PPO框架，包括图表示、网络架构、奖励设计和训练过程。第5节报告了计算实验和比较结果。第6节总结全文并讨论未来研究方向。
章节摘要
文献综述
与本文所研究问题相关的研究可以归纳为三个紧密联系的流派：并行机器调度、带有AGV运输和缓冲约束的集成调度，以及基于图的表示的学习型调度。尽管这些研究提供了重要的基础，但它们在本文所考虑的关键维度——非相关并行机器、AGV运输、有限缓冲约束、基于图/DRL的决策制定以及死锁感知——上的覆盖仍然有限
问题描述与数学模型
本节形式化地定义了带有有限缓冲约束的集成AGV调度和非相关并行机器调度问题。首先描述系统结构和物料流动逻辑，然后给出一个紧凑的混合整数调度公式，并讨论该问题的计算复杂度。
方法论
本节介绍了所提出的HCHGNN-PPO框架，用于带有有限缓冲约束的集成AGV调度和非相关并行机器调度。该框架形成了一个闭环决策回路，将事件驱动的仿真、基于图的状态编码、受约束的动作生成、奖励反馈以及基于PPO的策略优化联系起来。具体而言，事件驱动的仿真器揭示了车间异步的运输—处理—缓冲动态；枢纽中心的异构
计算实验
本节通过一系列全面的计算实验评估了HCHGNN-PPO的有效性。我们首先介绍实验平台、基准实例生成过程和训练超参数。然后考察所提出方法的训练行为，接着进行消融研究以隔离关键架构组件的贡献。随后，将HCHGNN-PPO与代表性的优先级调度规则和HGNN增强的深度
结论
本文研究了带有有限缓冲约束的集成AGV调度和非相关并行机器调度问题，其中运输、处理和缓冲释放决策之间的强耦合产生了阻塞和死锁风险。为应对这一挑战，本文提出了HCHGNN-PPO，一个枢纽中心的异构图强化学习框架，在统一的关系结构中建模订单、AGV、等待区和缓冲区。基于
CRediT作者贡献声明
Lei Yue：撰写—原稿，撰写—审阅与编辑，概念化，方法论，经费获取。Yuhao Zhu：撰写—原稿，概念化，方法论。Dan Luo：撰写—审阅与编辑，监督指导。Leilei Meng：监督指导，项目管理。Linshan Ding：撰写—原稿，方法论，形式化分析。
利益冲突声明
作者声明，他们没有已知的竞争性财务利益或个人关系可能影响本文所报告的工作。
Lei Yue|Yuhao Zhu|Dan Luo|Leilei Meng|Linshan Ding
