应用改进混合进化算法求解零空闲置换流水车间调度问题  

Improved Hybrid Evolutionary Algorithm for Solving No-Idle Permutation Flow Shop Scheduling Problem

作　　者：裴小兵[1] 李依臻 PEI Xiao-bing;LI Yi-zhen(School of Management,Tianjin University of Technology,Tianjin 300384,China)

机构地区：[1]天津理工大学管理学院,天津300384

出　　处：《运筹与管理》2020年第11期204-212,共9页Operations Research and Management Science

基　　金：国家创新方法工作专项项目:(2017IM060200);天津市哲学社会科学项目(TJYY17-013)。

摘　　要：针对总拖期时间最小化的零空闲置换流水车间调度问题,提出了一种基于关键块结构的混合进化算法。该算法以遗传算法为框架,设计了依据关联规则计算染色体上基因之间关联强度的方法,以便挖掘优势染色体上的优势基因组成关键块,并在优势关键块的基础上构建具有较优解的人工染色体种群。同时,引入双精英进化机制,提高算法交叉和变异的有效性,避免算法的无效交叉。精英进化产生的子代种群依据关联规则挖掘关键块,基于交换邻域结构,结合NEH算法的思想,互换非关键块上工件之间的位置,得到局部搜索解。最后,通过对Taillard基准问题进行仿真测试,并将本文算法运行结果与其他算法进行比较,验证了算法的有效性。This study proposes a hybrid evolutionary algorithm based on key blocks to solve the no-idle permutation flow shop scheduling problem with the total tardiness minimization criterion.Based on the framework of genetic algorithm,this paper designs a method to calculate the correlation strength of genes on chromosomes according to association rules in order to mine the key blocks of dominant genes on dominant chromosomes,and construct the artificial chromosome population with better solution according to dominant key blocks.Meanwhile,to avoid invalid intersection of algorithms and improve the effectiveness of crossover and mutation in algorithms,the dual-elite evolution mechanism is introduced.The descendant population generated by elite evolution mines key blocks following association rules.Based on the exchange of neighborhood structure and combining with the idea of NEH algorithm,the positions of the workpieces on non-key blocks are exchanged to obtain the local search solution.Finally,the simulation results on Taillard benchmark compared with other algorithms show that the proposed algorithm is an efficient and effective method.

关 键 词：置换流水车间调度 总拖期时间 关键块 关联规则 双精英进化 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TB491[自动化与计算机技术—控制科学与工程]