Abstract: Aiming at the blocking flow shop scheduling problem with minimized makespan,an effective population-based multi-layer iterated greedy algorithm was proposed.The permutation based encoding schemes was designed in the algorithm,and Nawaz-Enscore-Ham & Profile Fitting (NEH_PF) algorithm was proposed to construct the initial population for improving the quality of initial results.To enhance the local search abilities of individuals,a multi-layer iterated greedy algorithm was designed,together with the interchange and insert strategies to mutate individuals and path-relinking strategies to cross the individuals.The partly crossing policy was put forward to update the populations.The effectiveness of proposed algorithm was validated through a group of benchmark instances.

Key words: population, iterated greedy algorithm, blocking flow shop scheduling, minimized makespan

摘要： 针对以最小化最大完工时间为目标的阻塞流水车间调度问题,提出一种有效的基于种群的多层次迭代贪婪算法进行求解。算法基于排列形式进行编码,提出NEH_PF(Nawaz-Enscore-Ham & profile fitting)算法构造初始种群,以提高初始解的质量;设计了多层次迭代贪婪算法,并基于插入、交换策略对个体进行变异,基于Path-Relinking算法对个体进行交叉,以提高个体局部搜索能力,并提出部分交叉策略来更新种群。通过标准实例测试,验证了所提算法的有效性。

关键词: 种群, 迭代贪婪算法, 阻塞流水车间调度, 最小化最大完工时间