基于滑动窗口的强化学习方法用于具有多产品交付的动态装配流水车间调度

# 基于滑动窗口的强化学习方法用于多产品交付的动态装配流水车间调度 来源：https://arxiv.org/html/2607.02941 邱俊豪，刘建军，刘婷，廖荣杰，李占涛，张庆福 本研究得到国家自然科学基金（批准号：52375489, 51975129）和广东省基础与应用基础研究基金（批准号：2024A1515011211）资助。（通讯作者：刘建军。） 邱俊豪与广东工业大学机电工程学院（广州，中国）及香港城市大学计算机科学系（香港）均有联系（电子邮箱：[email protected]）。 刘建军、刘婷、廖荣杰、李占涛均任职于广东工业大学机电工程学院（广州，中国）（电子邮箱：[email protected], [email protected], [email protected], [email protected]）。 张庆福任职于香港城市大学计算机科学系（香港）（电子邮箱：[email protected]）。 ###### 摘要 多产品成套交付给集成加工与装配的混合制造系统中的实时调度带来了重大挑战，因为动态订单到达会同时改变供应依赖关系和可行的作业-机器分配集合。本文提出了一种基于滑动窗口的强化学习（SWRL）框架，用于解决具有复杂成套约束的柔性装配流水车间调度问题中的端到端在线调度。该问题被建模为一个基于异构图马尔可夫决策过程，该过程捕获了双层成套结构以及产生稀疏奖励景观的尾产品瓶颈动态。为应对由此产生的挑战，SWRL集成了以下三个模块：一个滑动窗口过滤机制，用于过滤非活跃节点并优先处理成套关键工序；一个时空图编码网络，用于跟踪连续决策状态间的瓶颈转移；以及一个动态动作映射模块，该模块采用约束等待策略，以适应可变拓扑下不断变化的动作空间。在来自某家电制造商的真实实例上进行的实验表明，SWRL在减少延迟方面持续优于经典调度规则和现有深度强化学习方法，并且在不同的资源配置、订单负载和到达集中度下均表现出稳健的性能。 ## I. 引言 对基于场景的成套订单日益增长的需求，推动着集成加工与装配的混合制造系统向以客户为中心的生产模式转变[1, 2]。传统上，加工与装配阶段之间的协调依赖于库存缓冲区[3]，但动态订单到达使得这种静态缓冲区失效。在此类系统中，订单到达的不确定性会持续破坏计划好的调度方案并降低交付性能。因此，能够应对多阶段扰动并跟踪跨并行产品流的成套进度的在线调度方法，对于具有多产品交付的动态柔性装配流水车间调度问题（DFAFSP-MPD）至关重要。 柔性装配流水车间调度问题（FAFSP）是经典流水车间问题的NP难扩展，它包含了在柔性资源约束下的零部件成套装配[4]。该问题广泛应用于家电[5]和汽车[6]等行业。DFAFSP-MPD的难度源于其双层成套结构。在产品层面，装配成套要求所有零部件在最终装配前完成。在订单层面，多产品交付要求同一订单内的所有产品同时完成，因此订单交货期由其尾产品决定。在动态到达环境下，尾产品的身份会因序列依赖的换模时间和不同的加工速度而发生转移，从而产生难以预测的移动瓶颈。由此产生的决策空间需要在柔性加工资质条件下同时进行作业排序和机器分配，而延迟信号在各项动作中非常稀疏。 集中式静态方法，包括混合整数线性规划[7]和元启发式算法[8, 9]，提供了有效的前瞻优化，但在秒级或毫秒级的实时决策中计算上不可行[10]。近似方法[11]为中等规模实例提供了实用的折衷方案。鲁棒调度方法通过时间缓冲和情景分析嵌入扰动容忍能力[12]，而重调度方法在扰动发生后修复计划[13, 14]。然而，在高频或大规模扰动条件下（在线FAFSP环境的常见情况），这些方法的有效性会下降[15, 16]。这些局限性凸显了从系统交互中直接学习的自适应、数据驱动调度策略的必要性。 深度强化学习（DRL）因其自适应决策能力而被广泛用于动态调度[17, 18]。一种方法在每个决策步骤使用DRL选择优先调度规则（PDR），并将其表述为马尔可夫决策过程（MDP）[19, 20]。文献[21]将深度Q网络（DQN）应用于FJSP中的调度规则选择，而文献[15, 22]将其扩展到分布式FSP环境。文献[23]通过多目标DQN进一步改进了泛化能力。基于PDR的方法提供了有保证的性能下限，并可扩展到复杂车间[24, 25, 26, 27]，但其对固定规则集的依赖限制了可达到的性能。 另一种范式采用具有图表示的端到端DRL求解器，直接分配工序和资源[28, 29, 30]。文献[28]将图神经网络（GNN）与DRL相结合用于JSP，使用图表示进行状态编码，并使用近端策略优化进行调度决策。文献[31]应用异构图神经网络对FJSP状态进行建模，并取得了有竞争力的完工时间性能。文献[32]进一步将此方法扩展到动态作业到达场景。文献[10]提出了一个分层强化学习框架用于大规模动态FJSP，其中高层智能体管理作业释放，低层智能体负责工序排序。然而，这些端到端方法主要针对静态图结构[33]设计，并未解决DFAFSP-MPD特有的挑战，即由于装配成套约束[34]，图拓扑和动作空间会动态演化。 将现有端到端DRL方法应用于DFAFSP-MPD会引入三个技术挑战。 1. **双重成套约束下的状态表示。** 多产品交付通过一个最大（max）运算符耦合并行产品：每个订单的延迟仅取决于其尾产品。这产生了一个阶梯状的奖励表面，其中大多数作业-机器对不会立即引起延迟变化，阻碍了智能体识别瓶颈关键动作的能力[35]。同时，动态订单到达扩展了候选作业集，将瓶颈相关信号淹没在来自无关并行操作的噪声中。 2. **捕获动态环境中的时空相关性。** 尾产品瓶颈并非固定不变，而是随序列依赖换模时间和加工速度改变各产品的相对完成进度而转移。现有方法在每个决策步骤将调度状态编码为静态图，未能捕获连续状态之间的时间依赖性[10]，使得智能体难以预测后续的配套压力累积点。 3. **复杂约束下的稀疏奖励。** 双层成套结构创建了一个高度受限的动作空间，在任何给定步骤中，只有有限的一组作业-机器对能够减少订单延迟。大多数动作的即时奖励为零，且每个决策步骤仅推进一个作业[25]。由此产生的奖励信号既稀疏又延迟，为策略优化提供的梯度信息有限，且该问题随问题规模增大而加剧。 为应对这些挑战，本文提出了一种基于滑动窗口的强化学习（SWRL）框架。SWRL集成了三个相应组件：一个基于滑动窗口的过滤机制，用于过滤非活跃节点以减轻特征稀释；一个时空图编码网络，用于跟踪连续决策状态之间的瓶颈转移；以及一个具有约束等待策略的动态动作映射模块，以适应稀疏奖励条件下变化的动作空间。本研究的贡献总结如下： 1. 将DFAFSP-MPD形式化为一个混合整数线性规划模型和一个基于异构图的马尔可夫决策过程。该模型捕获了双重成套约束，包括装配层面的零件耦合和订单层面的产品同步，以及尾产品瓶颈动态（这产生了稀疏且不断变化的奖励景观）。 2. 提出了一种名为SWRL的基于滑动窗口的强化学习框架，用于在可变拓扑和动作空间下进行端到端在线调度。一个滑动窗口过滤机制随着图结构演化动态过滤非活跃作业节点并优先处理成套关键节点。通过一个时空图神经网络提取时间相关图状态中的节点特征以进行状态表示。随后采用一个具有约束等待策略的动态动作映射模块，以适应变化动作空间中的可行作业-机器对。 3. 在生成实例和真实实例上进行了全面实验，包括参数敏感性分析、消融实验、与最先进基于DRL的调度方法的比较评估，以及在不同问题规模和到达模式下的鲁棒性验证。SWRL在延迟最小化方面持续优于现有方法，同时所需训练回合数显著减少。消融实验进一步验证了每个设计组件对整体性能的贡献。 本文其余部分组织如下。第二节描述了FAFSP及其异构图建模。第三节介绍了SWRL框架。第四节展示了实验结果，第五节对本文进行总结。 ## II. FAFSP-MPD的问题表述 ### II-A 问题描述 DFAFSP-MPD源自某家电企业的真实装配与加工车间。这种加工-装配混合制造系统由Mp台无关加工机器和Ma条装配线组成。其问题描述如下： 1. **柔性加工能力：** 不同阶段的机器在执行相同作业时的资质和加工效率不同。在作业j1和不同产品的作业j2之间切换需要换模时间ST_{j1,j2}。 2. **装配成套约束：** 订单i的产品根据其结构被划分为相应的加工和装配作业j。所有支撑部件需在最终装配前完成，以确保供应的层次耦合约束。 3. **多产品交付：** 每个订单i有特定的交付时间DT_i，且至少包含一个产品。订单中的所有产品在交付前必须完全装配完成。 4. **订单动态到达：** 订单动态到达时，需要快速响应扰动并调整计划调度，协调加工和装配资源以减少多产品订单的延迟。 本文使用的符号总结如下： i：订单索引，i∈I p：产品索引，p∈P j：作业索引，j1,j2∈J m：机器索引，m∈M Q_{j,m}：若机器m有资格加工作业j则为1，否则为0 P_{j1,j2}：若作业j1是作业j2的直接前序则为1，否则为0 PT_{j,m}：作业j在机器m上的加工时间 A_{p,j}：若作业j是产品p的装配任务则为1，否则为0 O_{i,p}：若产品p属于订单i则为1，否则为0 DT_i：订单i的交货时间 AT_i：订单i的到达时间 ST_{j1,j2}：从作业j1切换到作业j2所需的换模时间 V：一个足够大的正常数 tt_i：订单i的延迟 ft_i：订单i的完成时间 ct_j：作业j的完成时间 st_j：作业j的加工开始时间 x_{j1,j2,m}：若作业j1在机器m上紧接着作业j2之后加工则为1，否则为0 目标是在满足以下假设和约束的情况下最小化总延迟。 1. 本研究不考虑运输。 2. 每台机器一次只能加工一个作业。 3. 一旦操作开始，不允许中断。 4. 一个作业只有在所有组件完全完成后才能进入装配阶段。 目标是最小化订单的总延迟，如公式(1)所定义。 min ∑_{i=1}^{I} (tt_i) (1) **尾产品订单延迟：** 订单i的延迟变化很大，最终延迟取决于最后一个产品的完成时间，ft_i = max_{∀p,j} (ct_j × A_{p,j} × O_{i,p})。