含恶化维护与运输时间的节能混合流水车间调度问题的计算智能方法

《Mathematics》：A Computational Intelligence Approach for the Energy-Efficient Hybrid Flow Shop Scheduling Problem with Deteriorating Maintenance and Transportation Times

　　

该研究探讨了考虑恶化维护（deteriorating maintenance, DMT）与运输时间的节能混合流水车间调度问题（energy-efficient hybrid flow shop scheduling problem with deteriorating maintenance and transportation times, EHFSP-DMT），该问题是复杂制造系统中的NP难组合优化问题。为对该问题进行建模，研究人员建立了混合整数规划数学模型。研究人员提出一种称为自适应反馈多起点变邻域搜索（adaptive feedback multi-start variable neighborhood search, AFMS-VNS）算法的计算智能方法，以同时最小化最大完工时间（makespan, Cmax）与总能耗（total energy consumption, Etotal）。在AFMS-VNS中，设计了一种集成冲突检测的解码策略以满足设备维护的数学约束；采用强化学习（Q学习）机制评估并自适应选择搜索算子以提升搜索效率；提出基于种群分布状态反馈的搜索策略以平衡两个冲突目标间的优化方向；采用由精英外部存档引导的迭代贪婪重构策略替换停滞个体。在44个算例上的实验及Wilcoxon符号秩检验表明，在求解EHFSP-DMT时，AFMS-VNS在反向世代距离（inverted generational distance, IGD）、超体积（hypervolume, HV）和集覆盖（set coverage, SC）指标上均优于五种对比算法。

研究背景方面，混合流水车间调度问题（hybrid flow shop scheduling problem, HFSP）具有阶段并行与工序顺序约束特征，广泛存在于半导体制造、板式家具生产及机械加工等离散制造业，已被证明为NP难组合优化问题。随着离散工业对能效要求的提升，调度目标由单一完工时效性转向运营效率与能耗的权衡。现有研究多关注机器变速控制、分时电价、分布式布局、阻塞约束等，并在预防性维护（preventive maintenance, PM）方面常假设传统预防性维护（traditional preventive maintenance, TPM）时长恒定，忽视了设备随运行时间自然劣化导致维护时长非线性增长的恶化维护（deteriorating maintenance, DMT）现象；同时跨阶段运输时间对车间能耗与效率的直接影响在多数模型中未被同时纳入。由于DMT使维护开始时间推迟会放大下游工序与运输的非线性级联延迟，EHFSP-DMT在结构上区别于TPM模型。该研究由研究人员发表于《Mathematics》，旨在建立EHFSP-DMT的数学模型并设计高效多目标元启发式算法。

主要关键技术方法方面，研究人员采用混合初始化构造初始种群，结合最短加工时间（shortest processing time, SPT）与最长加工时间（longest processing time, LPT）规则及随机采样，并在速度层（VS）按节能优先、时间优先与均匀随机分层赋值；以Q学习驱动算子选择，将作业序列交换（Swap）、插入（Insert）与速度升降（SpeedUp、SlowDown）作为动作空间，以种群在目标空间中位于C_max极端、E_total极端或均衡区三种分布密度状态为状态空间，按Pareto支配关系给予分层奖励更新Q表；设计基于目标空间密度反馈的自适应搜索策略，在C_max拥挤时触发SlowDown、在E_total拥挤时触发SpeedUp、均衡时仅对作业序列做变邻域下降（variable neighborhood descent, VND）；以精英外部存档引导迭代贪婪重构替换停滞个体；整体以多起点变邻域搜索（multi-start variable neighborhood search, MS-VNS）为框架，解码阶段用贪心最早完工时间策略动态分配机器。

研究结果部分，第二节问题描述与数学模型建立EHFSP-DMT的机器三态（加工、空闲、PM）、速度集、跨阶段运输时间、DMT函数t_h^PM=t₀^PM+α·S_h及最大连续运行阈值T_m^max等约束，给出C_max与E_total（含加工、空闲、运输能耗）双目标及混合整数规划方程，并通过归约至经典HFSP证明其为NP难，指出DMT下局部扰动引发Δt_h·(1+α)放大延迟。第三节所提AFMS-VNS含双层编码（作业序列OS与速度选择VS）、带维护冲突检测的解码算法、混合初始化、Q学习自适应算子选择、三区域密度反馈搜索、存档引导贪婪重构及整体流程，复杂度分析表明为O(G·N·n·s·m_max+G·N·L_vnd·n)。第四节计算实验中，44个算例（n∈{10,20,30,40,50,60,80,100,120}，s∈{2,3,4,5,6,8}）以Python实现，对比MS-VNS、MDCEA、TMOEA、ITLBO、VNS-NSGA-II五算法，用SC、IGD、HV评价；小规模算例与CPLEX加权法和（ω=0.5）比对显示AFMS-VNS在15作业内达最优且耗时<1秒；消融实验（去Q学习noQ、去反馈noF、去重构noG、换标准Q学习StdQ）证三组件均贡献显著，noF对IGD损伤最大；主对比中AFMS-VNS在44例中33例IGD最小、37例HV最大，SC指标全面占优，Wilcoxon符号秩检验在0.05水平显著优于所有对比算法，最大规模120作业8阶段144秒CPU内出解。

讨论与结论翻译部分，研究人员指出：其一，纳入DMT捕捉设备老化时变特性，忽视劣化将导致计划过于乐观、引发非预期停机冲突与能耗估计偏差；其二，跨阶段运输时间使管理人员可识别机器空闲窗，在运输诱发空闲段关机节能而不增C_max；其三，状态反馈机制依种群分布切换提速/减速模式，在高作业机比瓶颈场景稳定调度性能。该算法在120作业8阶段典型班次调度量下144秒内输出节能方案，计算成本兼容离散制造现场班次级时预算。未来研究将沿四向拓展：将强化学习机制延伸至在线动态调度以应对机器故障与急单；在数字孪生框架内部署形成数据驱动闭环实时优化；放宽连续物流假设，耦合有限容量车辆路径与无碰撞AGV调度；将问题重构为分布式多智能体架构以提升大规模车间可扩展性与容错性。