基于自适应果蝇优化算法的逻辑辅助弯曲分解方法，用于分布式并行预制流水线作业调度

《Swarm and Evolutionary Computation》：Adaptive fruit fly optimization-assisted logic-based benders decomposition for distributed parallel precast flowshop scheduling

　　**摘要**
本文研究了一个分布式预制流水线调度问题，旨在最小化异构工厂中交付时间和生产-运输成本的加权组合。这些工厂具有平行生产线和共享资源。对于小规模实例，我们构建了混合整数线性规划（MILP）和约束编程（CP）模型。对于较大规模的实例，我们开发了两种精确分解算法，这些算法利用了问题的层次结构。第一种算法是自适应果蝇优化辅助的基于逻辑的Benders分解算法（AL_LBBD_SSR），它通过三种关键策略改进了基于逻辑的Benders分解：自适应果蝇优化生成高质量的初始解、强下界以缩小搜索空间以及子问题松弛以加速收敛。第二种算法是分支定界法结合调度子问题松弛（BCH_SSR），它采用了一种强化了问题特定不等式和有效松弛的分支定界框架。在180个基准实例上的计算实验表明，这两种算法的性能显著优于直接的MILP和CP方法，平均最优性差距低于1%。AL_LBBD_SSR在订单数量超过80的大规模实例中表现优异，而BCH_SSR在订单数量最多为50的中等规模问题中更有效。这些结果突显了将受自然启发的元启发式方法与精确优化相结合解决复杂工业调度问题的潜力。

**引言**
预制建筑在效率、成本和可持续性方面相比传统的现场施工具有显著优势[1][2]，已被广泛应用于住宅、办公和公共建筑项目中。生产调度在这些系统中起着关键作用，直接影响生产线吞吐量、资源利用和交付时效[3]。受信息技术和日益增长的定制需求的推动，制造业正从集中式向分布式模式转变[4][5][6][7]，订单被分配到地理位置分散的工厂，每个工厂通常运行多条共享瓶颈设备（如混凝土浇筑机）的平行生产线[8]。在典型的预制过程中，养护可以并行进行，而其他阶段则需要专用资源。浇筑过程中跨生产线的共享设备竞争会产生强烈的调度依赖性。此外，在分布式环境中，从工厂到客户地点的运输（包括路线选择和时间）对交付性能和整体系统成本有显著影响[9]。在这种背景下，分布式预制生产调度问题可以被视为具有共享瓶颈资源和运输约束的分布式混合流水线调度问题的一个变种。尽管分布式和混合流水线调度问题已经得到了广泛研究，但在系统集成、建模真实性和解决方法方面仍存在几个重要的研究空白。

首先，从集成角度来看，大多数现有研究将生产调度和运输规划视为两个独立的决策过程[10][11]。尽管一些最近的研究试图整合这些决策[12]，但它们主要集中在批量交付政策上，而不是点对点运输决策。关于所谓“集成运输”的相关研究通常局限于工厂内部的物流，例如AGV调度[13]，因此没有涵盖工厂与客户之间的地理分布式运输阶段。此外，现有基于逻辑的Benders分解（LBBD）在分布式调度中的应用[14]通常不显式考虑共享资源约束，也没有在统一的优化框架内整合生产和运输成本。

其次，从建模角度来看，大多数研究将单个工厂视为独立实体，很大程度上忽略了现代制造系统中普遍存在的共享资源约束[8][15]。例如，在预制组件生产中，同一工厂内的多条平行生产线（通常为2到5条）必须共享关键的瓶颈资源（如浇筑机），这会在生产阶段产生强烈的耦合效应。尽管最近的研究开始关注分布式环境中的共享资源调度[16]，但现有模型主要关注工厂内部的生产调度，没有考虑已完成工作向地理位置分散的客户运输的问题。同时，关于阻塞约束的研究[17]主要关注缓冲容量限制，而不是对共享资源的主动竞争，而相关的理论工作[18]关注的是与分布式制造系统的离线规划环境截然不同的在线调度设置。

第三，从方法论角度来看，大多数现有研究依赖于启发式或元启发式方法，这些方法通常缺乏对解决方案质量的可证明保证[19]。尽管最近已经探索了LBBD等精确解决方法用于分布式调度问题[20]，但目前的方法并未充分利用启发式和精确算法的互补优势。特别是，快速启发式方法很少用于生成高质量的初始解以启动基于分解的精确框架，这限制了它们的实际效率。最近的一篇综述确认，即使在规模适中的实例中，精确方法“在合理的计算时间内也难以找到最优解”[21]。值得注意的是，即使是最新的Benders分解研究也继续关注排除共享资源约束的简化问题设置[22]。

这些局限性导致了三个关键的研究空白。空白1（集成）涉及缺乏综合考虑订单-工厂分配、生产调度、共享资源分配和运输规划的统一优化框架，同时明确捕捉成本和时间之间的权衡。空白2（建模）指的是缺乏能够表示分布式工厂网络中平行生产线之间共享瓶颈资源的集成模型。空白3（方法论）强调了缺乏能够为中等规模实例（例如30-80个订单）提供解决方案质量保证的精确或近似精确解决方法，尤其是能够有效整合启发式、元启发式和基于分解的优化技术的混合方法。

