一种用于具有顺序相关准备时间和运输时间的混合流水车间调度问题的自适应协同进化文化基因算法

《Machines》:An Adaptive Co-Evolutionary Memetic Algorithm for a Hybrid Flow Shop Scheduling Problem with Sequence-Dependent Setup and Transportation Times

【字体: 大 中 小 】 时间:2026年08月28日 来源:Machines 3.0

编辑推荐:

  具有非相关并行机(UPMs)、顺序相关准备时间(SDSTs)和阶段间运输时间的混合流水车间调度问题(HFSP)近年来已成为一个重要的研究课题。为求解以最小化最大完成时间(makespan)为目标的该调度问题,研究人员首先基于机器位置建模思想构建了混合整数线性规

  
具有非相关并行机(UPMs)、顺序相关准备时间(SDSTs)和阶段间运输时间的混合流水车间调度问题(HFSP)近年来已成为一个重要的研究课题。为求解以最小化最大完成时间(makespan)为目标的该调度问题,研究人员首先基于机器位置建模思想构建了混合整数线性规划(MILP)模型。对小规模实例的精确解分析表明,这三重约束的强耦合效应将计算瓶颈集中于耗时的最优性证明过程,从而凸显了所研究的HFSP-SDST-T问题具有强NP难特性。为高效求解大规模实例,研究人员提出了一种新型自适应协同进化文化基因算法(ACMA)。ACMA采用双种群协同进化框架,其中定制遗传算法(GA)负责全局探索,而经Lévy飞行增强的粒子群优化(PSO)提升了局部搜索能力。为动态平衡探索与开发,研究人员设计了动态角色分配(DRA)机制,根据个体的进化状态在两个种群之间自适应地重新分配个体。此外,研究人员提出了一种渐进式两阶段文化基因增强策略,通过依次激活深度变邻域搜索(VNS)和基于灾变的多样化策略来克服早熟收敛,从而对不同停滞水平做出自适应响应。研究人员在小规模和大规模实例上开展了大量实验,包括消融研究、与基准算法的比较以及计算复杂度分析。结果表明,ACMA在小规模实例上能够稳定获得与MILP模型完全一致的最优解,并在大规模复杂实例上取得了具有竞争力的性能。此外,Wilcoxon符号秩检验证实了性能差异的统计显著性,支持了实验结果的可信度。
**面向HFSP-SDST-T的自适应协同进化文化基因算法研究解读**

**一、研究背景与问题**

混合流水车间调度问题(HFSP)是现代制造业中的一类典型调度问题,广泛存在于纺织、制药、半导体制造、汽车装配和钢铁生产等行业。经典HFSP假设各阶段机器为同速并行机,且忽略准备时间和运输时间。然而,实际生产中,同一工件在不同机器上的加工时间往往不同,即存在非相关并行机(UPMs);工序切换所需的准备时间通常取决于前后工件的组合,即顺序相关准备时间(SDSTs);工件在阶段间的转移也需耗费不可忽略的运输时间。现有研究大多仅考虑上述部分约束,对三种约束强耦合效应的建模与求解尚不充分。UPM、SDST和运输时间的交织使解空间结构异常复杂,精确算法即使对极小规模实例也难以在合理时间内证明最优性。因此,亟待开发能够在有限计算时间内获得高质量近似解的智能优化算法。针对这一问题,研究人员开展了本研究,提出了一种新型的自适应协同进化文化基因算法(ACMA),相关成果发表于《Machines》。

**二、研究内容与结论**

研究人员首先基于机器位置建模思想,构建了融合UPM、SDST和阶段间运输时间的混合整数线性规划(MILP)模型,为小规模实例提供精确基准。通过一个小规模实例(n5-s2-m2)的CPLEX求解过程分析发现,计算瓶颈不在于寻找高质量解,而在于证明最优解的所需时间——CPLEX仅需数十秒即可找到最优解(makespan=41),却花费约261秒完成最优性证明。这一现象揭示了该问题的强NP难本质与约束间的强耦合效应。

为高效求解大规模实例,研究人员提出了ACMA。该算法采用双种群协同进化框架:定制遗传算法(GA)负责全局探索,Lévy飞行增强的粒子群优化(PSO)负责局部开发。动态角色分配(DRA)机制根据个体的收敛性与多样性指标动态调整两个种群的成员构成,以维持探索/开发平衡。此外,两阶段文化基因增强机制通过变邻域搜索(VNS)和灾变策略依次响应不同水平的搜索停滞。实验结果表明,ACMA在小规模实例上能以100%的成功率获得与MILP模型一致的最优解,平均计算时间仅2.2秒,相比CPLEX提升约119倍的计算效率;在大规模复杂实例上也显著优于对比算法。

**三、关键技术方法**

