面向多智能体作业车间调度问题的基于组合竞价深度强化学习方法

《Expert Systems with Applications》：A combinatorial bidding based deep reinforcement learning approach for multi-agent job shop scheduling problem

　　

•提出一种基于组合竞标的深度强化学习框架。
•设计一种图注意力编码器，用于建模智能体特定的操作依赖关系。
•开发一种增强型指针解码器，用于生成组合操作包。
•实验表明，该框架能够生成高质量的解决方案。

引言
受消费者驱动制造趋势（Meng, Hu, Zhou, & Li, 2026）的启发，调度已从供应商主导的决策转变为消费者与生产提供商之间的协作过程。这一演变催生了多智能体作业车间调度问题（MJSSP），其中具有异构调度目标的多个消费者智能体（CAs）共享由作业车间智能体（JSA）管理的有限机器资源。智能体之间冲突的目标和资源竞争自然导致了分散式调度范式，这在原始设备制造（Ping, Liu, Zhang, Wang, & Xu, 2024）、边缘计算任务卸载（Fan, Ge, Zhang, Wu, & Luo, 2024）和高性能计算（Ray & Moulik, 2025）中具有广泛的应用。
为了解决多智能体调度问题，已经开发了各种分散式优化机制。基于拍卖和基于谈判的框架是最具代表性的范式。基于拍卖的方法将调度过程建模为市场，智能体对机器时间槽提交竞标，中央拍卖师通过定价或匹配规则确定分配（Fang, Zhang, Wang, Xie, Zhang, 2025, Liu, Sun, Shen, Wang, Wang, 2025, Liu, Sun, Shen, Wang, Wiktorsson, Wang, 2024）。基于拍卖的方法增强了自主性和可扩展性，但依赖于预定义的竞标和支付规则，这限制了它们在任务相互依赖或目标异构情况下的可行性。另一方面，基于谈判的方法允许智能体迭代交换报价以达成互接受的调度计划（Wang, Eunike, 2024, Zhang, Deng, Wen, Zhao, Gong, 2023）。此类模型可以捕捉智能体偏好的多样性；然而，多轮通信和收敛的需求导致在大规模调度中计算成本过高。在具有异构目标和资源约束特征的 MJSSP 中，上述机制可能表现出有限的泛化能力和可扩展性，使得在不同问题规模下的高效协调变得困难。
竞标机制为多智能体调度中的分散式决策提供了一个自然框架，使智能体能够通过迭代报价表达局部偏好，同时保持整体系统效率。通过引入深度强化学习（DRL），智能体可以自主学习有效的竞标策略，以实现自适应协调和高效资源分配（Lei, Hui, Chang, Dassari, Ding, 2023, Li, Liu, Li, Gao, 2025b）。遵循这一范式，开发了一种基于竞标的深度强化学习（BDRL）框架，以支持具有异构目标的多个 CA 之间的调度协调（Shen, Sun, & Liu, 2025）。
在 BDRL 中，每个 CA 都配备了一个智能选择器（IS）和一个智能竞标者（IB）。在每一轮竞标中，IS 确定一个待提交的候选操作，而 IB 根据学习到的策略确定其对应的投标价格。该框架有效地提高了协调效率和整体调度性能。由于每个 CA 在每轮竞标中仅提交一个操作，未能赢得机器资源将导致该轮分配机会的损失并延迟操作的开始。此外，这种单操作竞标机制将每个操作视为独立的，忽略了操作之间的优先关系和资源耦合。结果，智能体无法充分表达 CA 的异构偏好，导致资源利用率低和协调质量下降。
为了克服上述局限性，本研究为 MJSSP 引入了一种基于组合竞标的深度强化学习（CBDRL）框架。所提出的框架遵循集中训练与分散执行（CTDE）范式。集中调度信息在离线训练期间被纳入以支持策略学习，而在执行期间，每个 CA 和 JSA 根据其各自的观察结果以分散方式应用其学习到的策略。在 CBDRL 中，组合竞标使每个智能体能够在单轮内提交相互依赖的操作包，从而允许对调度偏好和操作依赖关系进行更具表现力的表示。开发了图表示学习和序列建模，以改善智能体之间的协调以及在不同调度实例上的泛化能力。本文的主要贡献如下：
•在 CTDE 范式下，为 MJSSP 提出了一种基于组合竞标的深度强化学习方法。学习到的策略支持分散执行，其中 CA 通过操作包表达相互依赖的调度偏好，JSA 执行竞标序列确定以在 CA 之间分配机器资源。
•开发了一种基于图注意力网络的编码器，用于捕捉未调度操作之间的相互依赖关系。它生成反映异构目标的智能体特定嵌入，指导解码器选择协调的操作包。
•设计了一种增强型指针解码器，用于在每轮竞标中生成组合操作序列。它基于增强查询嵌入自回归地构建序列，在生成过程中不更新调度环境。
本文其余部分组织如下。第 2 节回顾相关工作。第 3 节公式化 MJSSP。第 4 节提出所提出的 CBDRL 方法。第 5 节报告实验设置和结果。第 6 节得出结论并概述未来工作。

