混合柔性流水线中的资源依赖型工序时间：一种基于约束编程的分解方法

《European Journal of Operational Research》：Resource-dependent process times in hybrid flexible flowshops: A Constraint Programming-oriented decomposition approach

　　•受齿轮电机装配行业启发的混合柔性流水车间调度问题。•加工时间取决于所分配的工人数量。•基于逻辑的Benders分解方法，以处理复杂约束和与劳动力相关的加工时间。•利用问题特性以及将依赖资源的加工时间转化为可调整的调度方式来得到下界。•通过计算实验证明，在最多400个作业的基准实例中，优化差距很小。引言随着现实世界调度问题复杂性的增加，需要能够处理实际情况的可扩展解决方案，包括向以人为核心的生产布局发展的工业5.0趋势。在此背景下，基准问题被设计得更加贴近实际环境，通常还会考虑加工时间随分配工人数量的变化情况。流水车间调度问题（Johnson，1954）是指一组作业由多台机器依次处理的问题的研究。关于流水车间调度的研究在关注点和方法上都在不断发展（Gupta & Stafford，2006）。一个重要的扩展是混合柔性流水车间问题（HFFS）（Ruiz等人，2008），在这种问题中，每个生产阶段包含多台（通常是相同的）并行机器。HFFS与其他流水车间变体不同之处在于，它允许作业跳过某些阶段。为反映实际车间调度中的约束条件，一些研究引入了包含额外条件的HFFS模型，如与顺序相关的准备时间（Jabbarizadeh等人，2009）、同一阶段或不同工厂中机器之间的运输时间（Fernandez-Viagas，2025；Perez-Gonzalez & Framinan，2024），以及容量有限的缓冲区（Vatikiotis等人，2024）。通常，这类问题的研究目标是最小化总完成时间，即系统中所有操作的最大完成时间。然而，在实际的工厂中，加工时间取决于资源状况（Grigoriev等人，2007），也就是说，加工时间会因所分配的资源以及最常见的分配工人数量而变化。所使用的资源既影响模型约束条件（Behnamian & Ghomi，2011），也影响问题目标（Mokhtari等人，2011）。据我们所知，尽管文献中已经探讨了许多变体，但同时兼顾实际条件（如运输时间和容量有限缓冲区）以及依赖资源的加工时间的框架却很少被关注。实际上，我们在一个来自齿轮电机装配行业的案例研究中遇到了这样的条件，该行业面临着生产线中常见的现代挑战（Müllerklein等人，2022；Nourmohammadi等人，2022）。该工厂的车间包含多个不同的加工阶段，每个阶段对应不同类型的操作，并配有容量有限的输入和输出缓冲区。此外，每个阶段还配备不同数量的机器。在每个阶段，任何符合条件的作业都可以在不同数量的工人操作下进行处理，而这会影响其加工时间。作业在后续阶段的机器之间的传输则依靠大量（即不会造成限制的）自动引导车辆来完成。因此，出于研究空白和业务需求的考虑，我们的模型和方法考虑了机器间的运输时间、容量有限的缓冲区，以及随生产阶段和分配给作业的工人数量变化的加工时间。文献综述我们简要回顾了相关文献，有兴趣的读者可以在本文讨论的大多数论文中找到更详细的阐述。混合流水车间问题的标准建模方法（HFS）（Linn & Zhang，1999）考虑了一系列生产阶段，每个阶段包含多台（通常是相同的）机器。这种问题主要通过元启发式算法来解决（Choong等人，2011）。已经提出了多种算法，从典型的基于搜索的模型（Mirsanei等人，2011；Wang and Tang，2009）到基于种群的元启发式算法（Ruiz and Maroto，2006；Zheng等人，2024）。这类实现方法特别适合处理现实世界中的大型实例。随着更多符合实际情况的特征的加入，比如灵活性因素，选择精确方法就能简化额外约束的表达方式。Naderi等人（2014）提出了一组最先进的混合整数线性规划（MILP）模型，可用于处理最多12个作业和4个阶段的数据集。在另一个研究领域，Mollaei等人（2019）提出了一个具有资源约束的HFFS双目标MILP模型，而Jungwattanakit等人（2009）则提出了另一个包含总完成时间和延迟标准的双目标建模方法。Meng等人（2020）也对HFFS的典型MILP建模方法进行了扩展，以纳入现实世界中的各种条件。上述研究中所使用的测试环境表明，对于通常涉及大量作业的实际制造环境来说，MILP模型并不是最佳选择。这些情况需要使用约束编程（CP）模型，因为它们能更有效地处理现实世界的约束条件。I??k等人（2023）提出的CP模型在最多50个作业和4个阶段的实例中进行了测试，其在优化差距和计算时间方面都显著优于对比用的MILP模型。Mlekusch和Hartl（2025）展示了用于处理重新进入型HFS的CP实现方法，该方法可应用于小型（最多50个作业）和大型（最多100个作业）测试环境。Armstrong等人（2021）提出了一种最先进的CP模型，用于处理具有阶段间运输时间的HFFS问题，该模型可处理最多400个作业和8个生产阶段的实例；他们的研究成果对我们的技术贡献有着重要的启示作用。由于精确方法存在可扩展性方面的问题，近年来分解方法越来越受到重视。在简单的两阶段环境中，Tan和Terekhov（2018）提出了一种基于逻辑的Benders分解模型（LBBD），该模型将问题分解为一个MILP主问题以及基于CP的子问题。Jiang等人（2023）也将MILP-CP模型应用于更复杂的HFFS环境。Wallrath和Franke（2024）提出了一种用于流水车间调度问题的MILP建模方法，通过标准的Benders切割法迭代地纳入离散的模拟事件，该方法是在一家制药厂中应用的。Wang等人（2024）展示了将元启发式算法用于分解已建立问题的方法，他们采用人工蜂群算法通过不同的修改阶段来优化得到的解。Garraffa等人（2025）提出了一种新的分解方法，他们为具有运输时间的HFFS问题设计了两种不同类型的启发式方法，以应对不同类型的实例。随着研究重点转向包含可再生资源的情况（Jiang等人，2023），主要是指分配的工人（Gong等人，2020），根据新出现的约束条件调整HFFS框架就显得非常重要。一个具有挑战性的特点就是基于资源的加工时间（Behnamian and Ghomi，2011；Li等人，2024），这意味着完成作业处理所需的时间会受到制造系统中劳动力分配的影响。总之，表1总结了相关文献。Graham等人（1979）提出的标准符号被用来表示机器环境（α）和问题目标（γ）。“其他”目标指的是那些在相关调度问题中不常使用的特定于问题的指标，例如设备利用率、中断惩罚以及环境指标。贡献我们的工作是针对大规模且复杂的HFFS环境（即具有缓冲区、运输时间、资源有限以及依赖资源的加工时间）以及目前缺乏能够利用该问题在可再生约束条件下固有分解特性的方法而开展的。我们从模型、方法以及针对实际规模问题的计算实证三个方面做出了贡献。随着流水车间调度问题规模的扩大，即使作业数量相对较少，MILP模型也会变得效率低下。相比之下，CP模型能够有效处理优先级和资源约束问题。然而，它们无法计算出强有力的对偶下界，这限制了评估解决方案质量的能力。为了解决大规模数据集的问题，我们提出了一种完全由CP模型构成的LBBD算法，该算法既用于主问题也用于子问题，并通过逻辑Benders切割法将它们整合在一起。为弥补CP在产生强大下界方面的不足，我们开发了八种不同的对偶下界。这些下界不仅能够缩小解决方案空间内的搜索范围，还能通过减少优化差距显著提升解决方案质量的评估水平。其中一种领先的下界在将问题转化为支持广泛实际依赖资源加工时间函数的可调整调度简化模型后是合理的。大纲第2节详细介绍了具有依赖资源加工时间的HFFS问题，描述了问题本身以及本文中采用的数学符号。同时还概述了LBBD的理论框架以及我们的分解方法。第3节介绍了CP模型和LBBD分区的构建方法，以及所使用的下界和问题的可调整调度简化方法。第4节描述了实验工作，并介绍了用于评估方法性能的关键指标。文章最后是第5节的总结以及包含详细实验结果的附录。章节片段问题描述一组作业J必须经过一系列生产阶段S进行处理，每个阶段都配备有一组相同的机器M。每台机器都被分配到特定的阶段s，其中子集Ms?M表示阶段s中可用的机器。每个作业j∈J都可以跳过某些阶段；因此，子集Sj?S表示适合处理作业j的阶段序列。作业暂时存储在每个阶段的入口（Rm?）和出口（Rm+）处容量有限的在制品（WIP）缓冲区中。CP模型近几十年来，约束编程已成为建模复杂调度问题的主流方法。虽然MILP建模方法通常能更有效地生成紧密的下界，但其可扩展性较差。基于位置的建模方法（Pan & Ruiz，2014）通过在不需要依赖大M约束的情况下纳入阶段间的优先级约束，有时作为Benders分解方案的一部分（Bekta? & Ruiz，2020），在流水车间调度问题中实现了较小的优化差距。计算经验所有实验都在一台配备32颗AMD Ryzen Threadripper PRO 5955WX 16核处理器和32GB内存的服务器上运行，操作系统为Ubuntu 22.04.5 LTS。所有的数学模型（用于计算下界的线性规划问题和CP模型）都是使用CPLEX 22.1.1优化器来求解的。线性规划模型则是使用Pyomo 6.7.0编制的。对于所有的CP模型，我们使用了Python 3.10.12中的DOCplex模块。对于CP模型，设置了60分钟的时间限制。而对于LBBD算法，则设置了5分钟的时间限制。进一步的工作本研究通过考虑阶段和机器之间的灵活性，以及将缓冲区视为可再生资源来建模，从而对流水车间调度问题进行探讨。除了文献中已经研究的约束条件外，这里要解决的关键问题是加工时间取决于每项作业和每台机器所分配的工人数量这一情况。虽然CP模型能够解决规模较大的问题，但基于CP的LBBD算法表现出更优异的性能，能够产生较低且稳定的优化结果。CRediT作者贡献声明Ioannis Avgerinos：撰写——初稿、软件、方法论、概念构思。Ioannis Mourtos：撰写——审阅与编辑、撰写——初稿、监督、方法论。Dimitrios Papathanasiou：撰写——初稿、验证、软件、方法论、概念构思。Georgios Zois：撰写——审阅与编辑、撰写——初稿、监督、方法论。利益冲突声明作者声明他们没有已知的可能影响本文所述工作的财务利益或个人关系。致谢本研究得到了Horizon Europe的支持，属于MODAPTO研究与创新行动项目[资助编号101091996] https://modapto.eu/以及Tec4MaaSEs项目[资助编号101138517] https://tec4maases.eu/的支持。Ioannis Avgerinos|Ioannis Mourtos|Dimitrios Papathanasiou|Georgios Zois