关键词: 分布估计算法, 置换流水车间调度问题, NEH启发式, 择优机制, 邻域搜索

Abstract: Aiming to solve the permutation flow shop scheduling problem, minimizing the total flow time as the objective function, it proposes a novel two-stage estimation of distribution algorithm. In the first stage, it firstly uses NEH（Nawaz-Enscore-Ham, NEH） heuristic to construct a relatively optimal initial individual, and then generates initial population randomly. To keep the diversities of the population, it puts forward a preferred mechanism to select individuals and establish the probability model, and at the same time, uses elite mechanism to keep the optimal individual in the contemporary populations. Finally it uses probability model to sample and generate the next generation of population. In the second stage, it uses the insert and interchange operator to do neighborhood search around the optimal individual which is got in the first stage in order to improve the global search ability of estimation of distribution algorithm and prevent it from entrapping the local optimal. Through sufficient experiments, contrast and analysis for outcome of the examples, it proves the feasibility and effectiveness of the proposed algorithm.

Key words: estimation of distribution algorithm, permutation flowshop scheduling problem, NEH heuristics, preferred mechanism, neighborhood search