基于逻辑的Benders分解方法用于具有序列依赖性准备时间的增材制造调度

《European Journal of Operational Research》：Logic-based Benders decomposition for additive manufacturing scheduling with sequence-dependent setup times

　　•我们研究了在具有序列依赖性设置时间的无关并行机器上的增材制造调度问题。•开发并分析了三个混合整数规划模型。•引入了有效不等式、破缺对称性约束和解析界限以提高求解效率。•我们提出了一种基于逻辑的Benders分解算法来高效获得最优解。•计算结果证明了所有MIP模型的效率以及所提出的LBBD算法的有效性。

引言
增材制造（AM），通常称为3D打印，是一种革命性技术，可以创建复杂的几何形状和定制部件。与传统的减材制造不同，减材制造是通过去除材料来制造部件的，而AM则是从3D计算机辅助设计文件逐层构建部件的（Attaran, 2017），因此无需模具、夹具或切割工具。由于其在小规模生产中的灵活性以及显著的定制潜力，AM有望成为一种变革性技术，将对全球经济和供应链管理产生重大影响（Pérez-Pérez et al., 2018）。实际上，AM已经应用于多种领域，利用各种材料制造从医疗植入物到结构和航空航天工程设计的各种产品（Zastrow, 2020）。

AM带来了许多好处，例如能够按需提供定制产品并最小化材料浪费。尽管有这些优点，但在生产速度方面，AM通常仍落后于传统制造技术。最近的研究强调，优化AM机器上各种部件的调度可以显著提高处理效率并降低总体生产成本（Altekin & Bukchin, 2022; Pinto et al., 2024; Zipfel et al., 2024b）。特别是，一些研究指出，基于激光的金属粉末床熔融技术（通常称为直接金属激光烧结，DMLS）可以在一次构建过程中同时生产多个部件，从而显著缩短处理时间并降低成本。图1展示了DMLS过程，其中可以使用相同的材料在一次构建中生产多个部件。部件是逐层构建的：滚筒铺设粉末，激光熔化指定区域，然后降低构建平台以进行下一层。多余的粉末被收集起来进行回收，确保材料利用效率。DMLS还允许批次间的材料灵活性，因为同一台机器可以在不同批次中处理不同的材料（Zipfel et al., 2024b）。然而，工业DMLS中的材料更换通常成本较高且严重依赖顺序，因为需要清除粉末、清洁、重新校准以及加热/冷却，这些过程会消耗机器时间并减少可用生产时间。因此，从业者通常按合金或材料家族分组作业，并避免频繁更换材料，因此明确建模和优化AM调度中的序列依赖性设置时间至关重要。

在现代制造中，高混合度、低数量的生产往往需要制造由不同材料制成的部件。鉴于AM使用的合格金属粉末种类繁多，包括钢、铝合金、镍合金、钛合金和钴合金（Patel et al., 2024; Yap et al., 2015），为每种材料配备单独的机器往往不切实际，因为这涉及较高的资本密集度、有限的机器数量以及合金需求的巨大变化。虽然一些公司可能会为少数关键材料保留设备，但许多生产环境仍然依赖于在多种材料之间共享AM机器以提高利用率和响应能力。然而，在同一台机器上生产不同材料会引入不可忽视的切换工作量。更换粉末通常需要清除残留粉末并防止外来颗粒的带入，因为在同一台机器上连续处理不同材料时可能会发生交叉污染（Horn et al., 2020）。工艺腔室通常还会用惰性气体冲洗以建立所需的工艺气氛。这些程序的实施是为了控制交叉污染并确保工艺一致性，其范围可能取决于材料的组合（例如，污染容忍度、兼容性和安全协议的差异）。因此，材料更换时间更适合建模为序列依赖性的，而不是零或恒定的。本研究专注于DMLS工艺，并开发了一个调度框架，用于在无关并行机器上分配和排序具有不同材料的部件订单，同时明确考虑由材料更换引起的序列依赖性设置时间。

在这项工作中，我们解决了一个AM调度问题，该问题涉及使用DMLS技术在无关并行机器上生产不同材料的部件，并且设置时间具有序列依赖性。这些机器的构建容量有限，目标是最小化总制造时间。问题包括如何有效地将部件分组到批次中，将这些批次分配到AM机器上，并在每台机器上对它们进行排序。具体来说，每个批次的处理时间被建模为分配部件的总体积和批次内最大高度的线性组合，每个分量都乘以机器和材料依赖的系数。由于材料更换过程增加了问题的复杂性，我们的模型考虑了序列依赖性设置时间的影响，确保材料处理顺序得到优化，以减少总体生产时间。为了简化问题，我们将这个问题称为在具有不同材料和序列依赖性设置时间的无关机器上的AM调度问题，简称为AMSRM-S问题。

