Abstract: Aiming at the flow shop scheduling problem with limited buffers,a Memetic algorithm based on Variable Neighborhood Search (VNS) strategy was proposed.To guarantee the quality of initial population,NEH algorithm and improved IG algorithm were used to generate some initial individuals,and partial crossover and insert mutation operators were used to design an improved VNS algorithm which could conduct the local search.In this algorithm,SA was taken as the local method to enhance the search capability of the algorithm.Thus Memetic algorithm obtained a balance between the exploration and exploitation.The computational experiments and comparisons were conducted to solve on the classic benchmark problems,and the computational results demonstrated the effectiveness of the proposed algorithm.

Key words: flow shop scheduling, limited buffer, Memetic algorithm

摘要： 针对有限缓冲区流水线调度问题,提出一种基于变邻域搜索策略的Memetic算法。在基本遗传算法中,采用NEH算法和改进IG算法产生部分初始种群,使用部分交叉算子和插入变异算子,在交叉和变异之后设计一种改进变邻域搜索方法来进行局部搜索。在该改进变邻域搜索中,将模拟退火算法作为变邻域搜索中的局部搜索方法,大大增强了算法的寻优能力,使得Memetic算法在集中搜索和分散搜索之间达到更合理的平衡。运用提出算法求解经典基准算例,并与当前先进算法比较,验证了所提算法的有效性。

关键词: 流水车间调度, 有限缓冲区, Memetic算法