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

Abstract:

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), 遗传算法, 变邻域搜索, 精英保护策略