章节片段
组合竞标机制
组合竞标通过物品包实现偏好表达，并已被广泛应用于调度问题。Kutanoglu 和 Wu（Kutanoglu & David Wu, 1999）将作业车间调度重构为分散式拍卖，其中作业对机器 - 时间槽包进行竞标，赢家确定遵循拉格朗日松弛。Yan 等人（Yan, Wang, & Shi, 2025）对带有外包的非相关并行机调度进行了建模，其中第三方供应商对进行组合竞标

多智能体作业车间调度问题
考虑的 MJSSP 由 N 个 CA{CA1,CA2,…,CAi,…,CAN} 和一个 JSA 组成。每个 CAi 拥有 ni 个作业，表示为 Ji={J1i,J2i,…,Jji,…,Jnii}，其中 Jji 表示 CAi 的第 j 个作业。设 Oj,ki 表示作业 Jji 的第 k 个操作，加工时间为 pj,ki。Jji 的完工时间和交货期分别表示为 Cji 和 ddji。每个作业由一系列操作组成，这些操作必须在 JSA 管理的一组 m 台机器 M={M1,M2,…,Mm} 上进行处理。考虑的 MJSSP 遵循

所提出方法的框架
在所提出的框架中，CA 和 JSA 被建模为由 DRL 训练的智能智能体。在每一轮竞标中，每个 CA 通过向 JSA 提交操作包来进行组合竞标。在本研究中，组合竞标指的是操作包提交，而不是带有价格或支付的货币竞标。在接收到提交的操作包后，JSA 执行竞标序列确定以生成部分调度序列。具体而言，竞标序列确定

实验
在本节中，进行了大量实验以评估所提出的 CBDRL 方法的有效性和泛化能力。该方法与代表性的多目标进化算法和 DRL 方法进行了比较。在公开基准实例和大规模实例上进一步检验了泛化能力。最后，进行了两项消融实验，以评估各个组件对整体有效性的贡献。

结论
本研究在 CTDE 范式下为 MJSSP 提出了一种 CBDRL 框架。所提出的框架旨在生成同时考虑智能体私有目标和整体社会福利的调度计划。CBDRL 允许每个 CA 在单轮竞标中提交一组相互依赖的操作。这一设计使 CA 调度偏好的表示更具表现力，并提高了共享机器资源的分配效率。基于图注意力网络的编码器是

作者贡献声明
Gaopan Shen：概念构思、方法论、软件、数据、撰写 - 初稿。Shudong Sun：监督、概念构思、资源、撰写 - 审阅与编辑。Yaqiong Liu：可视化、软件、撰写 - 审阅与编辑。

利益冲突声明
作者声明他们没有已知的竞争性经济利益或个人关系，这些利益或关系可能被认为影响了本论文中报告的工作。

Gaopan Shen|Shudong Sun|Yaqiong Liu