arXiv 2606.31737v2 · 发布 2026-06-30

基于多智能体深度强化学习与Petri网的柔性制造系统动态调度

Dynamic Scheduling for Flexible Manufacturing Systems Based on Multi-Agent Deep Reinforcement Learning and Petri Nets

AUTHORS Zhou He, Ning Li, Ruotian Liu, Liang Li, Carla Seatzu
EVIDENCE 基于多智能体深度强化学习的动态调度
SCORE 0.9
CATEGORIES TASK mas
GENERATED 2026-07-04 02:30:15 UTC

📝 TLDR

柔性制造系统在实际运行中常面临新订单到达、订单临时取消以及机器故障等动态扰动,传统调度方法难以保证实时响应。本文将调度问题建模为基于时间Petri网的马尔可夫决策过程,借助基可达图压缩状态空间以缓解状态爆炸,并设计融合逐步引导与终值评价的分层稠密奖励函数。在此基础上,采用集中训练、分散执行的多智能体近端策略优化算法求解调度策略。实验结果表明,所提方法能够有效应对典型动态事件,调度性能显著优于传统启发式方法。

🧭 速览

动机

柔性制造系统面临新订单、取消和机器故障等动态事件,传统方法实时响应能力不足。

方法

将调度建模为基于时间Petri网的MDP,利用基可达图压缩状态空间,设计分层稠密奖励函数,并采用多智能体PPO集中训练分散执行求解。

结果

实验表明所提方法能有效应对多种动态扰动,调度效率与性能均显著优于传统方法。

结论

该方法为柔性制造系统实时动态调度提供了一种基于Petri网与多智能体深度强化学习的高效可行方案。

📊 论文图表(共 11 张)

展开查看 11 张图

TL;DR

本文针对柔性制造系统(FMS)中订单动态变化与机器故障等扰动场景,提出将[[时间Petri网]]与[[多智能体深度强化学习]]相结合的动态调度方法。通过基可达图压缩状态空间缓解[[马尔可夫决策过程]]的状态爆炸问题,并设计融合距离引导、时间代价与终值评价的分层稠密奖励函数,采用集中训练分散执行的[[多智能体近端策略优化]]算法求解调度策略。实验表明,该方法在36个动态测试实例上显著优于传统启发式规则,在线决策时间低于0.5秒。

研究背景与动机

柔性制造系统作为工业4.0时代的核心生产范式,能够通过多条可选工艺路径同时处理多种零件,被广泛应用于航空航天、汽车制造等高端装备领域。这类系统本质上属于离散事件系统,具有动态性、并发性与资源共享等典型特征,其调度问题需要在工艺约束、资源约束与路径柔性约束下确定各工序的操作时序与资源分配。更为棘手的是,实际生产环境中新订单持续到达、已接收订单可能临时取消、关键设备随时可能发生故障,这些动态扰动使得原本就属于NP-hard组合优化问题的FMS调度面临状态空间指数级膨胀的挑战,传统调度方法难以在保证解质量的前提下实现实时响应。

现有方法在应对动态扰动时存在明显瓶颈。基于数学规划的精确方法虽能获得高质量解,但计算复杂度随问题规模呈指数增长,无法满足实时性要求;启发式规则如先到先服务、最短处理时间等计算简便却难以捕捉系统复杂动态特性,调度效果波动较大;近年来兴起的深度强化学习方法在组合优化领域展现出潜力,但直接将图像或序列作为输入的做法容易陷入维度灾难,训练收敛困难且泛化能力受限。如何在保证调度质量的同时实现对多种动态事件的快速响应,成为该领域亟待突破的关键问题。

本文的切入点在于将[[Petri网]]的结构化建模优势与多智能体深度强化学习的在线学习能力相融合。一方面,[[时间Petri网]]能够自然地表达FMS中的工艺流程、资源竞争与并发行为,其基可达图提供了一种紧凑而精确的状态空间表示;另一方面,多智能体架构与FMS多条产线并行的天然结构相契合,每条产线可由独立的智能体负责调度决策,而集中式训练机制允许智能体在训练阶段获取全局信息以协调资源竞争。

方法

方法设计的核心思路围绕三个关键问题展开:如何建立兼顾表达力与紧凑性的状态表示?如何设计有效引导策略学习的奖励信号?如何让多个智能体高效协作同时保持分散执行的实用性?

