具有作业同时到达和机器故障的动态分布式生产调度问题：迭代贪婪算法的学习方法

《Swarm and Evolutionary Computation》：Dynamic distributed production scheduling problem with simultaneous job arrivals and machine breakdowns: Learning to learn iterated greedy algorithm

动态分布式混合流车间调度问题中同时考虑动态任务到达和机器故障，提出基于LSTM和PPO的学习型迭代贪婪算法（LIG），通过端到端训练实现算法自适应调整，实验证明其在多规模动态场景下具有更优的收敛速度、解质量、稳定性和泛化能力。

　　

周青|邵伟石|邵忠石|皮德昌|高家权

南京师范大学计算机与电子信息学院/人工智能学院，中国南京

摘要

由于环境复杂性和需要应对实时中断，动态分布式生产调度对现代制造系统提出了重大挑战。本文研究了同时存在动态任务到达和机器故障的动态分布式混合流水线问题（DDHFSP），旨在最小化总加工时间。为了解决这个问题，在经典的IG框架内提出了一种可学习的迭代贪婪算法（LIG）。LIG通过从搜索轨迹中提取知识来学习如何自适应地配置其操作组件，从而有效处理动态调度环境。基于IG结构，设计了四种动态事件的重新调度策略、四种破坏-重建策略和四种局部搜索策略。该算法采用长短期记忆（LSTM）网络提取时间相关的生产特征，并采用近端策略优化（PPO）构建一个代理，该代理根据当前状态在IG框架内自适应地选择最有前途的策略组合进行执行。实验结果表明，LIG在各种问题规模和动态场景下均优于几种先进的元启发式和基于强化学习的方法，表现出更快的收敛速度、更好的解决方案质量、更高的稳定性和更强的泛化能力。最终，所提出的可学习机制为处理DDHFSP中的动态干扰建立了一个新的范式。

引言

日益加深的全球化和不断变化的消费者需求使企业面临更高的市场波动性和生产系统的内在干扰。传统的生产计划方法越来越无法适应这些动态条件。因此，企业必须实施实时生产计划调整，以满足不断变化的市场需求并最大化经济效率。这种必要性在各种工业场景中都有体现。在汽车制造中，混合模型装配线需要动态重新调度以应对意外的材料短缺或机器人单元故障。同样，电子装配线必须实时重新分配任务，以应对组件缺陷或机器停机。港口码头操作需要在潮汐条件、泊位可用性和服务优先级波动的情况下进行动态调度。此外，航空航天制造综合体必须在适应紧急订单插入和机器维护延迟的同时协调多工厂生产。纺织生产链需要在频繁的订单变化和资源限制下，在分布式编织、染色和整理阶段进行自适应调度。为了应对这些挑战，动态调度已成为一个关键的研究焦点。这导致了针对各种复杂调度问题的广泛研究，包括排列流水线问题[1]、灵活作业车间问题[2]、混合流水线问题[3]（HFSP）、分布式作业车间问题[4]和分布式混合流水线问题[5]（DHFSP）。与传统的静态调度相比，动态调度需要通过定义的重新调度策略来应对生产环境中的不可预见的中断。与动态事件相关的固有不确定性为开发有效的解决方案带来了重大挑战。

随着社会劳动分工的日益专业化，越来越多的公司在不同地点建立工厂，以确保劳动力、技术和原材料能够满足生产需求，从而产生了分布式生产调度问题。尽管近年来在分布式生产调度方面进行了大量研究，但在涉及多个同时发生的动态因素的动态调度方面仍存在重大差距，这些因素受到的关注更少。因此，本文重点关注DHFSP中的两种动态因素：新任务的到达和意外的机器故障。新任务的到达是指在制造系统运行过程中随机引入的计划外生产任务。意外的机器故障表示突然的设备故障，会中断生产的连续性。这种中断会使预先优化的计划失效，需要在容量受限的情况下快速重新调整任务分配和时间线。DHFSP涉及多个工厂，每个工厂都包含一个HFSP，每个任务必须依次通过几个阶段进行处理。由于HFSP已被证明是一个NP难问题[6]，分布式动态混合流水线问题（DDHFSP）在两个关键方面增加了复杂性：跨工厂的分布式任务分配以及处理随机动态事件（如任务到达和机器故障）的需求。

