用于生产排序和设置时间最小化的元启发式算法比较分析

《Computers & Industrial Engineering》：A comparative analysis of metaheuristic algorithms for production sequencing and setup time minimization

　　

**摘要**

提高生产效率并减少非增值换模时间是具有竞争力的制造系统中的关键目标。本研究利用真实工业生产数据，解决了轮胎制造线中瓶颈设备的顺序相关换模时间最小化问题。该问题与非对称旅行商问题密切相关，被建模为开放旅行商问题或非对称哈密顿路径变体，因为每种产品必须恰好加工一次，且所选顺序形成路径而非闭合回路。本文实现并比较了三种元启发式算法——模拟退火（SA）、粒子群优化（PSO）和禁忌搜索（TS）——与公司现有供应链部门（SCD）的排产顺序。同时开发了一个带子回路消除约束的混合整数线性规划（MILP）模型，并在LINGO 21.0.37中在实践停止准则下进行求解。实验设计包含十六个每日生产实例：十个真实工业生产日和六个从同一产品池、工厂环境、换模结构和运行假设生成的假设性实例。蚁群优化（ACO）和Lin–Kernighan启发式（LKH）仅作为文献参考基准，用于前十个真实生产日。在全部十六天的内部比较中，相对于SCD顺序，SA、PSO和TS分别将平均换模时间减少了13.71%、13.48%和11.29%，而MILP-20（MILP设置2）实现了16.70%的减少。非参数统计检验证实，所有基于优化的方法均显著优于当前的SCD顺序。结果表明，瓶颈设备上的换模时间优化可以提高有效产能、减少非增值生产时间，并为顺序相关生产环境提供一个可迁移的决策支持框架。

**引言**

在高度竞争的制造环境中，提高生产效率和减少非增值时间对于维持运营绩效至关重要。在直接影响生产效率的因素中，由产品切换引起的换模时间起着特别重要的作用。过长的或规划不良的换模操作可能会降低设备的有效产能、增加空闲时间、形成瓶颈、扰乱交货进度并产生额外的运营成本。这些效应在具有高产品多样性和顺序相关切换需求的制造系统中尤为关键。顺序相关换模时间常见于作业的换模需求取决于前一作业的情况；在生产计划中明确考虑此类关系可以减少换模相关的浪费、提高生产力，并支持更高效地利用制造资源（Lin和Ying，2022）。类似地，Toksar?和To?a（2022）表明，由材料切换引起的换模时间可以成为生产调度中的关键参数，特别是在不同材料必须在同一设备上加工时。

瓶颈资源在制造系统中也起着核心作用，因为整个系统的产能和运营绩效在很大程度上受瓶颈设备的产能和利用率影响。因此，提高瓶颈设备绩效是重要的生产管理目标（Si等，2024）。在调度研究中，瓶颈信息也被用于指导优化过程，特别是在车间调度和转移瓶颈方法中，通过识别和优先处理瓶颈设备来改进调度质量（Waubert de Puiseau等，2023）。

轮胎制造是此类生产环境的代表性例子。在轮胎生产线中，连续产品之间的换模时间主要由技术过渡特性决定，特别是模具和胶料的变化。具有相同模具和胶料的产品可能只需要非常短的换模时间，而涉及不同模具和胶料的过渡则可能导致显著更长的换模时间。因此，产品的加工顺序直接影响总换模时间、瓶颈设备利用率和每日生产效率。这使得生产排序成为轮胎制造商的一个具有实际重要性的决策问题。

本研究解决了一个真实的工业生产排序问题，针对轮胎制造线中的瓶颈设备。目标是通过确定适当的每日产品顺序来最小化总顺序相关换模时间。从结构上看，该问题与非对称旅行商问题密切相关，可视为开放旅行商问题或非对称哈密顿路径变体，因为每种产品必须恰好加工一次，且所选顺序形成路径而非闭合回路。因此，所解决的生产排序问题可以在旅行商问题相关的图优化问题的大家族框架内加以解读。Saller等（2025）强调，许多旅行商问题的变体可以在具有有向或无向边的图上构建，其中有向边允许非对称转换成本，而哈密顿回路和哈密顿路径之间的区别取决于路径是闭合还是开放的。类似地，Guettala等（2026）指出，非对称旅行商问题（ATSP）因其方向相关的成本结构而特别具有挑战性，这与本研究中使用的有向模具-胶料换模时间矩阵一致。

