累积流水车间调度问题的局部搜索方法

《Operations Research Perspectives》：Local search methods for the cumulative flow shop scheduling problem

　　

调度问题通常是在每个资源一次只能处理一个作业的假设下进行研究的。然而，在许多现实场景中，资源能够同时处理多个作业，从而产生了累积调度问题，其中每个资源可以处理多达指定容量的若干个作业。虽然累积调度已经在作业车间和并行机器环境中得到研究，但在流水车间环境中仍未被探索。在这项工作中，研究人员将累积流水车间调度问题作为经典流水车间的一个推广引入。研究人员提出了一种混合整数规划（MIP）公式以及两种元启发式方法——一种迭代局部搜索算法（ILS）和一种迭代贪婪算法（IG）——旨在最小化总流动时间（Total Flow Time, TFT）。两种方法都融入了问题特定特征，例如适应性的初始解和改进资源利用的重调度机制。通过这种方式，它们在一项综合计算研究中展示了强大的性能。此外，研究人员分析了总流动时间与资源利用之间的权衡，并研究了不同作业规模和资源容量如何影响结果。研究人员的发现提供了可操作的管理见解，并为累积调度问题的研究开辟了新途径。

**论文解读：累积流水车间调度问题的局部搜索方法**

**研究背景与问题**

在传统的调度问题中，通常假设每个资源一次只能处理一项作业。然而，在许多实际生产环境中，资源具备同时处理多项作业的能力，例如农业技术公司的温室设施或热加工过程中的烘箱。这种环境下，资源具有容量限制，可并行处理多个作业，被称为累积调度问题。尽管累积调度已在作业车间和并行机器场景中得到初步研究（如Nuijten和Aarts[8]、Carlier和Néron[9]），但在流水车间环境中仍未被探索。经典流水车间调度问题本身是NP难的，引入累积特性后，作业的并行处理增加了类似装箱问题的维度，使问题更加复杂。然而，目前缺乏针对累积流水车间的有效求解方法和系统性分析。为此，研究人员首次提出并研究累积流水车间调度问题，旨在填补这一空白，并开发高效的求解方法，以最小化总流动时间（Total Flow Time, TFT），同时揭示问题结构与优化权衡。

**研究内容与结论**

研究人员定义了累积流水车间问题：一组作业需按相同顺序通过多台机器，每台机器可同时处理多个作业，但总作业规模不得超过机器容量。为此，他们提出了混合整数规划（MIP）模型作为精确求解方法。由于问题的NP难性质，进一步设计了两种元启发式算法：迭代局部搜索（ILS）和迭代贪婪算法（IG），两者均集成了问题特定的重调度机制和适应性初始解生成规则。通过大规模计算实验，研究人员验证了所提方法在多种实例规模下的有效性，并深入分析了总流动时间与机器利用率之间的权衡关系，以及作业规模分布和机器容量变化对性能的影响。研究结果表明，所提方法显著优于对比算法，且重调度机制对大规模实例至关重要；同时，优化单一目标可能导致资源利用率次优，容量增加带来递减的边际收益。这些发现提供了具有管理实践意义的指导，并开创了累积调度问题研究的新方向。该论文发表在《Operations Research Perspectives》。

**关键技术方法概述**

研究人员主要采用了三种核心技术方法：（1）混合整数规划（MIP）模型，采用时间索引变量直接建模容量约束，但仅适用于极小规模实例。（2）迭代局部搜索算法（ILS）和迭代贪婪算法（IG），均基于作业序列表示，通过标准插入解码实现调度。ILS使用局部搜索（单作业插入）、扰动（随机插入或交换）和模拟退火接受准则；IG则通过破坏-重建步骤替换扰动。两种算法均包含重调度机制，旨在利用空闲容量提前插入作业，改善资源利用。（3）初始解生成采用最短处理时间（SPT）和考虑作业规模与处理时间乘积的SPTS规则，择优使用。计算实验基于生成的数据集，包括小规模（10-15作业，3-10机器）和大规模（20-500作业，3-10机器）实例，作业规模分布分别为均匀分布U[1,20]和U[5,15]，机器容量水平设为20、50和100。

**研究结果**

**5. 计算研究**