上述空白与最近的综述研究一致。Wang等人[23]强调了需要针对预制生产系统定制的分布式排列流水线调度模型，强调生产和运输决策的整合以及可持续性相关因素的考虑。然而，现有研究仍然未能同时捕捉到关键的实际特征，如异构工厂、共享瓶颈资源和协调的生产-运输决策。从更广泛的角度来看，Perez-Gonzalez和Framinan[6]指出了分布式排列流水线调度（DPFS）文献中的类似研究空白，特别是在异构生产环境和物流决策整合方面。受这些空白的启发，本文开发了一个具有共享资源和生产-运输成本的分布式异构并行预制流水线调度问题（DHPPFSP_SRPTC）。所提出的公式通过纳入异构工厂、多条平行生产线、共享瓶颈资源和点对点运输决策，扩展了经典的DPFS模型。这一公式弥合了理论模型和实际预制生产系统之间的差距。

在DHPPFSP_SRPTC中，需要共同做出三个关键决策：（1）订单到工厂-生产线的分配；（2）操作顺序和时间安排；（3）共享浇筑机的分配与直接交付。目标是最小化总成本和最大交付时间的加权和。我们在LBBD框架内开发了两种基于分解的精确算法——AL_LBBD_SSR和BCH_SSR，并通过自适应果蝇优化、结构化下界和子问题松弛来改进这些算法。我们构建了紧凑的MILP和CP模型，明确考虑了共享资源约束，从而能够高效解决中到大规模实例，并提供可证明的解决方案质量保证。本文的主要贡献总结如下：
- 我们首次提出了DHPPFSP_SRPTC，它整合了工厂的异构性、多条平行生产线、共享资源和直接交付。我们制定了严格的MILP和CP模型来解决小规模实例，并为基于分解的精确方法提供了基础。
- 我们开发了两种基于分解的精确方法。第一种方法AL_LBBD_SSR结合了自适应果蝇优化派生的上界、结构化下界和子问题松弛。第二种方法BCH_SSR采用了加强的有效主问题不等式和松弛的分支定界框架。这两种方法共同解决了LBBD中常见的弱界限和收敛缓慢的问题。
- 计算实验表明，AL_LBBD_SSR和BCH_SSR显著提高了解决方案质量和计算效率。具体来说，AL_LBBD_SSR在中等和大规模实例中表现出强大的鲁棒性，而BCH_SSR在小规模案例中实现了更高的效率。敏感性分析进一步确认了这两种算法在不同目标权重设置下的稳定性和可靠性。
- 所提出的LBBD框架通过启发式上界、加强的下界和SSR策略得到了改进，有效地利用了生产过程和共享资源结构，使其适用于其他分布式或混合流水线调度问题。

本文的其余部分组织如下：第2节回顾了相关的调度问题，重点介绍了PPSP和DHFSP，并讨论了LBBD的应用和局限性。第3节介绍了DHPPFSP_SRPTC问题并展示了MILP和CP模型。第4节描述了AL_LBBD_SSR和BCH_SSR框架及其相关的优化策略。第5节报告了计算结果，第6节总结了本文并概述了未来的研究方向。

**文献综述**
在本节中，我们首先回顾了与DHPPFSP_SRPTC密切相关的两个调度问题：预制生产调度问题（PPSP）（第2.1节）和分布式异构流水线调度问题（DHFSP）（第2.2节）。然后讨论了LBBD技术的最新进展及其应用（第2.3节），最后总结了我们的研究与现有文献之间的区别。

**问题描述和公式化**
在本节中，正式描述了DHPPFSP_SRPTC问题（3.1节）。随后，为DHPPFSP_SRPTC开发了一个基于Manne的MILP模型（3.2节）。最后，为同一问题提出了一个约束编程（CP）模型，提供了一种替代的解决方法（3.3节）。

**LBBD算法**
在本节中，我们首先分析了DHPPFSP_SRPTC的结构，并构建了一个基本的LBBD框架（4.1节）。接下来，为了提高计算效率，我们引入了一套增强策略，包括基于AFOA的初始上界、结构感知的初始下界以及将调度子问题的线性化松弛注入主问题的SSR加强（4.2节）。在这些组件的基础上，我们提出了两种改进的算法：AL_LBBD_SSR。

**计算实验**
所有模型和算法均在Julia 1.8.5环境中实现，结合了Gurobi 10.0.2和IBM ILOG CPLEX 12.10（包括CP Optimizer）进行求解。所有MILP模型使用Gurobi通过VS Code 1.92.2平台求解，所有CP模型通过PyCall包在同一平台上调用ILOG CP Optimizer进行求解。计算环境配置如下：Microsoft Windows 10操作系统、2.30 GHz Intel Core i5-8300H处理器和16 GB内存。

**结论和未来方向**
本研究解决了具有共享资源和生产-运输成本的分布式异构并行预制流水线调度问题（DHPPFSP_SRPTC），其中包含了关键的实际复杂性，如异构工厂、多条生产线、共享瓶颈资源和集成交付决策。我们开发了两种精确的数学公式：一种基于Manne编码的MILP模型，它在保持可行性的同时减少了变量和约束；另一种是CRediT模型。

**作者贡献声明**
Fuli Xiong：撰写——审阅与编辑、撰写——原始草稿、监督、软件、资源管理、项目管理、方法论、资金获取、概念化。
Muming Wu：撰写——原始草稿、可视化、验证、软件、形式分析、数据整理。
Kaihao Zhou：撰写——原始草稿、可视化、验证、软件、数据整理。

**利益冲突声明**
作者声明他们没有已知的财务利益或个人关系可能影响本文所述的工作。

**致谢**
作者感谢编辑和两位匿名审稿人对本研究的深刻评论和启发性建议。这项工作部分得到了绿色建筑国家重点实验室（项目编号LSZZ-Y202614）、国家自然科学基金（项目编号61473216）和陕西省自然科学基础研究计划（项目编号2023-JC-YB-582）的支持。