随着产品数量的增加，可能的顺序数量呈阶乘增长，这使得精确优化方法在计算上具有挑战性，特别是在真实工业规划条件下。因此，元启发式算法被广泛用于复杂的调度和排序问题，因为它们能在精确优化对大规模组合实例变得不切实际时，在合理的计算时间内提供高质量解。Hajariwala等（2025）强调，模拟退火（SA）、禁忌搜索（TS）、粒子群优化（PSO）、遗传算法（GA）和蚁群优化（ACO）等方法常被应用于车间调度问题，因为它们能够在解质量和计算量之间取得平衡。类似地，Khraibet等（2025）表明，元启发式和混合方法可以有效地解决复杂的单机调度问题，特别是在多目标或大规模问题使得传统精确方法难以应用时。

尽管元启发式算法已被广泛应用于调度、路径和排序问题，但仍存在若干研究空白。首先，许多现有研究依赖基准数据集或简化的问题设置，而非详细的真实工业过渡结构。其次，换模时间通常被视为通用的顺序相关参数，而较少有研究明确建模模具-胶料交互等技术切换特性。第三，算法比较常常基于不同的数据集、参数设置、停止准则和计算环境报告，这可能会限制性能比较的公平性和可解释性。最后，许多研究强调百分比改善，但对计算量、运营影响、成本影响和可推广性的讨论有限。

为了弥补这些空白，本研究开发并评估了一个基于优化的决策支持框架，用于在真实轮胎制造环境中最小化顺序相关换模时间。三种元启发式算法——模拟退火（SA）、粒子群优化（PSO）和禁忌搜索（TS）——使用相同的工业数据集和计算框架进行实现。此外，开发了一个带子回路消除约束的混合整数线性规划（MILP）模型，并在LINGO 21.0.37中求解，以提供精确优化基准并检验问题的计算难度。精确优化模型为旅行商问题相关的排序问题提供了有价值的基准；然而，其计算难度随节点数和时序约束的增加而急剧上升。这与之前的研究一致，表明穷举精确搜索对于较大的旅行商问题实例是不切实际的（Niharika等，2024），而非对称旅行商问题相关的车间环境中的MILP模型尽管建模严格，但仍具有计算挑战性（Zhang等，2025）。

计算实验中使用两种MILP停止配置。MILP-10表示当满足以下任一停止准则时终止的MILP运行：10分钟计算时间、200万次迭代或1%最优性间隙。MILP-20表示当满足以下任一停止准则时终止的MILP运行：20分钟计算时间、500万次迭代或1%最优性间隙。主要的受控比较在作者实现的方法与公司供应链部门使用的现有排序策略之间进行。ACO和Lin-Kernighan启发式（LKH）仅作为文献参考基准用于结果背景说明。

实验评估基于从案例公司获得的十个真实每日生产计划。为将这些观察到的生产日之外的计算评估进行扩展，从同一产品池并在同一工厂环境、换模结构和运行假设下生成了六个额外的假设性每日生产计划，从而代表了另一种但结构一致的生产场景。因此，所提出的框架在十六个每日问题实例上进行了评估。这一扩展实验设计在研究的工业实例范围内，为替代生产条件下的解质量、鲁棒性和计算性能提供了额外证据，但不暗示对系统性递增问题规模的全面可扩展性分析。

本研究并非提出一种根本性的新优化算法，而是开发并实际评估了一个用于工业生产排序的集成决策支持框架。该框架结合了非对称哈密顿路径建模、基于MILP的优化基准、工业模具-胶料过渡建模以及在一致计算条件下评估的三种元启发式方法。因此，贡献主要在于这些互补组件的系统集成、透明评估和工业验证。

