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

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