状态空间构建与压缩是方法的首要环节。研究将FMS建模为带时间的Place-Timed Petri Net(P-TdPN),其中库所集合划分为源库所、操作库所、终止库所与资源库所,操作库所被赋予确定性的处理时间。系统的关键特性在于:未来演化仅取决于当前标识与后续所执行的变迁,与历史轨迹无关,这为[[马尔可夫决策过程]]的建立提供了理论基础。然而,直接使用完整可达图会导致状态数量爆炸——文中Example 1显示,一个包含两条产线、四类资源的简单FMS,其完整可达图包含26个标识。

为此,研究引入基可达图(BRG)作为紧凑状态空间表示。其核心思想是通过基划分将变迁分为显式变迁与隐式变迁两类:隐式变迁构成的子网具有无环特性,任意显式变迁的执行效果可由其最小解释向量唯一确定。设当前基标识为 ,执行显式变迁 的效果为:

其中 为隐式变迁的关联矩阵, 为最小解释向量集合。采用基可达图后,同一示例的状态数从26个缩减至11个,显著缓解了状态爆炸问题,为后续强化学习训练的收敛奠定了基础。

状态与动作表示采用本地观测与全局状态相结合的设计。每条产线的智能体仅观测本地信息,包括当前子网的库所标识、基于最短路径估计的剩余处理时间、考虑加权资源时间的剩余负载,以及按资源容量归一化后的累计资源使用情况。集中式评论器额外接收联合状态用于价值估计。动作表示为基可达图事件 ,其中 选择显式变迁、 指定隐式变迁的解释向量。为避免在线重计算,研究预先离线构造complete minimal explanation set 作为每条产线的候选动作空间,并采用动作掩码机制确保只采样当前可行的动作。

分层稠密奖励函数的设计是方法的核心创新。考虑到纯终态奖励的稀疏性严重影响学习效率,研究构建了包含五个组件的分层奖励:

距离奖励 引导智能体朝向终态标识优化;时间代价惩罚基于动态空闲区间调度机制计算当前决策对最终makespan的影响,;步长惩罚 鼓励快速完成任务;冲突惩罚在联合动作不可行时施加负向激励;终值奖励在到达终态时给出makespan相关的正向反馈,否则给予固定惩罚。实验验证表明,这种分层设计能有效加速收敛——特别是步长惩罚对训练稳定性影响最大,终值奖励对最终解质量贡献最显著。

多智能体近端策略优化算法采用集中训练、分散执行的经典架构。每条产线对应一个Actor网络,采用3层全连接MLP(隐藏层128维),输出经掩码与Softmax归一化得到动作策略;所有产线共享一个集中式Critic网络,以联合状态为输入估计状态价值函数。训练采用PPO的截断目标与GAE优势估计,通过梯度裁剪保证训练稳定。算法流程包括:离线计算动作空间、初始化网络参数、每个episode重置至初始标识、循环执行交互采样与网络更新。

实验与结果

实验在两类基准测试集上开展:基于FMS01-FMS20构造的DFMS01-DFMS20,以及基于In01-In16构造的DIn01-DIn16,分别包含20个和16个动态测试实例。动态事件包括随机数量的新订单到达(1-5个)、服从指数分布的机器故障与修复时间、以及服从指数分布的订单取消事件。对比方法涵盖FIFO、SPT、LPT、GREEDY等经典启发式规则,以及基于完整可达图的RG-MAPPO消融变体。

实验结果揭示了几个重要发现。在DFMS01-DFMS20全部20个实例上,BRG-MAPPO均取得最小makespan,相比RG-MAPPO平均改进4.51%,相比SPT、FIFO、GREEDY、LPT分别改进8.14%、11.36%、10.52%、14.09%。在更大规模的DIn01-DIn16上,16个实例中有16个达到最优,平均改进幅度为9.43%。值得注意的是,RG-MAPPO在Example 1教学示例上makespan高达323,而BRG-MAPPO仅为287,这直观说明了基可达图压缩对策略质量的显著提升作用。

消融实验系统验证了各组件的贡献。步长惩罚移除后episode长度出现剧烈震荡,表明该组件对训练稳定性至关重要;终值奖励移除后makespan明显恶化,说明终态反馈对解质量具有决定性影响;距离奖励与时间代价惩罚主要加速收敛过程并提升解的质量上界;冲突惩罚则有效改善了早期训练阶段智能体的探索成功率。基划分敏感性分析表明,大多数基划分方案都能收敛至287或293的makespan,性能对具体划分选择具有较好的鲁棒性。

