一种基于尺度感知和异构图神经网络的深度强化学习方法,用于灵活的工作车间调度
《Advanced Engineering Informatics》:A deep reinforcement learning method based on scale perception and heterogeneous graph neural network for flexible job shop scheduling
【字体:
大
中
小
】
时间:2026年04月27日
来源:Advanced Engineering Informatics 9.9
编辑推荐:
柔性车间调度问题(FJSP)的复杂性和规模多样性导致传统方法难以应对。本文提出基于深度强化学习(DRL)、异构图神经网络(HGNN)与规模感知模块的联合方法,通过GAT编码机器节点特征、HGT编码操作节点特征,并引入四维规模感知特征,实现固定维度状态表征。实验表明该方法在10个随机问题与90个基准测试中均优于组合调度规则、元启发式算法及现有DRL方法,在解质量和计算效率上均有显著提升。
宁光帅|郑美美|夏唐斌|潘尔顺|吴侃
上海交通大学机械工程学院,中国上海200240
摘要 随着制造生产系统的扩展和运营复杂性的增加,灵活作业车间调度问题(FJSP)面临着来自各种企业应用场景的挑战。受车间配置差异和客户需求变化等因素的影响,FJSP的规模在不同场景中存在显著差异,从而导致问题状态特征的维度发生变化。现有的深度强化学习(DRL)方法通常由于依赖于特定的问题规模而存在训练效率低下和泛化能力有限的问题。为了解决这些问题,提出了一种基于规模感知和异构图神经网络(HGNN)的深度强化学习调度方法。FJSP的异构图被用作强化学习的状态表示。由于机器节点拥有众多邻居,但仅通过一种关系类型连接,而操作节点参与的关系相对稀疏但语义多样,因此设计了图注意力网络(GAT)和异构图变换器(HGT)分别对机器节点和操作节点进行编码。然后将获得的嵌入合并,生成与问题规模无关的固定维度状态表示。此外,引入了一个规模感知模块,将与规模相关的信息纳入HGNN获得的图嵌入中,从而提高不同问题规模下的泛化能力。使用随机生成的方法构建了多样化的训练数据集,并通过近端策略优化算法(PPO)实现了端到端训练。在10个随机问题和90个基准测试上的实验结果表明,所提出的方法在解决方案质量和计算效率方面优于复合调度规则、元启发式算法和现有的DRL方法。
引言 灵活作业车间调度问题(FJSP)最初由Brucker和Schlie提出[1],其中每个操作可以由给定集合中的任何机器处理。这种灵活性使FJSP更能代表现代制造系统,其复杂性体现在两个方面:为每个操作选择合适的机器以及确定所有操作的处理顺序。FJSP实例的规模通常由多个维度表征,包括作业数量、机器数量、每个作业的操作数量以及每个操作的可用机器数量。这些维度直接影响计算复杂性和获得高质量调度的难度。有效的调度方法可以显著提高生产效率、缩短交货时间并提高机器利用率。已经开发了各种关于FJSP的模型和方法,以应对各种实际生产场景,为机械加工[2]、[3]、航空航天[4]、[5]和电子制造[6]等多个行业带来了丰富的经济效益。然而,不同制造企业的车间在设备类型、数量和性能水平以及产品种类和客户批量生产需求方面通常存在差异。这些不同的生产场景导致问题属性的变化,特别是在将问题建模为FJSP实例时,问题规模和结构也会发生变化。因此,现有的解决方法需要进一步改进或适应,以实现跨多种应用场景的强泛化。
用于解决FJSP的常见方法包括精确方法、启发式方法和元启发式方法[7]。精确方法如混合整数线性规划(MILP)或约束编程(CP)通常在标准求解器的帮助下使用[8]。尽管这些方法在实践中可以直接使用,但即使对于中小规模问题,它们也很少能产生最优解。由于FJSP的高复杂性,启发式方法和元启发式方法被广泛采用,以在合理的时间内生成最优或接近最优的解决方案。启发式方法(如调度规则)计算成本较低,且对问题规模相对不敏感。但它们在解决方案质量方面往往受到很大限制,并且严重依赖于领域知识[9]、[10]。元启发式算法旨在通过迭代搜索找到更好的解决方案,但需要仔细设计算法框架并进行广泛的参数调整[11]。此外,随着问题规模的增加,元启发式方法所需的计算时间也会显著增加[12]。鉴于平衡解决方案质量和计算时间的难度,以及工业4.0下对自动化需求的增加[13],上述传统方法越来越不适合需要实时响应的多样化调度场景。
近年来,基于强化学习(RL)的方法受到了越来越多的关注,特别是那些集成深度学习模型(如图神经网络(GNN)[14]的方法。这些方法基于两个关键原则。一方面,可以使用适当的图结构(如析取图[15]或异构图[16])有效表示FJSP,这些结构描述了调度问题中作业、操作和机器之间的关联。GNN[17]非常适合学习图结构数据的表示,因为它们可以提取深层隐含特征,从而为调度任务提供启发式指导[18]、[19]。另一方面,现实世界的调度数据往往稀缺或难以获得。RL通过使代理通过与大量随机采样实例构建的环境互动来学习有效策略,从而解决了这一挑战。通过在训练过程中迭代更新代理的参数,逐渐获得最优策略[20]。现有研究通过使用GNN学习FJSP图表示,并将其作为状态输入集成到RL框架中[21],从而在一定程度上实现了泛化,使模型能够在更大的实例上保持合理的性能[22]。然而,这些方法通常需要对特定大小的数据集进行单独训练。为了在各种测试场景中取得良好性能,必须分别训练多个模型以适应不同大小的问题。因此,当依赖单个独立训练的模型时,解决方案质量和跨尺度泛化仍有很大的改进空间。
本研究试图开发一种深度强化学习方法,能够在单次训练后实现对不同规模问题的强泛化。为了为RL代理提供有效的状态表示,设计了图注意力网络(GAT)和异构图变换器(HGT),分别从FJSP的异构图中的机器节点和操作节点提取特征。然后将获得的特征向量合并,以实现捕捉图中局部结构信息的固定维度表示。此外,提出了一种规模感知模块,将与规模相关的信息显式编码到图嵌入中,从而提高不同FJSP实例的泛化能力。最后,应用近端策略优化算法实现单次迭代过程中的端到端训练。本研究的主要贡献总结如下:
(1) 为了有效捕捉FJSP异构图中的局部特征信息,设计了一种异构图神经网络(HGNN)。根据图中不同节点类型的独特特征,HGNN为机器节点引入了GAT,为操作节点引入了HGT。
(2) 设计了一个规模感知模块,从异构图结构中提取全局特征。捕获了四个精心设计的与规模相关的特征,以提高跨尺度泛化能力。
(3) 广泛的数值实验表明,所提出的方法在解决方案质量和计算效率方面优于复合调度规则、元启发式方法和现有的DRL方法。
本文的其余部分组织如下。第2节介绍了文献综述。第3节给出了FJSP的数学模型和异构图表示。第4节详细介绍了基于异构图神经网络和规模感知的深度强化学习方法。第5节详细介绍了设计的异构图神经网络和规模感知模块以及实验结果和分析。第6节给出了结论和未来研究的潜在方向。
部分摘录 文献综述 文献综述基于两个主题:解决FJSP的传统方法和用于FJSP的图神经网络(GNN)方法。其中,重点关注结合GNN和DRL的方法。此外,还提供了本文的研究空白。
FJSP的数学模型 灵活作业车间调度问题(FJSP)是一个典型的组合优化问题,在汽车制造和电子组装等生产领域有广泛的应用。一个规模为n × m 的问题可以描述如下:有n 个作业需要在m 台机器上处理。每个作业由O i 个操作组成,其中操作的数量因作业而异。因此,操作的总数为∑ i = 1 n O i
主要框架 为了有效提高对不同规模FJSP实例的泛化能力,提出了一种基于规模感知和异构图神经网络(SHL)的深度强化学习调度方法。所提出的SHL的主要框架如图2所示。FJSP主要涉及操作选择和机器分配。首先,将一个问题的解决过程建模为马尔可夫决策过程(MDP),其中每个调度时间步的状态是
实验与讨论 为了评估所提出方法的性能,所有实验都在python 3.8环境中使用gym 0.22.0和torch 2.0框架进行。计算是在配备Intel Xeon(R) Platinum 8255C CPU和NVIDIA RTX 2080Ti 11 GB GPU的个人计算机上进行的。为了确保可重复性,本文中使用的所有算法的完整代码和数据可以在以下网站找到:
https://github.com/36inn/SHL.git 结论 为了解决由于车间配置变化和订单需求波动而在不同企业应用场景中出现的FJSP问题,提出了一种集成规模感知和异构图神经网络的深度强化学习框架。所提出的方法在单次训练阶段后实现了对不同规模调度问题的有效泛化。具体来说,使用异构图来模拟机器之间的结构关系
CRediT作者贡献声明 宁光帅: 写作 – 审稿与编辑,撰写原始草稿,可视化,验证,软件,资源,方法论,调查,形式分析,数据管理,概念化。郑美美: 写作 – 审稿与编辑,监督,资源,方法论,资金获取,形式分析。夏唐斌: 验证,方法论,概念化。潘尔顺: 验证,数据管理。吴侃: 验证。
利益冲突声明 作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。
致谢 本研究得到了国家自然科学基金 的支持,资助编号为#72271162。
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号