利用异构图变换器挖掘作业车间调度问题中的边语义

《Advanced Intelligent Systems》:Exploiting Edge Semantics in Job Shop Scheduling Problem With Heterogeneous Graph Transformers

【字体: 大 中 小 】 时间:2026年08月29日 来源:Advanced Intelligent Systems 6.7

编辑推荐:

  作业车间调度问题(JSSP)通常表示为析取图,其中节点表示工序,边编码工艺前继约束与机器共享冲突。大多数现有深度强化学习(DRL)方法将该图建模为同构图,把前继边与竞争边合并为单一关系类型,从而忽略了二者不同的语义。为解决此局限,研究人员提出HGT-Sched

  
作业车间调度问题(JSSP)通常表示为析取图,其中节点表示工序,边编码工艺前继约束与机器共享冲突。大多数现有深度强化学习(DRL)方法将该图建模为同构图,把前继边与竞争边合并为单一关系类型,从而忽略了二者不同的语义。为解决此局限,研究人员提出HGT-Scheduler,一种显式将JSSP建模为异构图的强化学习框架。与现有学习方法不同,该框架采用边类型特定的注意力机制区分前继关系与机器竞争关系,从而获得更丰富的调度表示。调度策略使用就近策略优化(PPO)进行优化。该框架在Fisher–Thompson基准实例上评估。在FT06上,HGT-Scheduler取得8.4%的最优性间隙,显著优于无边类型感知的同架构模型(p=0.011)以及图同构网络(GIN)基线。在更大的FT10实例上,所提方法展现出良好的可扩展性,尽管在50,000步训练预算下异构与同构表示性能相当。消融研究确定三层注意力架构为最有效配置。总体结果表明,显式建模边语义可改进智能作业车间调度中的强化学习。
研究背景方面,工业4.0推动制造系统向智能化与数据驱动转型,作业车间调度问题(JSSP)作为典型NP-hard组合优化问题,其求解长期受限于精确方法在大规模实例上的指数级计算开销与传统启发式规则(如最短加工时间SPT、最长加工时间LPT)的短视性。近年深度强化学习(DRL)将调度建模为马尔可夫决策过程(MDP),借助图神经网络(GNN)处理析取图表示,但多数方法将前继(conjunctive)边与析取(disjunctive)边合并为同构关系,模糊了工艺顺序与机器资源竞争两类语义截然不同的约束,限制了策略表达力。研究人员指出,显式保留边类型语义是突破同构图表示瓶颈的关键,因此开展将异构图变换器(HGT)与PPO结合、针对JSSP边语义建模的研究,论文发表于《Advanced Intelligent Systems》。
关键技术方法上,研究人员构建以工序为节点、含precedes(有向前继)与competes(无向机器竞争)两类类型化边的异构析取图,节点特征含归一化加工时间、完成度比例与已调度标志;采用三层HGT编码器(嵌入维64、隐藏维128、4头注意力、dropout 0.1)做类型依赖注意力消息传递,全局池化后接双层MLP分别作actor与critic;以MDP形式定义状态(动态节点特征)、动作(掩码后候选工序)、转移(确定性排程)与奖励(剩余makespan下界边际下降减常数惩罚),用PPO(裁剪代理目标、GAE优势、熵正则)在50,000步预算、5随机种子下训练,基线含Random/SPT/LPT、同构GIN、同构HGT(Homo-HGT)及CPLEX/Gurobi最优界。
研究结果部分,摘要已述FT06上HGT-Scheduler最优性间隙8.4%,优于Homo-HGT(p=0.011)与GIN;FT10上异构与同构表示在5万步内性能接近但HGT展现扩展性优势;消融确定三层注意力最佳。引言与背景章节论证同构合并导致顺序就绪信号与资源竞争信号在消息传递中被同一矩阵混叠,异构建模可分流两类约束。方法章节给出异构图形式化((’op’,’precedes’,’op’)与(’op’,’competes’,’op’)双邻接Aprec、Acomp)、HGT类型依赖Q/K/V投影(WQτ(s,t)等按边类型τ参数化)及PPO目标式(LCLIP、LVF、熵项系数cv=0.5、ce=0.01)。实验设置章节说明FT06(6×6,Cmax*=55)与FT10(10×10,Cmax*=930)及Taillard扩展集,基线控制同参数量(HGT-Scheduler 319,198参数 / Homo-HGT 294,610 / GIN 271,174)。结果章节表2显示FT06均值makespan:Random 96.1、LPT 129.0、SPT 109.0、GIN 66.6、Homo-HGT 66.0、HGT-Scheduler 59.6(间隙8.36%);FT10均值:Random 1832.8、LPT 2940.0、SPT 2648.0、GIN 1994.8、Homo-HGT 1540.6、HGT-Scheduler 1594.2(间隙71.42%),同构HGT在FT10偶然优于异构但FT06显著劣于异构,证明小实例边语义收益大。消融章节确认三层HGT为最优深度。讨论部分研究人员强调,显式边类型注意力使顺序逻辑与机器竞争经独立通道传播,避免同构混叠造成的表达损失;FT10下50k步预算不足以让异构优势完全显现,但参数规模相近时异构更具样本效率潜力;该工作首次将HGT的边类型特定机制用于JSSP析取图,构成对同构DRL调度(如L2D式GIN)的方法论推进。结论翻译:总体结果表明,显式建模边语义改进了智能作业车间调度中的强化学习;所提HGT-Scheduler在FT06以8.4%间隙逼近最优,验证前继与竞争边语义分离的有效性,三层注意力架构与PPO联合训练为后续异构图调度提供可扩展基线。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号