实时性方面,完成训练后系统在普通个人电脑(2.1 GHz CPU、16 GB RAM,未使用GPU)上实现单次在线决策时间低于0.5秒,验证了方法在工业场景下的实用潜力。

讨论与可借鉴点

从方法论角度,本文展示了如何将离散事件系统建模工具与深度强化学习相融合的范式。基可达图提供了一种在保持状态精确性的同时压缩搜索空间的思路,这对于将强化学习应用于状态空间庞大的实际工业系统具有重要启示。分层稠密奖励函数的设计哲学——将长期目标分解为短期的距离引导与时间代价评估——为解决强化学习中奖励稀疏问题提供了可迁移的框架。

方法的局限性同样值得关注。首先,基划分的选择目前依赖启发式准则,缺乏理论保证最优划分的定量刻画,这限制了方法的自动配置能力。其次,处理时间被设定为确定性值,而实际制造系统普遍存在加工时间波动,引入随机处理时间会使模型更贴近真实但会增加分析复杂度。再次,动态事件的扰动强度仅通过单一参数配置,未系统分析不同扰动强度下的鲁棒性。此外,消融实验仅在教学示例上完成,其结论在更大规模问题上的可推广性有待验证。

对于后续研究而言,将该框架扩展至随机处理时间场景、设计自适应的基划分策略、以及探索与其他先进DRL算法(如双网络架构、基于图神经网络的全局状态编码)的结合,都是值得关注的方向。总体而言,本文在将多智能体深度强化学习落地于复杂工业调度问题上迈出了扎实的步伐,其建模思路与实验范式对类似研究具有较高的参考价值。

摘要

本文针对柔性制造系统(FMS)在新订单到达、临时订单取消以及机器故障等动态事件下的动态调度问题展开研究。传统方法在此类条件下实现实时响应往往面临重大挑战。为解决这一问题,将调度问题建模为带时间Petri网的马尔可夫决策过程(MDP),其中系统的未来演化仅取决于当前标识及后续所执行的变迁,而与历史轨迹无关。利用Petri网基可达图(一种紧凑的状态空间表示)构建MDP的状态空间与动作空间,以缓解状态爆炸问题,从而加速模型训练的收敛。同时,通过将分步引导与终值评估相结合,构建一种分层稠密奖励函数。在此基础上,采用多智能体近端策略优化算法,在集中训练、分散执行的框架下进行模型训练,以提高调度效率。针对典型动态事件开展了数值实验,结果表明,所提方法能够有效处理动态事件,相较于传统方法具有更优的调度性能。

Abstract

This paper investigates dynamic scheduling for flexible manufacturing systems (FMSs) subject to dynamic events, such as new order arrivals, temporary order cancellations, and machine failures. Traditional methods often face significant challenges in achieving real-time responsiveness under such conditions. To address this issue, the scheduling problem is formulated as a Markov decision process (MDP) with timed Petri nets, where the future evolution of the system depends exclusively on the current marking and the subsequently executed transitions, independent of historical trajectories. The state space and action space of the MDP are constructed using the notion of basis reachability graph (a compact state space representation) of Petri nets to alleviate the state explosion problem, thereby accelerating model training convergence. Meanwhile, a hierarchical dense reward function is constructed by integrating stepwise guidance with terminal evaluation. Then, a multi-agent proximal policy optimization algorithm is employed for model training under the centralized training and decentralized execution paradigm to improve scheduling efficiency. Numerical experiments are conducted involving typical dynamic events, and the results demonstrate that the proposed method can effectively handle dynamic events and achieve superior scheduling performance compared with conventional approaches.


论文详细总结(自动生成)

论文总结:基于多智能体深度强化学习与 Petri 网的柔性制造系统动态调度

1. 核心问题与整体含义

  • 研究背景:随着工业 4.0 与智能制造的推进,柔性制造系统(FMS)因能通过多条可选工艺路径同时处理多种零件,被广泛用于航空航天、汽车制造等行业。FMS 是一类典型的离散事件系统,具有动态性、并发性与资源共享等特征。
  • 核心问题:调度任务需要在工艺先后约束、共享资源约束、路径柔性约束下,确定各工序的操作时序与资源分配,以优化 makespan 等指标。新订单到达、订单取消、机器故障等动态事件会导致状态空间指数级增长,使得 FMS 调度(NP-hard 组合优化)实时响应困难。
  • 整体含义:将 Petri 网的结构化建模优势与多智能体深度强化学习的在线学习能力相结合,构建一种可在线快速响应多种动态扰动、且能最小化 makespan 的 FMS 调度方法。