本研究的主要贡献总结如下：

（i）将轮胎制造中一个真实的工业瓶颈设备排序问题建模为基于模具-胶料过渡特性的顺序相关换模时间最小化问题。

（ii）将问题构建为非对称哈密顿路径问题，开发并求解了一个带子回路消除约束的MILP模型，在实践停止准则下分析精确优化结构并在合理的计算时间内生成高质量基准解。

（iii）在相同的工业数据集和计算设置下实现并评估了三种元启发式算法，即SA、PSO和TS。

（iv）从同一产品池并在相同的运行假设下生成六个额外的假设性每日生产计划，将实验分析扩展到原始十个真实生产日之外。

（v）本研究不仅讨论了百分比改善，还讨论了计算量、运营影响、成本相关影响以及所提出框架向其他顺序相关生产环境推广的可行性。

本文其余部分组织如下。第2节回顾相关文献并将本研究定位于先前工作。第3节阐述问题结构、数学建模和解决方案。第4节描述工业应用和实验设计。第5节报告计算和统计结果。第6节讨论研究发现、运营影响以及所提出框架的可推广性。最后，第7节总结研究并展望未来研究方向。

**文献综述**

在换模时间取决于产品加工顺序的制造系统中，生产排序起着关键作用。在此类环境中，低效的排序会增加非增值切换时间、降低有效产能并加剧瓶颈效应。因此，顺序相关换模时间最小化在运筹学和工业工程文献中引起了越来越多的关注。由于这些问题通常是组合性的，并且……

**方法**

本研究解决轮胎制造环境中瓶颈设备上的顺序相关换模时间最小化问题。从建模角度来看，每日生产计划中的每种产品表示为一个节点，两个产品之间的每个有向转换关联一个由模具和胶料变化决定的换模时间。由于每种产品必须恰好加工一次，且所选生产顺序形成一条开放路径而非闭合回路，因此该……

**应用**

本节描述工业案例研究、换模时间数据的构建以及将生产排序问题转化为优化问题的过程。该应用基于从一家轮胎制造公司供应链部门获得的生产数据。主要运营目标是通过确定更高效的每日生产顺序来减少瓶颈设备上的总换模时间。

案例公司生产多种轮胎类型，其中……

**统计分析**

本节呈现完成所有计算实验后的修订统计分析。该分析评估了传统供应链部门顺序、所实现的元启发式算法——禁忌搜索、粒子群优化和模拟退火——以及LINGO基于MILP的基准在20分钟停止条件下（MILP-20）的顺序相关换模时间性能。MILP-10的结果仅在原始结果表中报告以保持透明度，并……

**讨论**

本研究的发现表明了基于优化的生产排序在真实轮胎制造环境中减少顺序相关换模时间的实用有效性。与公司供应链部门使用的现有排序策略相比，所有作者实现的解决方案方法在十个真实生产日均实现了有意义的总换模时间减少。这证实了当前的工业排序实践可以大幅……

**结论**

本研究利用真实工业生产数据，研究了轮胎制造线中瓶颈设备上的顺序相关换模时间最小化问题。

该问题被建模为不对称哈密顿路径问题，其中每个产品必须恰好被处理一次，且所选序列构成一条路径而非环。为解决这一组合优化问题，采用了三种元启发式算法——模拟退火、粒子群优化和TabuCRediT

作者贡献声明
Muhammet Aydin：撰写初稿、软件、调查研究、形式化分析。
Halil ?brahim Demir：撰写审阅与编辑、撰写初稿、监督指导、资源支持、项目管理、研究方法、调查研究、概念构思。

利益冲突声明
作者声明他们不存在任何可能影响本文所述工作的已知竞争财务利益或个人关系。

Muhammet Aydin | Halil ?brahim Demir
萨卡里亚大学，工业工程硕士项目，土耳其萨卡里亚