基于大语言模型引导的耦合感知破坏方法用于节能型阻塞混合流水车间调度

《Computers & Operations Research》：Coupling-aware destruction with large-language-model guidance for energy-efficient blocking hybrid flow shop scheduling

　　

## 摘要

带有顺序相关准备时间的阻塞式混合流水车间调度与分时电价问题是一个双目标调度问题，需要同时最小化完工时间和能源成本。阻塞约束在这两个目标之间产生了隐性的耦合关系，即单个约束通过不同机制影响完工时间和能源成本，且占主导地位的耦合效应随帕累托前沿不同区域而变化。标准进化基线方法并未显式建模这种区域特定的耦合结构。我们的方法在基于分解的多目标框架中嵌入了一种耦合感知的迭代贪心算法，其中大语言模型（LLM）充当约束-目标耦合分析器。LLM并非替代进化算子，而是识别每个帕累托区域中占主导地位的耦合效应，并通过三级阶段自适应架构提供子问题特定的破坏-构造策略。在测试的配置中，该设计每次运行约需三十一次至四十三次LLM调用机会。在适配的基准实例以及具有真实调度结构和代表性能源参数的炼钢-连铸实例上的计算实验表明，所提方法比九种比较算法获得了更高的超体积和更低的反向世代距离，其中包含了使用相同破坏模式动作空间的非LLM变体。

## 引言

混合流水车间调度问题（HFSP）产生于作业必须按顺序通过多个加工阶段、且每个阶段提供两台或更多并行机器的场景。这种配置在钢铁制造、半导体制造、石化加工和造纸行业十分常见（Ruiz和Vázquez-Rodríguez，2010）。作为经典流水车间问题和并行机问题的推广，HFSP即使在两个阶段、其中一个阶段仅有一台机器时也属于NP-hard问题（Ribas等人，2010）。其实用重要性和计算难度促使过去二十年来涌现了大量研究。

在许多生产环境中，阶段间的缓冲存储要么有限要么完全缺失。一旦作业在某个阶段完成，如果下游机器仍被占用，已完成的作业就会停留在当前机器上，使其无法接受下一个作业（Hall和Sriskandarajah，1996）。这种现象称为阻塞，它以一种无限缓冲模型无法捕获的方式将所有阶段耦合在一起。任何下游阶段的延迟都会沿生产线向上传播，产生的连锁效应可能使完工时间远超各作业单独加工时间之和所暗示的水平。阻塞流水车间已通过构造启发式方法（Pan和Wang，2012）和迭代贪心（IG）算法（Tasgetiren等人，2017）进行了研究。然而，阻塞混合流水车间因作业还必须分配到各阶段的并行机器上，且一台机器的阻塞可能影响同阶段其他机器的可用性而引入额外难度（Y. Wang等人，2023）。

现代制造业面临着在缩短生产时间的同时降低电费支出的日益增长的压力。分时（TOU）电价在不同的高峰、平峰和低谷时段收取不同价格，为通过将能耗密集的操作移至廉价时段来降低成本提供了机会（Zhang等人，2014）。在阻塞约束下，这一机会更难实现：被阻塞的机器在持有已完成作业且不产生输出时仍消耗能源，而这种无生产性运营的成本取决于阻塞发生在电价表中的哪个时段。H.-X. Qin等人（2022）研究了节能型阻塞混合流水车间并提出了一种改进的IG算法，但其模型仅针对单一能源目标。当完工时间和能源成本必须同时优化时，问题变为多目标问题，阻塞约束与两个目标之间的相互作用创造了单一目标方法无法直接建模的耦合景观。引入能源目标的必要性源于TOU定价下两个标准之间的真实冲突：最小化完工时间倾向于将操作连续填充无论电价时段如何，而最小化能源成本倾向于将操作移至低谷窗口，即使这会造成空闲间隔。阻塞放大了这种冲突，因为被阻塞的机器在无产出的情况下消耗待机功率，而这种浪费是否昂贵取决于其发生在电价表中的时间。在我们的实验中，完工时间最优解比能源最优解的能源成本高出18%至27%（跨所有测试基准实例），证实了单一目标公式将牺牲大量成本节省。双目标公式允许决策者沿帕累托前沿选择一个平衡吞吐量和电费支出的运行点，以符合其生产优先级。