**5.1 实验设置**：研究人员生成了两个数据集，小规模用于MIP验证，大规模用于元启发式比较。处理时间从[1,50]均匀选取，机器容量在三个水平，作业规模分布分为高方差和低方差两类。所有算法用C++实现，MIP用CPLEX求解，时间限制设为(n·m·π_CPU)毫秒，π_CPU取30或60。

**5.2 校准**：通过设计实验对ILS和IG的参数进行校准，使用90个不同大小的实例。结果显示，ILS的最佳参数为PerL=2、PerSol=10、T=7，且单作业插入局部搜索优于块插入。IG的最佳参数为d=1、T=7。所有对比算法也经过类似校准。

**5.3 小规模实例结果**：MIP仅能最优求解最多15作业和5机器的小问题，对更大实例出现高RPD（如580.28%）。而ILS和IG在多数小实例中平均RPD低于1%，证明了其有效性。

**5.4 大规模实例结果**：在q_j～U[1,20]实例中，ILS和IG的总平均RPD均为1.30%（π_CPU=30），显著优于对比算法（HSA 6.67%，ABC 9.76%）。重调度机制大幅提升性能，如n=500时，IG与无重调度的IGw的RPD分别为1.91%和16.86%。对于q_j～U[5,15]实例，ILS在较大问题上略优于IG，重调度增益降低。整体上，ILS更稳健，IG适合大规模高方差实例。

**6. 问题分析与讨论**

**6.1 总流动时间与机器利用的层次优化**：研究人员以最大完工时间（C_max）作为次要目标衡量资源利用，采用ε约束法生成帕累托前沿，分析两个目标的关系。

**6.2 示例帕累托前沿**：两个示例实例的帕累托前沿显示明显的权衡关系，例如在总流动时间仅增加1.1%时，最大完工时间可降低4.5%。存在非比例变化，提示仅关注总流动时间可能导致资源利用率偏低。

**6.3 机器容量的影响**：通过缩放容量因子f∈[1.2,2.0]进行敏感性分析，结果表明容量增加20%可使总流动时间平均降低8.05%，但边际收益递减。容量翻倍时改善约24%。容量增加对多作业少机器实例更有效，而对多机器实例效果减弱。

**6.4 管理见解**：基于分析，研究人员建议决策者优先使用ILS算法，尤其在作业规模方差较低时；重调度机制应作为核心组件；单一目标优化可能误导，多目标视角更优；容量投资需评估收益递减特性，在作业数量多且机器少的场景下回报最高。

**总结讨论与研究结论**

研究人员在讨论部分强调，问题结构依赖实例参数（如作业规模方差），所提出的元启发式方法可有效求解，但未来研究可向理论分析与多目标优化拓展。结论部分翻译如下：

在这项研究中，研究人员引入了累积流水车间调度问题，其特点是机器可以在给定容量内并行处理多个作业。该问题源于温室作业等实际应用，是经典流水车间调度问题的推广。研究人员提出了最小化总流动时间的混合整数线性规划公式，并开发了两种元启发式方法：迭代局部搜索（ILS）和迭代贪婪算法（IG），两者均通过重调度程序等定制组件得到增强。一项全面的计算研究证明了这些方法的有效性，并提供了对累积流水车间调度问题结构特征的见解。结果强调，调度策略应根据具体问题设置进行调整。特别是，作业规模的分布起着重要作用，尽管这一因素在调度文献中常被忽视。此外，总流动时间与机器利用率之间的相互作用反映了累积调度中容量使用的独特作用。即使对流动时间的小幅放松也能带来不成比例的高利用率，这表明双目标视角比仅关注流动时间更合适。同时，敏感性分析量化了容量变化对解决方案质量的影响，从而能够对累积调度环境进行更明智的成本效益评估。尽管有这些贡献，仍有几个研究问题有待解决。对不同目标下累积调度问题的理论分析仍然缺乏。特别是，与相关问题（如混合流水车间或具有批处理机器的流水车间）的异同值得进一步研究。由于累积调度整合了调度和装箱问题的各个方面，结合两个领域的求解技术也可能提供有价值的见解。此外，多目标方法应得到更多关注，超越总流动时间和最大完工时间，纳入更多性能标准。最后，所提出的元启发式方法只是解决累积流水车间问题的第一步；数学启发式和基于分解的方法似乎是未来研究中特别有前景的途径。