增强型混合离散差分进化算法求解阻塞流水车间调度问题  

An enhanced hybrid discrete differential evolution algorithm for blocking flow shop scheduling problem

作　　者：易高明 YI Gaoming(College of Science,Guilin University of Aerospace Technology,Guilin 541000,China)

机构地区：[1]桂林航天工业学院理学院,桂林541000

出　　处：《现代制造工程》2023年第4期1-12,共12页Modern Manufacturing Engineering

基　　金：2022年桂林航天工业学院科研基金项目(XJ22KT17)。

摘　　要：针对以最小化制造期为优化目标的阻塞流水车间调度问题,提出一种基于动态自适应的增强型混合离散差分进化算法。增强型混合离散差分进化算法采用基于工件排列的形式进行编码,首次利用带机器权重的PF规则与NEH启发规则联合构造初始种群,PF-NEH联合规则提升了初始解的质量和多样性;在差分进化的变异阶段,采用一种全新的分类变异策略,更有针对性地控制不同适应度个体的变异需求和方向;在交叉阶段,采用基于位置的交叉策略,保证得到一组合法完整的实验调度序列,并利用贪婪选择的方式确定目标个体;在局部搜索阶段,加入禁忌搜索算子,并融入一种新颖的兼顾集中性与多样性的自适应局部搜索机制,以动态平衡算法的全局粗搜索和局部细搜索。此外,为避免算法的早熟及后期易陷入局部最优,增加了多样性保持机制。最后,在典型算例上进行各种性能实验,验证了所提出的增强型混合离散差分进化算法的有效性和优越性。An enhanced hybrid discrete differential evolution algorithm based on dynamic self-adaptation was proposed for the blocking flow shop scheduling problem which was optimized to minimize the manufacturing period.The enhanced hybrid discrete differential evolution algorithm is coded based on the work-piece arrangement.For the first time,the PF rule with machine weight was combined with the NEH heuristic rule to construct the initial population.The PF-NEH joint rule improves the quality and diversity of the initial solutions.In the variation stage of differential evolution,a new categorical mutation strategy was adopted to control the variation demand and direction of individuals with different fitness more pertinently.In the crossover stage,the location-based crossover strategy was used to ensure a set of legal and complete experimental scheduling sequences,and the greedy selection method was used to determine the target individuals.In the local search stage,tabu search operator was added,and a novel adaptive local search mechanism with both concentration and diversity was integrated,as well as the global coarse search and local fine search of dynamic balance algorithm.In addition,in order to avoid the prematurity of the algorithm and the tendency to fall into local optimization in the late stage,the diversity preservation mechanism was increased.Finally,the effectiveness and superiority of the proposed enhanced hybrid discrete differential evolution algorithm were verified by various performance experiments on typical examples.

关 键 词：阻塞流水车间调度 增强型混合离散差分进化 分类变异 自适应局部搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TH164[自动化与计算机技术—计算机科学与技术]