关键词: 置换流水车间, NEH算法, 关联规则, 基于区块进化算法

Abstract: To solve the permutation flowshop scheduling problem with an objective of minimizing the makespan,a Linkage Mining in Block-based Evolutionary Algorithm (LMBBEA) was improved with NEH-based methods,in which the association rules and the greedy iterative idea were both applied to help generate various artificial chromosomes with better fitness to escape from local optimal.An improved NEH algorithm was used to initialize the population instead of using the completely randomized method,so that the diversity and competitive advantage of accelerating the convergence speed could be achieved.In the stage of recombining with populations,an NEH exchange method that with diversity and global search ability was proposed,which was combined with Neighborhood Swapping (NS) that had strong local search ability to improve the quality and diversity of solutions for speeding up the convergence efficiency.The proposed NEH-LMBBEA algorithm was then implemented to solve the benchmark problems of Taillard and Reeves in OR-Library,and the numerical results showed the improvement of robustness and effectiveness of this algorithm.

Key words: permutation flowshop, NEH algorithm, association rule, block-based evolutionary algorithm