如Kucukkoc（2019）所示，即使没有不同的材料和序列依赖性设置时间，AM中的相应无关机器调度问题也已经是最难的NP问题，因此AMSRM-S问题也是NP难的。以往的研究通常依赖元启发式算法来解决相关问题（Hu et al., 2022; Rohaninejad et al., 2022; Ying et al., 2022）。虽然这些算法在实际应用中表现良好，但它们具有固有的局限性：它们不能保证全局最优性，并且通常提供的理论保证比精确方法要弱。为了克服这些缺点，我们提出了一种精确算法来获得可证明的最优解。这种精确算法不仅为AMSRM-S问题提供最优解，还依赖于成熟的数学模型和严格的优化技术，从而提供了更强的理论支持，增强了解决方案的可解释性和适用性。

在这项工作中，我们的主要目标是为AMSRM-S问题开发数学公式和精确算法。首先，我们制定了三个MIP模型，这些模型捕捉了在序列依赖性设置时间下部件分组和分配、批次材料确定以及批次排序的联合决策。与现有的AM调度公式不同，所提出的模型明确考虑了多种材料对批次可行性、处理时间计算和连续批次之间设置时间的影响。其次，我们开发了针对多材料环境的模型改进技术。具体来说，我们推导出批次数量的解析上界和总制造时间的下界，并引入了有效不等式和破缺对称性约束来增强公式。这些改进扩展了Altekin和Bukchin（2022）的公式改进思想，纳入了材料兼容性、机器依赖的构建容量和材料依赖的处理特性。第三，我们提出了一种针对AMSRM-S问题结构的精确LBBD算法。主问题确定部件分组和分配，而子问题优化机器级别的批次顺序。根据主问题的决策，每个子问题被重新表述为非对称旅行商问题（ATSP），并使用Dantzig-Fulkerson-Johnson（DFJ）公式和动态生成的子 tour 消除约束来解决。我们进一步结合了两种类型的优化Benders割和局部搜索启发式方法来提高计算效率。最后，我们进行了计算实验来评估所提出的公式、模型改进和LBBD算法。还进行了敏感性分析，以研究序列依赖性设置时间的影响。

本文的其余部分组织如下。第2节回顾了AM机器调度问题和LBBD算法。第3节描述了AMSRM-S问题及其三个相关的MIP公式，并介绍了对模型的几种改进。第4节详细介绍了所提出的LBBD方法。第5节展示了计算实验和结果，第6节以对未来研究的建议结束本文。

文献综述
由于我们的工作重点是使用LBBD算法解决AMSRM-S问题，我们的文献综述主要围绕解决AM调度问题的研究论文以及探索LBBD算法应用的研究论文展开。

问题描述和公式化
我们首先正式定义了在无关并行机器上的AMSRM-S问题，并提出了三种针对该问题的公式。然后，我们引入了几种有效不等式来加强这些公式，接着采用了多种边界技术来进一步提高它们。

基于逻辑的Benders分解算法
为了利用AMSRM-S问题的结构特性，我们提出了一种在分支检查框架下实现的LBBD算法。原始问题被分解为一个MP（混合整数规划）和一组特定于机器的SP（简单规划）。MP同时确定部件到批次的分配和机器的分配，而SP根据MP获得的分配结果优化每个机器上的批次排序。解决过程是迭代进行的。在每次迭代中，MP首先确定...

计算实验
在本节中，我们进行了一组全面的计算实验。我们展示了所提出模型和LBBD算法的性能，并进行了敏感性分析。所有模型和提出的算法都是使用Python 3.13实现的，优化器使用的是Gurobi 11.0.3。代码在配备两个虚拟CPU的服务器上执行，该服务器运行在Intel Xeon Gold 5218上，基本频率为2.30 GHz。机器配置有64 GB的RAM。

结论
本文解决了在无关机器、多种材料和序列依赖性设置时间下的AM调度问题，目标是最小化总制造时间。我们使用三个MIP模型对这个问题进行了公式化，并引入了模型改进，包括有效不等式、破缺对称性约束和解析界限来减小问题的规模。由于所研究问题的NP难度，我们在分支检查框架内实现了LBBD算法。

数据可用性
为了提高透明度和可重复性，本文中的所有基准实例都已在以下地址公开提供：https://github.com/OurGroupNUAA/AMSRM-S。对于每个实例，如果能够达到最优解，我们会报告最优目标值；如果在时间限制内未达到最优解，则提供已知的最优目标值。

资助
这项研究得到了中国国家自然科学基金（72571139, 72501141）的支持。

伦理批准
本文不包含任何由作者进行的涉及人类参与者或动物的研究。

未引用的参考文献
Chandra Sugianto和Soo Kim, 2024

作者贡献声明
Ma Wenjing：撰写——原始草稿、软件、方法论。
Chen Jian：撰写——审阅与编辑、监督、资金获取、概念化。
Sang Yaowen：可视化、调查、数据管理。
Zhang Yingqian：撰写——审阅与编辑、验证。
Wu Yaoxin：撰写——审阅与编辑、验证。