尽管已经提出了一些动态调度方法来应对这些挑战，但它们仍然面临重大限制。大多数现有方法无法有效提取和利用动态环境中嵌入的特征信息，特别是时间模式和状态演变特征。这种缺陷从根本上限制了它们从历史调度经验中学习并积累战略知识的能力，最终限制了它们在分布式动态调度问题中的适应性和性能。为了克服这些限制，本研究提出了一种基于迭代贪婪（IG）框架的可学习迭代贪婪（LIG）算法。该算法使用长短期记忆（LSTM）网络从动态生产环境中提取时间相关特征。然后将这些特征输入到多层感知器（MLP）中进行决策，以输出特定的组合策略，这些策略在IG框架内执行。整个系统（包括LSTM和MLP）使用近端策略优化（PPO）进行端到端训练，使得迭代算法能够自我学习。

本文的贡献总结如下：首先，我们研究了同时存在动态任务到达和机器故障的DDHFSP，并开发了一个混合整数线性规划（MILP）模型，目标是最小化总加工时间。其次，基于IG框架，我们设计了重新调度策略、重建策略和局部搜索策略来处理动态事件，提高了算法对变化环境的响应能力。第三，通过集成LSTM进行特征提取、MLP进行决策和PPO进行训练，我们提出了一种具有自学习能力的LIG方法。第四，通过全面的实验，我们验证了每个提出组件的有效性，并将LIG与几种先进的基于强化学习和元启发式方法进行了比较，证明了其在解决方案质量和计算效率方面的优越性。

本文的其余部分结构如下。第2节回顾相关文献。第3节介绍了DDHFSP的数学表述。第4节描述了DDHFSP的IG框架，包括其核心组件和具体策略。第5节详细阐述了所提出的LIG，介绍了其学习机制和实现方式。第6节讨论了实验设置和结果分析。第7节总结了本文并提出了未来研究的有希望的方向。

节选

文献综述

在过去十年中，由于DDHFSP在现代制造业中的重要实用价值，它吸引了大量的学术兴趣。Ying和Lin[7]首次应用自调优IG算法来解决这个问题，为后续研究奠定了基础。Wang和Wang[8]开发了一种双种群合作遗传算法，通过双种群合作和局部强化来最小化总加工时间。Shao等人[9]提出了

问题定义

如图1所示，DDHFSP定义如下。F个工厂处理n个动态到达的任务。每个任务必须依次通过k个阶段。在工厂f的第s阶段，有$M_{fs}$$M_f>1$台相同的并行机器，至少有一个阶段满足在某些工厂。也就是说，每个工厂都包含一个混合流水线调度问题。运输时间和准备时间被忽略。其他假设如下。所有机器在时间0时都可用

DDHFSP的迭代贪婪框架

通用IG算法的程序如算法1所示，包括初始化、破坏-重建、局部搜索和接受标准。本节介绍了DDHFSP的IG的主要组成部分。它保留了标准IG算法的基本阶段，如解决方案表示、初始化、破坏-重建、局部搜索、接受标准，并进一步集成了一个重新调度阶段以应对动态中断。对于这些

可学习的迭代贪婪算法

本节介绍了一种为DDHFSP设计的LIG算法，该算法通过结合一个学习机制来增强IG框架。所提出的方法通过一个新颖的学习模块来捕捉不断演变的生产模式，该模块通过分析连续动态事件之间的调度解决方案来提取时间相关的生产特征。然后，MLP处理这些特征以选择行动。整个学习系统通过PPO进行训练

实验设置

为了全面评估所提出的DDHFSP方法，我们生成了多个不同规模的模拟实例，包括一个训练集和一个测试集。定义这些实例问题结构的关键参数在表5中总结。对于时间相关设置，任务处理时间$p_j从区间[1,\; 50]中均匀采样。机器故障是随机发生的，要求同一台机器上两次连续故障之间的间隔$

结论和未来工作

本研究研究了同时存在动态任务到达和机器故障的DDHFSP。进行了系统的消融实验，以剖析LIG算法中每个核心组件的具体作用。在各种规模和动态复杂性的测试场景中，完整的LIG算法始终实现了最佳或接近最佳的平均性能。最重要的是，在绝大多数情况下，其方差保持最低。

CRediT作者贡献声明

周青：撰写——原始草稿、软件、方法论、数据整理、概念化。邵伟石：撰写——原始草稿、方法论、资金获取。邵忠石：撰写——审阅与编辑、监督、资金获取。皮德昌：撰写——审阅与编辑、监督、方法论。高家权：撰写——审阅与编辑、监督。