2. 方法论

2.1 总体框架

提出基于 Place-Timed Petri Net(P-TdPN)+ 基可达图(BRG)+ 多智能体 PPO(MAPPO) 的动态调度框架:

  • P-TdPN:将 FMS 拆分为 J 条生产线的子网 ,通过共享资源库所集成;形式化定义为 ,其中 赋予操作库所确定性的处理时间。
  • 动态事件建模
  • 新订单:在对应子网 的起始库所 中添加 token。
  • 订单取消:从 移除 token 并释放资源。
  • 机器故障:将对应资源库所 的 token 临时移除并延迟归还。

2.2 BRG 状态空间压缩

  • 基划分,其中 诱导的子网无环, 分别为显式、隐式变迁。
  • 基标识:显式变迁 与其最小解释向量 共同作用得到新基标识:
  • 关键效果:Example 1 中,原始可达图(RG)含 26 个标识,而 BRG 仅含 11 个基标识,显著缓解状态爆炸。
  • MDP 的 Markov 性质:命题 1 表明任意由显式+隐式变迁组成的执行序列可等价地由 BRG 路径表示,且未来演化仅取决于当前标识和后续所执行的变迁,与历史无关。

2.3 MDP 建模

#### 状态表示(每个 agent 仅用本地观测

其中:

  • 本地标识 :当前标识在子网 上的投影。
  • 剩余处理时间:利用从库所 到终止库所的最短路径处理时间
  • 剩余负载:借助加权资源时间矩阵
  • 累计资源使用:按资源容量归一化:
  • 联合状态(仅用于集中式 critic):

#### 动作表示

  • 动作:选择 BRG 事件
  • 动作空间离线构造:使用 complete minimal explanation set ,避免在线重计算:
  • 动作空间大小,含 1 个 null 动作(等待/避让)。
  • 动作掩码:对原始 logits 做掩码 ,经 Softmax 后得到策略分布,保证只采样可行动作。

#### 分层稠密奖励函数

其中:

  • 距离奖励:
  • 时间代价惩罚:,其中 由动态空闲区间调度机制计算 makespan
  • 步长惩罚:
  • 冲突惩罚:(联合动作不可行时施加)
  • 终值奖励:,否则

2.4 MAPPO 算法

  • 集中训练-分散执行(CTDE)架构:每条产线一个 actor ,共享一个集中式 critic
  • 策略网络:3 层全连接 MLP,隐藏层 128 维,激活函数 ReLU,输出层经 Mask+Softmax:
  • PPO 截断目标
  • 价值损失
  • 算法流程(Algorithm 1):离线计算 初始化 每个 episode 重置至 交互循环中:计算掩码 、采样动作 、执行复合事件、更新环境、收集轨迹、计算优势 与回报 、更新 critic、再依次更新各 actor(梯度裁剪稳定训练)。

3. 实验设计

  • 平台:Python 实现,2.1 GHz CPU、16 GB RAM 的个人电脑(未使用 GPU)。
  • 数据集/场景
  • 教学示例:Example 1——两条产线、四类资源(R1–R4)、两类工件 L1/L2、含替代路径的工业 FMS。
  • 动态基准:基于 [12] 的 FMS01–FMS20 与基于 [11] 的 In01–In16 静态实例,构造两类动态测试集:
  • DFMS01–DFMS20(共 20 组)
  • DIn01–DIn16(共 16 组)
  • 动态事件注入:随机整数 的新订单到达、指数分布的机器故障时间与修复时间、指数分布的订单取消(每次取消 1 个工件)。
  • 对比方法
  • 启发式规则:FIFO、SPT、LPT、GREEDY
  • 自身消融:RG-based MAPPO(不使用 BRG 压缩)
  • 不同基划分下的 BRG-based MAPPO
  • 评价指标:Makespan、平均总奖励、episode 长度、成功率。
  • 每个算法运行 20 次后取平均

4. 资源与算力

  • 文中明确说明:仅使用一台个人 PC,2.1 GHz 处理器 + 16 GB RAM,未使用 GPU
  • 训练配置:Adam 优化器,actor 与 critic 学习率分别为 ,截断参数 ,GAE 参数 ,每步惩罚 ,训练 10,000 episodes,每 50 episodes 记录一次指标。
  • 推理效率:在线决策时间 < 0.5 s
  • 未提供:训练总时长、CPU 核心数、内存峰值等更详细的资源占用信息。

