Abstract: 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 dualelite evolution mechanism is introduced. The descendant population generated by elite evolution mines key blocks following association rules. Based on the exchange of neigh borhood 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.

Key words: permutation flow shop scheduling problems, total tardiness, key blocks, association rule, dual-elite evolution

摘要： 针对总拖期时间最小化的零空闲置换流水车间调度问题,提出了一种基于关键块结构的混合进化算法。该算法以遗传算法为框架,设计了依据关联规则计算染色体上基因之间关联强度的方法,以便挖掘优势染色体上的优势基因组成关键块,并在优势关键块的基础上构建具有较优解的人工染色体种群。同时,引入双精英进化机制,提高算法交叉和变异的有效性,避免算法的无效交叉。精英进化产生的子代种群依据关联规则挖掘关键块,基于交换邻域结构,结合NEH算法的思想,互换非关键块上工件之间的位置,得到局部搜索解。最后,通过对Taillard基准问题进行仿真测试,并将本文算法运行结果与其他算法进行比较,验证了算法的有效性。

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