基于改进多种群候鸟迁徙算法的混合流水车间调度

An Improved Multi-Swarm Migrating Birds Optimization Algorithm for Hybrid Flow Shop Scheduling

针对带顺序依赖准备时间的混合流水车间调度(HFS-SDST)问题,以最小化总最大作业完成时间为调度目标,提出一种改进多种群候鸟迁徙优化(IMMBO)算法.算法中个体基于工件加工顺序进行编码,用改进的NEH(MNEH)算法产生初始种群,并按照适应度值分配到各子种群.子种群中领飞鸟和跟飞鸟分别利用串行和并行邻域策略产生邻域个体,如果跟飞鸟优于领飞鸟,二者互换,完成种群内部个体的信息交互;在IMMBO算法中嵌入离散鲸鱼优化策略对各子种群的领飞鸟进行优化,实现子种群之间信息交互;为提高算法的局部搜索(LS)能力,对种群中最优个体执行LS,同时,为了避免算法早熟收敛,针对每个种群的领飞鸟设计了种群多样化控制策略.最后,在实验法调整算法参数的基础上,对IMMBO的4个变体进行了仿真实验,通过测试Ta自适应算例验证IMMBO算法各部分的作用;将IMMBO算法与现有3个算法测试Ta自适应算例,进行实验结果比较,证明了IMMBO算法求解混合车间调度问题的有效性.

An improved multi-swarm migrating birds optimization(IMMBO)algorithm is proposed for hybrid flow shop scheduling with sequence-dependent setup times(HFS-SDST),to minimize the total maximum completion time(i.e.,makespan).Permutation-based encoding is adopted to substitute the individual.The modified Nawaz-Enscore-Ham(MNEH)algorithm is employed to generate initial population which are assigned to each sub-swarm according to the makespan.For each sub-swarm,the neighborhood individuals of the leader and followers are generated respectively by performing serial and parallel neighborhood strategies.If the follower is better than the leader according to their makespan,they are exchanged to ensure the information interaction of individuals within the sub-swarm.Moreover,the discrete whale optimization strategy is embedded in IMMBO to optimize the leaders of all sub-swarms to enhance the interaction among them.Furthermore,the local search is designed for the optimal individual to further improve the local search ability of the algorithm.Meanwhile,to avoid algorithm premature convergence,the control strategy for population diversification is designed to the leader of each sub-swarm.Finally,based on adjusting the algorithm parameters experimentally,simulation experiments are conducted on four variants of IMMBO to verify the function of each part by testing an adaptation dataset of Ta.Moreover,the IMMBO is compared with three existing algorithms by testing an adaptation dataset of Ta,and the experimental results demonstrate the effectiveness of the IMMBO algorithm to solve the hybrid flow shop scheduling problem.