用异构图注意力机制改进流水线调度,让模型更懂任务依赖和机器冲突。
HGT-Scheduler: Deep Reinforcement Learning for the Job Shop Scheduling Problem via Heterogeneous Graph Transformers
- 将调度问题建模为带类型区分的异构图,分别处理任务顺序与机器争用关系。
- 在FT06上最优解差距仅8.4%,显著优于忽略边类型的同类模型(p=0.011)。
- 适合需要高精度、长周期训练的复杂调度场景,尤其在大规模实例中表现更好。
作业车间调度问题(JSSP)通常被建模为析取图,其中节点代表操作,边表示技术优先约束和机器占用冲突。现有强化学习方法多将图视为同质图,将任务依赖与机器竞争边合并为单一关系类型,忽略了问题结构的内在异质性,可能丢失关键关系信息。为此,本文提出HGT-Scheduler,一种基于异构图变换器(Heterogeneous Graph Transformer)的强化学习框架,显式建模不同类型的边。该架构通过边类型相关的注意力机制,分别捕捉优先关系与竞争关系的特定模式。调度策略采用近端策略优化(Proximal Policy Optimization)训练。在Fisher-Thompson基准实例上评估表明:在FT06实例上,优化差距为8.4%,显著优于忽略边类型的相同架构(p=0.011)及标准图同构网络基线;在更大的FT10实例上展现出良好可扩展性。然而,在50,000步训练限制下,异构与同构模型性能相近,表明边类型感知需更长训练周期以在大规模实例中发挥优势。消融实验进一步显示三层注意力结构表现最佳。总体结果验证了显式建模不同边语义能有效提升调度策略的学习效果。
原文摘要 · Abstract (English)
The Job Shop Scheduling Problem (JSSP) is commonly formulated as a disjunctive graph in which nodes represent operations and edges encode technological precedence constraints as well as machine-sharing conflicts. Most existing reinforcement learning approaches model this graph as homogeneous, merging job-precedence and machine-contention edges into a single relation type. Such a simplification overlooks the intrinsic heterogeneity of the problem structure and may lead to the loss of critical relational information. To address this limitation, we propose the Heterogeneous Graph Transformer (HGT)-Scheduler, a reinforcement learning framework that models the JSSP as a heterogeneous graph. The proposed architecture leverages a Heterogeneous Graph Transformer to capture type-specific relational patterns through edge-type-dependent attention mechanisms applied to precedence and contention relations. The scheduling policy is trained using Proximal Policy Optimization. The effectiveness of the proposed method is evaluated on the Fisher--Thompson benchmark instances. On the FT06 instance, the HGT-Scheduler achieves an optimality gap of 8.4\%, statistically outperforming both an identical architecture that ignores edge types ($p = 0.011$) and a standard Graph Isomorphism Network baseline. On the larger FT10 instance, the approach demonstrates favorable scalability. However, under a 50,000-step training limit, the performance of heterogeneous and homogeneous graph models is comparable, suggesting that edge-type awareness requires longer training horizons for larger problem instances. Ablation analyses further indicate that a three-layer attention architecture provides the best performance. Overall, the results confirm that explicitly modeling distinct edge semantics improves the learning of effective scheduling policies.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。