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

摘要： 针对置换流水车间调度问题，以最小化总流水时间为目标，提出了一种新颖的两阶段分布估计算法。第一阶段先利用NEH（Nawaz-Enscore-Ham，NEH）启发式构造一个较优的初始个体，然后随机生成初始种群，为保留种群的多样性，提出一种择优机制来选择个体并建立概率模型，同时在当代种群中利用精英机制保留当代种群中的最优解，最后利用概率模型采样并生成下一代种群。第二阶段采用插入、互换操作算子对第一阶段得到的最优解进行邻域搜索，来提高分布估计算法的全局搜索能力，阻止其陷入局部最优解。通过对算例进行实验、对比和分析，证明该算法的可行性和有效性。

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