5. 实验数量与充分性

  • 基划分敏感性实验:在 Example 1 上测试 8 种不同基划分(含 的纯 RG 情形)。
  • 奖励消融实验:分别移除距离奖励、时间代价惩罚、步长惩罚、终值奖励、冲突惩罚,共 5 组消融,对比 Full Reward,绘制平均 episode 长度、平均 makespan、成功率 3 张曲线。
  • 对比实验:在 DFMS01–20 与 DIn01–16 共 36 个动态实例上对比 6 种方法。
  • 统计方式:每种算法在每实例上 20 次独立运行取平均,且报告了 ±1 标准差区间。
  • 充分性评价:覆盖了基划分、奖励组成、benchmark 横向对比三大维度,样本量较为充分;但 ablation 只在 1 个教学示例上做,benchmark 缺乏多随机种子间的统计显著性检验(如 t 检验)。

6. 主要结论与发现

  • 方法有效性:所提 BRG-MAPPO 在 DFMS01–20 全部 20 个实例上取得最小 makespan,相较 RG-MAPPO、SPT、FIFO、GREEDY、LPT 平均改进分别为 4.51%、8.14%、11.36%、10.52%、14.09%
  • 可扩展性:在更大规模 DIn01–16 上 16/16 实例均最优,平均改进 9.43%
  • BRG 的关键作用:相比 RG,BRG 减少动作搜索空间、缓解资源冲突与死锁,使 agent 能更高效探索并学习更高质量策略;RG-based MAPPO 在 Example 1 上 makespan 高达 323,显著差于 BRG 的 287。
  • 基划分鲁棒性:大多数基划分取得 287 或 293 的 makespan,性能对具体划分不敏感; 越大,决策步数越少而 makespan 接近。
  • 奖励组成贡献:步长惩罚对训练稳定性最关键(移除后 episode 长度大幅震荡),终值奖励对 makespan 影响最大,距离奖励与时间代价惩罚主要提升收敛速度与解的质量,冲突惩罚改善早期成功率。
  • 实时性:训练完成后在线决策 < 0.5 s,可应对动态事件。

7. 优点

  • 建模层面:用 P-TdPN 把 FMS 拆为多产线子网,与多智能体结构天然对齐;BRG 提供紧致的状态空间表示,兼顾结构与行为特性。
  • 算法层面:使用 complete minimal explanation set 离线确定动作空间,避免在线重计算,并结合 action masking 保证动作可行性。
  • 奖励设计:分层稠密奖励(距离+时间+步长+冲突+终值)有效缓解奖励稀疏,加速收敛。
  • CTDE 架构:actor 只用本地观测即可执行,便于扩展和实际部署。
  • 实验对比:与 4 类经典调度规则 + RG-MAPPO 对比,且覆盖多种规模基准,体现方法普适性。
  • 工程友好:纯 CPU 即可训练,推理时延 < 0.5 s,对工业落地友好。

8. 不足与局限

  • 算力信息披露不足:仅给出 2.1 GHz CPU + 16 GB RAM,未报告 CPU 核心数、训练时长、内存峰值等,难以评估真实计算代价。
  • 基划分选择缺乏系统化理论:当前依靠 [34] 的启发式划分,没有定量刻画 BRG 规模与基划分间的精确关系,也未给出最优划分准则。
  • 动态事件建模简化:处理时间假设确定(),而真实制造系统常具有随机处理时间;机器故障与订单取消时间虽用指数分布建模,但实验设计未在多种扰动强度下系统分析。
  • 缺乏与先进元启发式/DRL 方法的对比:未与图卷积 DQN [27, 30]、dueling DQN [31]、A*/beam search [21] 等代表性 PN+DRL 方法在同等基准上做直接对比。
  • ablation 仅在单一教学示例上完成:奖励组件贡献的可推广性受限,且未对 BRG 中 大小做更细粒度的消融。
  • 统计显著性未充分检验:20 次平均只附 ±1 StdDev,未做显著性检验(如 Wilcoxon、t 检验)。
  • 可扩展性边界未给出:未测试 agent 数量极大、token 数极多或资源种类繁杂情形下的性能上限。
  • 依赖 PN 结构假设:弧权均为 0/1、 子网无环等约束,限制了对更复杂制造系统的直接适用性。

(完)

✨ 编译论文

点「✨ 编译」开始,LLM 会按 Polaris 风格翻译并把图片/表格嵌到对应位置。结果存到浏览器 localStorage,下次访问自动加载。

📓 我的笔记