《Swarm and Evolutionary Computation》：Serial distributed heterogeneous flowshop group scheduling with sequence-dependent setup times via adaptive rapid-evaluation memetic optimization
编辑推荐：
摘要串行双车间系统在多阶段制造中十分常见。印刷电路板组装（PCBA）就是一个典型的例子，其中表面贴装技术（SMT）车间和双列直插封装（DIP）车间按顺序排列。此类系统的调度十分困难，因为工件在分布式异构生产线上加工，且按照成组技术（GT）进行组织，同时受到顺序相关换型时间（S
摘要
串行双车间系统在多阶段制造中十分常见。印刷电路板组装（PCBA）就是一个典型的例子，其中表面贴装技术（SMT）车间和双列直插封装（DIP）车间按顺序排列。此类系统的调度十分困难，因为工件在分布式异构生产线上加工，且按照成组技术（GT）进行组织，同时受到顺序相关换型时间（SDST）的影响。此外，两个车间之间还需要进行精细协调。本文研究了带顺序相关换型时间的串行分布式异构流水车间成组调度问题（SDHFGSP-SDST）。目标是最小化完工时间（makespan）。首先构建了一个混合整数线性规划（MILP）模型，用于描述和求解小规模实例。针对大规模实例，提出了一种种群状态引导的自适应快速评估遗传算法（ARMA）。ARMA 采用面向问题的构造性初始化、精英档案库引导的重启策略，以及基于 Q 学习的算子概率调整方法。为降低评估成本，设计了一种双层快速评估方法，在串行双车间结构下同时在工作族和工件两个层面对候选移动进行评估。在基准实例上进行了计算实验。结果表明，MILP 模型能够求解小规模案例，而 ARMA 在大规模案例中能够以低得多的计算成本获得稳定且高质量的解。本文提出的方法为具有分布式异质性和基于工作族生产的串行多阶段调度提供了一种有效的解决途径。
引言
现代制造业越来越多地采用多阶段生产组织方式。产品通常会按照固定的顺序经过多个加工阶段[1]。这些阶段之间通过工艺流程、资源约束以及阶段间的协调要求进行连接。一种常见的形式是串行双车间系统[2]。在此类系统中，产品依次在两个车间中加工。两个车间在设备和加工能力方面通常存在差异。尽管每个车间都有自己的工艺特点，但它们通过运输、缓冲和工序优先关系相互联系。
印刷电路板组装（PCBA）制造是一种典型的串行双车间系统。PCBA 生产过程通常包括一个表面贴装技术（SMT）车间，其后接一个双列直插封装（DIP）车间[2,3]。在 SMT 车间中，电子元器件通过锡膏印刷、锡膏检测、元件贴装、回流焊接和自动光学检测（AOI）安装在电路板上。半成品板随后被转运至 DIP 车间。在该车间中，通孔元件被插入，并通过波峰焊接、AOI 和清洗进行处理。两个车间在设备类型、加工节奏和操作模式方面存在差异。因此，同时调度 SMT 和 DIP 车间比单独调度任何一个车间都要更加困难。PCBA 车间的布局如图 1 所示。
如图 1 所示，在每个车间内部，多条装配线并行排列，以提高吞吐量并缩短交付时间。这创造了一种分布式生产环境，不同的生产线可以同时处理不同的工件。然而在实践中，具有相同名义功能的产线并不完全相同。由于设备配置、升级、退化或维护等原因，它们在加工效率、产能和可靠性方面可能存在差异。因此，PCBA 生产具有异构分布特征[4]。简单的分配规则往往不足以平衡工作量并充分利用生产资源。另一个重要特征是工作族生产。成组技术（GT）被广泛用于减少因频繁换单造成的换型损失[5]。具有相似工艺路线或元件类型的工件被归入工作族，生产以工作族为单位组织。与逐件调度相比，基于工作族的调度可以减少换型频率，提高工艺连续性，并提高设备利用率。然而，当不同工作族连续加工时，仍然需要进行换型操作。这些换型时间取决于加工顺序。换言之，它们是顺序相关换型时间（SDST），由当前工作族和前序工作族共同决定[6]。不合理的族序安排可能会增加等待时间，延长生产周期，并使资源处于空闲状态。
在 PCBA 调度中，分布式异构产线、成组技术、顺序相关换型时间以及 SMT 与 DIP 车间之间的串行耦合需要同时加以考虑。现有研究通常仅涉及其中的一部分设置。关于分布式流水车间调度问题（DFSP）的研究主要关注分布式生产和产线分配，但很少同时考虑基于工作族的生产与顺序相关换型时间。分布式流水车间成组调度问题（DFGSP）的研究引入了族级调度，但大多局限于单车间系统。串行多车间协同调度问题（SMCSP）与 PCBA 的实际结构更为接近，但它们并未充分纳入基于工作族的生产与顺序相关换型时间。因此，现有研究未能充分捕捉异构产线、成组技术、顺序相关换型时间与串行双车间协调之间的耦合交互作用。这种组合设置引入了多个紧密耦合的决策。异构产线使得加工时间依赖于产线分配，因此产线选择既影响工作量分配，也影响实际加工时长。成组调度将族序决策与工件排序决策耦合在一起，而顺序相关换型时间则使得换型时间取决于相邻工作族的顺序。此外，串行双车间结构通过释放和转运关系将 SMT 与 DIP 车间的调度决策联系起来，使得上游的族序安排和完工时间能够影响下游的调度。因此，某一决策的变化会通过这些交互作用传播，从而影响其他决策的可行性和性能。因此，这种组合问题无法通过直接扩展传统的 DFSP、DFGSP 或 SMCSP 模型来充分解决，而需要专门的数学建模。
从算法角度来看，这种组合调度设置也带来了若干挑战。该问题的搜索空间庞大，涉及产线分配、族序安排和工件排序，而调度质量往往依赖于瓶颈产线周围的局部改进。遗传算法（MA）适合解决此类问题，因为它将基于种群的探索与基于邻域的精细化结合起来[7,8]。然而，如果没有针对问题特点的设计，常规遗传算法无法高效应用。随机或弱引导的初始化可能导致较差的初始调度，因为早期的工作族分配和车间间协调会强烈影响后续搜索。此外，候选移动可能会改变工作族换型、产线工作量和释放时间，导致重复的完整评估代价高昂。固定的算子概率也可能无法在不同的搜索阶段平衡探索与开发。而且，强耦合性可能导致搜索停滞在局部有潜力但全局不平衡的调度方案附近。
鉴于这一研究空白，本研究考虑了 PCBA 制造中的 SMT-DIP 系统。由于两个车间均包含多条并行生产线的流水车间逻辑，基本问题属于 DFSP。通过进一步考虑串行双车间结构、异构产线、成组技术和顺序相关换型时间，本文定义了带顺序相关换型时间的串行分布式异构流水车间成组调度问题（SDHFGSP-SDST）。目标是最小化完工时间。作为 DFSP 的扩展，SDHFGSP-SDST 是 NP 难问题。为解决该问题，首先开发了一个混合整数线性规划（MILP）模型，用于求解小规模实例。针对大规模实例，设计了一种种群状态引导的自适应快速评估遗传算法（ARMA）。本研究的主要贡献如下：
本文其余部分组织如下。第 2 节回顾了相关文献。第 3 节描述了 SDHFGSP-SDST 问题并给出了 MILP 模型。第 4 节介绍了 ARMA。第 5 节报告了计算实验。第 6 节对论文进行了总结并讨论了未来工作。
各节摘要
文献综述
本文所考虑的 SDHFGSP-SDST 与若干调度问题相关。该问题涉及分布式生产、成组调度以及两个串行车间之间的协调。因此，本节回顾了三个密切相关的领域：DFSP、DFGSP 和 SMCSP。
问题描述与数学模型
本节描述了 SDHFGSP-SDST 问题并给出了其 MILP 模型。研究考虑了一个包含两个车间的串行系统。该模型还可扩展至包含更多车间的系统。
针对 SDHFGSP-SDST 的算法
本节提出了用于求解 SDHFGSP-SDST 的 ARMA 算法。首先介绍了算法的动机和总体框架，然后详细描述了解表示、双层快速评估、初始化策略、进化算子、关键产线引导的局部搜索、精英档案库引导的重启策略以及基于 Q 学习的概率调整方法。
计算实验
本节给出了用于评估所提出的 MILP 模型、ARMA 及其主要组件的实例设置、参数标定和计算实验。
结论
< `div class="u-margin-s-bottom" id="para0143">本研究探讨了 PCBA 生产中的调度问题，其中 SMT 和 DIP 车间按顺序排列。工件在分布式异构生产线上加工，按工作族分组，并受顺序相关 `换型时间影响。两个车间之间还存在工序优先和转运关系。这些特征使该问题不同于传统的 DFSP 或单车间调度问题。基于此设置，本文研究了以最小化完工时间为目标的 SDHFGSP-SDST 问题。CRediT 作者贡献声明
韩震多（Zhenduo Han）：撰写——初稿，软件。卢超（Chao Lu）：撰写——审阅与编辑，概念化。张彪（Biao Zhang）：监督，调查。张国辉（Guohui Zhang）：监督，调查。李正锋（Zhengfeng Li）：形式化分析。
Zhenduo Han|Chao Lu|Biao Zhang|Guohui Zhang|Zhengfeng Li