进化多目标优化存在两种主流框架。非支配排序遗传算法II（NSGA-II）（Deb等人，2002）基于帕累托支配对解进行排序，并通过拥挤距离促进多样性。基于分解的多目标进化算法（MOEA/D）（Zhang和Li，2007）则将多目标问题分解为一组标量子问题，每个由一个权向量控制，并通过邻域结构协作求解。对于帕累托前沿为非凸或不连续的调度问题，MOEA/D相较于基于支配的方法已展现出优势（Zhang等人，2019a）。混合流水车间中的阻塞约束往往恰好产生此类不连续性，因为作业顺序的小变化即可触发或消除阻塞连锁效应，导致两个目标值的突变。

在流水车间调度的元启发式算法中，IG算法以其简洁性和优越性能而脱颖而出（Ruiz和Stützle，2007）。IG在破坏阶段和构造阶段之间迭代，破坏阶段从当前解中移除一部分作业，构造阶段通过贪心启发式将它们重新插入。该机制保留了流水车间解的顺序结构，并已扩展至阻塞变体（Tasgetiren等人，2017）、分布式配置（Y. Wang等人，2023）和约束混合设置（Su等人，2025）。然而，在标准IG过程中，破坏步骤随机选择作业，不考虑哪些作业对阻塞贡献最大或哪些作业安排在昂贵电价窗口期间。对于阻塞通过不同机制影响完工时间和能源成本的多目标问题，耦合感知的破坏提供了一种方式，将搜索努力导向对目标影响更大的作业。

大语言模型（LLM）最近已成为组合优化和算法设计的工具。FunSearch证明，将LLM与程序评估器配对可以发现超越人类设计方法的启发式（Romera-Paredes等人，2024）。ReEvo提出了一种反思进化框架，LLM在其中生成、评估并优化操作算子（Ye等人，2024），启发式进化方法进一步表明LLM驱动的设计在经典组合问题上可达到甚至超越手工设计的算法（Liu等人，2024）。在调度领域，多智能体LLM框架已被提出作为跨多个问题类别的通用进化优化器（Wang等人，2025），LLM辅助的强化学习框架已被应用于混合流水车间调度（Zhao等人，2026）。近期的一项综述概述了LLM与进化计算之间日益增长的互动关系（Wu等人，2025）。在这些密切相关的工作中，LLM通常用于算子生成、初始化、评估或智能体编排。一个中间选项，即少数精确定位的LLM调用，读取局部帕累托前沿状态并调整子问题级算子选择，受到的关注较少。

这一设置促使我们提出三项方法论需求。首先，阻塞约束与每个目标产生不同的耦合效应：阻塞通过连锁延迟增加完工时间，通过在昂贵电价窗口内的无生产性机器运行增加能源成本。其次，基于分解的多目标搜索可以从子问题特定的破坏-构造算子中受益，因为靠近完工时间最优端的子问题面临的占主导耦合效应与靠近能源最优端的子问题不同。第三，LLM引导应该有选择地调用：每代调用LLM开销较大，而优化前的一次性调用无法适应搜索的演变状态。阶段自适应策略可以在引导质量与计算成本之间取得平衡。

在此，我们提出了一种耦合感知的LLM增强多目标IG算法，称为COLA-MOIG，用于带有顺序相关准备时间的双目标节能型阻塞混合流水车间调度问题。贡献如下：

