Mamba-CrossAttention:通过序列建模和强化学习解决灵活作业车间调度问题
《Swarm and Evolutionary Computation》:Mamba-CrossAttention: Solving Flexible Job Shop Scheduling via sequence modeling and reinforcement learning
【字体:
大
中
小
】
时间:2026年05月01日
来源:Swarm and Evolutionary Computation 8.5
编辑推荐:
曹志|张聪|吴耀欣|侯雅晴|葛宏伟
大连工业大学计算机科学与技术学院,中国大连116023
**摘要**
灵活作业车间调度问题(FJSP)是一个NP难组合优化任务,涉及将操作分配到适当的机器上,同时追求最小化完工时间等目标。在现代工业环境中,解决这个问题需要能够做出
曹志|张聪|吴耀欣|侯雅晴|葛宏伟
大连工业大学计算机科学与技术学院,中国大连116023
**摘要**
灵活作业车间调度问题(FJSP)是一个NP难组合优化任务,涉及将操作分配到适当的机器上,同时追求最小化完工时间等目标。在现代工业环境中,解决这个问题需要能够做出准确高效调度决策的智能系统。尽管基于图的学习方法已被广泛探索,但许多方法依赖于局部特征提取,这使得难以捕捉跨越操作和机器的总体依赖关系。为了克服这一限制,我们设计了一个基于Mamba的新框架,Mamba是一种具有线性计算复杂度的状态空间模型,能够高效提取FJSP特征序列中的复杂依赖关系。我们的方法采用了一个编码器和一个解码器。编码器包含一个双Mamba模块,分别提取操作和机器的表示,而解码器则结合了一个高效的交叉注意力机制来学习它们之间的交互。我们还提出了一种排列不变的强化学习算法,增强了模型的序列建模和决策能力。在多个基准数据集上进行的实验表明,与现有的基于学习的FJSP方法相比,所提出的方法性能更优。
**引言**
灵活作业车间调度问题(FJSP)是经典作业车间调度问题(JSSP)的一个重要扩展,是运筹学和计算机科学中的核心组合优化挑战。它在制造业、汽车和航空航天领域非常普遍[1]。通过允许每个操作在一系列兼容的机器上进行处理,FJSP引入了机器分配决策,除了传统的操作排序任务之外。这种额外的灵活性提高了资源利用率,但也显著增加了问题的复杂性,使其成为NP难问题[2]。在现代制造业环境中,由于高变异性和快速响应的需求,传统的精确方法往往无法扩展,而启发式[3]和元启发式算法[4],[5]常常难以在解决方案质量和计算时间之间取得平衡。因此,迫切需要能够即时提供近乎最优调度决策的智能系统。
为了解决这些挑战,人们开始将机器学习,特别是深度强化学习(DRL),集成到调度系统中。与静态启发式方法不同,DRL方法通过与环境的交互来学习构建解决方案,具有更好的泛化能力和速度。这一趋势在JSSP领域尤其取得了显著成果[6],[7],[8],[9]。通常,这些方法将调度状态建模为析取图,利用图神经网络(GNN)来提取特征并顺序或迭代地构建解决方案[6],[8]。尽管在JSSP方面取得了进展,但由于机器灵活性的引入,基于学习的FJSP求解器的研究仍处于发展阶段。目前最先进的FJSP方法大多采用了JSSP中使用的基于图的范式。例如,Song等人[10]使用了异构图表示来捕捉操作-机器关系,而后续的工作如DAN[11]则结合了图注意力机制来增强特征提取。然而,过度依赖基于图的架构带来了结构和计算上的挑战。首先,构建和维护复杂的析取图涉及大量的计算成本。其次,标准的GNN甚至图注意力网络依赖于基于消息传递的机制,这些机制本质上关注局部邻域。这种局部化使得难以捕捉长距离依赖关系,例如调度决策对远端操作的连锁效应,除非堆叠许多层,否则会导致过度平滑和训练不稳定[12]。因此,一个自然的问题是:我们能否开发出一种神经架构,通过学习操作的完整序列(或机器)来改进性能,从而避免复杂的基于图的状态设计,并同时保持更快的解决速度?
在本文中,我们通过提出Mamba-CrossAttention(M-CA)这一基于Mamba架构[13]的新神经框架,给出了肯定的答案,以实现FJSP的高效和有效序列建模。通过将视角从图拓扑转移到序列建模,M-CA有效地绕过了GNN固有的邻域限制。它利用Mamba的线性时间选择性扫描来捕捉操作和机器之间的长距离依赖关系,从而显著加速了端到端的解决方案生成。此外,通过集成Mamba的状态空间公式,网络利用隐藏状态来记忆历史上下文。这种能力使模型能够超越单步特征提取,捕捉整个序列决策过程中的特征动态演变,有助于构建高质量的解决方案。具体来说,M-CA框架采用编码器-解码器架构。编码器包含一个双Mamba模块设计,分别提取操作特征(例如处理时间、优先级约束)和机器特征(例如工作负载、可用性)的潜在表示。这些并行分支确保了专门的特征学习,同时增强了它们各自序列的建模。随后,解码器使用轻量级的交叉注意力机制来融合这些表示,使网络能够共同推理机器分配和操作排序。此外,为了减轻序列模型对输入顺序的敏感性,我们提出了一种排列不变的策略优化(PiPO)算法。该算法鼓励模型对特征序列进行多样化扫描,从而学习出对顺序不敏感的鲁棒表示。
**总结**
我们的贡献如下:
• 我们将Mamba的应用范围扩展到了调度领域,这是其在制造组合优化中的首次应用,利用其线性复杂性和状态空间表示来克服基于图的方法的缺点。
• 我们提出了Mamba-CrossAttention网络,以实现FJSP的高质量端到端解决方案生成。它从操作的完整序列中学习操作和机器的交互表示,从而实现高效的序列建模和特征融合。
• 我们提出了排列不变的策略优化算法,鼓励模型完全扫描特征序列以学习排列不变的表示,进一步增强了序列建模。
• 我们通过广泛的实验表明,我们的方法可以为FJSP提供近乎最优的解决方案,在基于学习的方法中实现了新的最佳结果,并且具有快速的解决速度。
**相关工作**
灵活作业车间调度问题(FJSP)由于其复杂性和工业相关性而吸引了大量研究关注。现有的解决方法可以大致分为传统方法、基于图神经网络的方法和非图架构。本节回顾了这些范式,并明确了我们提出的框架的位置。
**Mamba网络**
Mamba[13]是一种基于选择性状态空间模型(SSM)的最新提出的序列建模架构,最初是为了解决基于注意力的模型在处理长序列时的效率限制而设计的。通过用线性时间选择性扫描机制替换二次复杂度的自注意力,Mamba实现了长距离依赖关系的可扩展建模,同时保持了强大的表示能力。
**当前研究**
当前的研究主要依赖于图卷积或图注意力机制作为学习FJSP中机器和操作嵌入的基本方法,这通常需要对问题进行专门的图结构配置。然而,这些基于图的方法不可避免地受到GNN固有限制的约束,例如由K跳消息传递引起的过度平滑问题和由复杂性导致的计算开销。
**基准测试**
在这项工作中,我们使用六个在先前工作中广泛使用的公共基准测试集[10],[11],[20]来评估我们的方法。它们分别是Barnes数据集[26]、Brandimarte数据集[1]、Dauzere数据集[27]和3组Hurink数据集[28]。对于合成数据,我们使用了[10]中的实例进行测试,涵盖了六个问题规模:10 × 5、20 × 5、15 × 10、20 × 10、30 × 10和40 × 10,每个规模包含100个实例。在这些数据中,每个操作Oij在机器pijk上的处理时间...
**结论**
在这项研究中,我们提出了一个基于Mamba的网络,用于FJSP的全面序列建模。与以在FJSP中表示学习效率低下而闻名的基于图注意力的框架不同,我们提出的模型展示了更高的效率和效果。同时,所提出的PiPO算法也显示出对FJSP序列建模的积极影响。实验结果表明,我们的方法优于现有的基于学习的最佳方法。
**作者贡献声明**
曹志:撰写 – 审查与编辑、撰写 – 原始草稿、可视化、验证、方法论、调查、形式分析、数据管理、概念化。
张聪:撰写 – 原始草稿、可视化、验证、软件、资源、方法论、形式分析、概念化。
吴耀欣:验证、监督、资源、项目管理、资金获取。
侯雅晴:监督、软件、资源、项目管理、资金获取。
**利益冲突声明**
作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。
**致谢**
本工作部分得到了大连科技创新基金(2025JJ12CG028)、辽宁重点研发计划(2025080041-JH2/1028)和中国中央高校基本研究基金(DUT25YG235)的支持。
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号