研究人员使用了以下主要技术方法:1)基于机器位置的MILP数学建模,用于精确描述强耦合约束并提供小规模基准;2)双种群协同进化框架,其中GA采用双轨进化算子(顺序交叉与均匀交叉、邻位交换突变与约束随机重置突变),PSO通过连续位置到离散调度的映射机制适配调度问题,并引入Lévy飞行精英扰动;3)动态角色分配(DRA)机制,基于归一化的收敛值(目标函数值)与二维结构多样性(工序排序距离和机器分配距离)计算个体适应度分数,按分数排序将前一半个体分配至探索种群、后一半分配至开发种群;4)两阶段记忆增强机制,通过滑动窗口检测有效停滞,第一阶段执行VNS局部救援(作业插入算子Nins和机器变更算子Nmach),失败后第二阶段触发灾变重建(保留前(1?β)比例精英个体,其余用随机解替代);5)采用田口方法(Taguchi method)进行参数校准,并利用Wilcoxon符号秩检验验证算法间差异的统计显著性。实验数据来自统一生成的24个仿真实例(n∈{5,20,50,100},s∈{2,4,6},每阶段机器数Ms~U[2,4],设置低/高两种准备时间强度水平STF=0.5和1.25),无真实样本队列来源。

**四、研究结果**

**(1)参数校准与有效性验证(4.2节)**

采用L27(3×13)正交表对五个关键参数(交叉概率上界$\overline{p_c}$、协作周期T、停滞检测窗口W、VNS最大迭代数K、灾变扰动比β)进行田口参数校准,确定了最优参数组合为$\overline{p_c}$=1.0、T=15、W=20、K=600、β=0.3。随后在n5-s2-m2小规模实例上与CPLEX对比验证,ACMA在10次独立运行中均以2.2秒平均耗时获得最优值41,与CPLEX解完全一致,验证了算法的正确性与高效性。

**(2)消融研究:核心组件的必要性(4.3.1节)**

将完整ACMA与两个退化变体ACMA-no-DRA(移除DRA机制)和ACMA-no-ME(移除两阶段增强机制)进行对比。结果表明:移除记忆增强机制导致的性能退化最为显著,在大型实例上最优值和平均值均大幅恶化,证明了两阶段增强机制对于深度局部开发和摆脱局部最优的关键作用;移除DRA机制后,最优值、平均值和标准差均有不同程度恶化,且大规模实例上标准差的增大更为明显,说明DRA机制在维持种群多样性、稳定全局探索过程和增强鲁棒性方面具有重要作用。两种机制互补且不可或缺。

**(3)SOTA对比:综合性能与统计检验(4.3.2节)**

在全部24个实例上与离散人工蜂群算法(DABC)和混合蚁群优化算法(HACO)进行比较。ACMA在所有24个实例上均取得历史最优值(Best),DABC和HACO的命中率远低于ACMA;在平均值指标上,ACMA在21个实例上取得最优,而DABC和HACO分别仅在2个和5个实例上最优。箱线图分析表明,虽然ACMA在某些实例上的标准差数值略高,但其整体解分布区间仍低于竞争对手的最优解下限,说明微小方差增加换取了平均性能的大幅提升。Anderson–Darling正态性检验显示数据不服从正态分布,故采用Wilcoxon符号秩检验:在Best指标上,ACMA对DABC和HACO的Z值分别为?3.724和?3.920(p<0.001);在Mean指标上Z值为?4.107和?3.302(p<0.001),均达到统计显著差异;在Std指标上Z值为?0.146和?1.164(p>0.05),说明ACMA的性能提升不以牺牲稳定性为代价。

**(4)理论分析(4.3.2节)**

从算法设计角度分析,DRA机制根据个体进化状态动态调整其搜索角色,改善了搜索资源利用率,维持了探索与开发的平衡;两阶段增强机制针对不同停滞水平自适应触发不同强度的干预,减少了不必要的计算开销,提升了摆脱深层局部最优的能力。两种机制在优化过程的不同阶段互补协作,使ACMA能够根据进化状态持续调整搜索行为,从而有效应对HFSP-SDST-T的强耦合特性。

**五、总结与展望(第5节翻译)**

本研究通过提出新型ACMA,解决了包含UPM、SDST和阶段间运输时间的复杂HFSP问题(HFSP-SDST-T)。主要贡献包括:(1)建立了融合多种实际约束的精确MILP模型,为启发式搜索提供了最优基准;(2)提出了具备创新DRA机制的双种群架构,实现了从被动进化到主动种群管理的转变;(3)设计了两阶段增强引擎,改善了局部最优逃逸能力并确保稳定收敛;(4)大量测试实例证实该算法在解质量和鲁棒性方面优于现有方法。大量计算实验表明,ACMA有效处理了多种物理约束引起的高阶耦合与级联延迟效应。在解质量和跨尺度鲁棒性方面,该算法表现出优于现有先进算法的优势,为现代复杂柔性车间的智能调度提供了一种极具竞争力的新工具。本研究仅限于静态单目标调度环境,未来工作将:(1)将ACMA扩展至考虑能耗和拖期指标的多目标框架;(2)集成数字孪生技术和深度强化学习,以应对动态不确定的生产事件。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号