- 开发了一个约束-目标耦合分析框架，LLM在其中总结阻塞、准备时间和TOU能源定价如何在帕累托前沿不同区域相互作用。LLM被用作紧凑统计摘要的结构化阅读器，输出区域特定的破坏模式标签，而非算子生成器或端到端求解器。
- 设计了一个三级阶段自适应的LLM集成架构。在实例层面，LLM在优化开始前刻画耦合结构。在分解层面，定期调整权向量并推荐区域特定算子。在精英层面，对停滞解执行定向扰动。在测试的配置中，每次运行的LLM调用机会总数约为三十一次至四十三次。
- 为IG引擎开发了一种耦合感知的破坏-构造机制。破坏步骤不再随机移除作业，而是根据子问题在帕累托前沿上的位置，基于阻塞时间、高峰窗口能源或二者乘积的模式特定严重度评分定向选择作业。
- 在适配的阻塞混合流水车间基准和Su等人（2025）的炼钢-连铸实例（补充了代表性TOU和机器功率参数）上的实验表明，所提方法比九种比较算法获得了更高的超体积和更低的反向世代距离。
- 刻画了调度结构。阻塞阻止在相邻阶段共享同一机器的两个作业交换位置，因此每个可行的两阶段调度使用一个共同作业顺序，而从第三阶段起，超越可达到的帕累托点无法通过任何共同顺序实现。测量了共同顺序限制的代价与精确前沿的对比，并展示了不存在在任何阶段都以相同顺序完成所有作业的帕累托最优调度的实例。

本文其余部分组织如下。第2节回顾阻塞混合流水车间调度、节能调度和LLM辅助优化的相关工作。第3节对问题进行数学建模。第4节详细介绍COLA-MOIG框架。第5节报告计算实验与分析。第6节讨论主要发现和局限性，第7节总结全文并讨论未来方向。图1展示了总体框架。

## 问题片段

### 阻塞混合流水车间调度

当相邻阶段之间不存在中间缓冲时，已完成作业的机器无法释放该作业，直到下游机器可用（Hall和Sriskandarajah，1996）。被阻塞的机器保持空闲但被占用状态，这以级联方式将所有阶段耦合在一起。由此产生的阻塞流水车间即使在简化设置下也是NP-hard的（Ribas等人，2010）。

早期工作针对排列情况。已开发了构造启发式方法和迭代局部搜索

### 问题描述与符号

节能型阻塞混合流水车间调度问题（EBHFSP）描述如下。一组$\mathcal{J}=\{1,\ldots,n\}$共$n$个作业必须按固定顺序$1,2,\ldots,S$通过$S$个顺序阶段。阶段$s$包含$m_s$台无关并行机器$\mathcal{M}_s$，每个作业在每个阶段恰好在一台机器上加工，不可抢占。作业$j$在阶段$s$机器$i$上的加工时间为$p_{j,s,i}$。当作业$j$紧随作业$j'$在阶段$s$机器$i$上加工时，会产生顺序相关准备时间（SDST）$\sigma_{j',j,s,i}$；a

### 框架概述

COLA-MOIG集成了三个组件：将双目标问题转化为$N$个标量子问题的MOEA/D分解层、通过耦合感知破坏和构造改进每个子问题的IG引擎、以及提供子问题特定战略引导的三级LLM架构。一个耦合知识缓存存储成功的LLM分析结果以供相似模式重现时复用。

一个解被编码为作业排列$\pi=(\pi_1,\pi_2,\ldots,\pi_n)$，作为优先级

### 实验设置

实验在两组基准实例上将COLA-MOIG与九种比较算法进行评估。三个多目标性能指标评估解的质量，非参数统计检验确定观察到的差异是否可靠。

构建了两组基准实例。第一组称为适配Taillard阻塞混合流水车间实例（AT-BHFS），将经典Taillard基准扩展至带有SDST的阻塞混合流水车间设置，遵循适配

### 讨论

三项发现值得强调。第一，COLA-MOIG与LLM-EA的对比表明LLM的集成角色至关重要。两种算法都调用LLM，然而COLA-MOIG在AT-BHFS上比LLM-EA高出6.5%，在SCC上高出7.7%。差异在于LLM被要求总结的内容：COLA-MOIG引导LLM关注约束-目标耦合，而LLM-EA使用更通用的调度表示。

该结果表明，大语言模型在优化中的价值取决于Conclusions本文研究了分时电价下具有序列相关准备时间的双目标节能阻塞式混合流水车间调度问题。我们提出了COLA-MOIG，该方法将大语言模型嵌入到基于MOEA/D的迭代贪心搜索中，作为约束-目标耦合分析器。其三层架构分别用于刻画实例结构、在Pareto前沿上分配区域特定的破坏模式，以及扰动停滞的精英解，同时将LLM总成本控制在以下Shikun Chen宁波财经学院人工智能学院，中国宁波，315175