Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (22): 236-243.DOI: 10.3778/j.issn.1002-8331.1908-0462

Previous Articles     Next Articles

Genetic-Variable Neighborhood Search Algorithm with Elite Protection Strategy for Flexible Job Shop Scheduling Problem

WU Shujing, YOU Youpeng, LUO Fuyuan   

  1. College of Mechatronics, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
  • Online:2020-11-15 Published:2020-11-13



  1. 南京航空航天大学 机电学院,南京 210016


Aiming at single-objective Flexible Job Shop Scheduling Problem(FJSP)with the objective of optimizing the maximum completion time, a hybrid algorithm incorporating genetic algorithm, variable neighborhood search and elite protection strategy is proposed. Firstly, the mathematical model is established and the overall flow of the algorithm is presented. Then, the genetic operator is improved and the improved memory base is added to protect the elite individuals. Secondly, based on the critical operations adjustment, three neighborhood structures are designed to enhance the local search ability, which are same-machine moving operation, cross-machine moving operation and double operations adjustment. Finally, the benchmark examples and numerical experiments are used to test and verify the effectiveness of the proposed method.

Key words: Flexible Job Shop Scheduling Problem(FJSP), genetic algorithm, variable neighborhood search, elite protection strategy



关键词: 柔性作业车间调度(FJSP), 遗传算法, 变邻域搜索, 精英保护策略