变邻域保优遗传算法求解柔性车间调度问题  

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

作　　者：吴树景 游有鹏[1] 罗福源[1] WU Shujing;YOU Youpeng;LUO Fuyuan(College of Mechatronics,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

机构地区：[1]南京航空航天大学机电学院,南京210016

出　　处：《计算机工程与应用》2020年第22期236-243,共8页Computer Engineering and Applications

基　　金：江苏省自然科学基金优秀青年基金(No.BK20160084);中央高校基本科研业务费专项资金(No.NS2016056)。

摘　　要：针对单目标柔性作业车间调度问题,以最大完工时间为优化目标,将遗传算法、变邻域搜索算法与精英保护策略相结合,提出一种运算效率和求解性能均较好的混合算法。首先建立数学模型,阐述算法的整体流程。对遗传算子进行改进,并添加改良的保优记忆库对精英个体进行保护。基于关键工序调整,设计了“同机器工序调整”“变机器工序调整”“双工序调整”三种邻域结构,增强了局部搜索能力,并给出一种高效的关键工序寻找法则。通过对基准算例及数值实验的测试,验证了该算法的有效性和可行性。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.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301[自动化与计算机技术—控制科学与工程]