Abstract: The flow shop scheduling problem with no-wait constraints is a typical NP-hard problem.A new hybrid improved genetic algorithm was proposed to solve the problem.The improved Nawaz-Enscore-Ham(NEH) algorithm was used to enhance the initial population,which improved the diversity and quality of the initial population.The association rule was used to mine the dominant blocks on the chromosomes,and the artificial chromosomes were combined by the dominant blocks to reduce the complexity of the problem.The crossover operation adopted three crossover mechanisms: single-segment crossover,two-segment crossover and three-segment crossover to improve the global search ability of the algorithm.In the process of mutation,the idea of level set and population segmentation was introduced to divide the population into two parts,and different probability of mutation was given to ensure the effectiveness of mutation,improve the local search ability of the algorithm and avoid falling into the local optimum.To further improve the performance of genetic algorithm,a neighborhood search mechanism based on NEH was proposed,which increased the diversity of population and further improved the population quality.The performance of the algorithm was tested by standard examples.The test results showed that the proposed algorithm had better performance.

Key words: no-wait constraints, flow shop scheduling problem, genetic algorithms, NEH algorithm, association rules, dominant block

摘要： 具有零等待约束条件的流水车间调度问题是一类典型的NP难问题,针对该问题提出一种新型混合改进遗传算法进行优化求解。首先,采用改进NEH算法强化初始种群质量,提高种群的多样性。结合关联规则理论挖掘种群中的优势块,借助优势块进行人工染色体组合,以降低问题复杂度。交叉操作采用单段交叉、双段交叉和三段交叉3种交叉机制,改善算法全局搜索能力;变异过程引入水平集和种群分割的思想,将种群分割成两部分,并赋予不同的变异概率,提高算法局部搜索能力。为进一步提高遗传算法的求解性能,提出了基于NEH的邻域搜索机制,增加种群多样性,进一步提高种群质量。最后,通过实验结果和算法比较,验证了所提算法的求解性能。

关键词: 零等待约束条件, 流水车间调度问题, 遗传算法, NEH算法, 关联规则, 优势块