求解零等待流水线调度问题的离散磷虾群算法  

A Discrete Krill Herd Algorithm for the No-wait Flow Shop Scheduling Problem

作　　者：刘长平 简祯富[2] 傅文翰 Liu Changping;Jian Zhenfu;Fu Wenhan(Faculty of Management Engineering,Huaiyin Institute of Technology,Huaian 223200,China;Department of Industrial Engineering and Engineering Management,National Tsing Hua University,Hsinchu 30013,China;Jiangsu Smart Factory Engineering Research Center,Huaian 223003,China)

机构地区：[1]淮阴工学院管理工程学院,江苏淮安223200 [2]清华大学工业工程与工程管理系,台湾新竹30013 [3]江苏省智能工厂工程研究中心,江苏淮安223003

出　　处：《系统仿真学报》2020年第6期1051-1059,共9页Journal of System Simulation

基　　金：国家自然科学基金(71761027);教育部人文社会科学规划基金(16YJA630032)。

摘　　要：针对最小化最大完工时间零等待流水车间调度问题,设计了一种离散磷虾群优化算法进行求解。根据优化问题特性,定义了算法中虚拟食物的计算方法,规定了虚拟食物影响下磷虾个体之间的交叉规则;提出了个体间的距离计算方式,从而可以界定邻域范围实现个体信息交流;进一步采用交换、逆序、插入等策略来提高算法的局部搜索能力,同时借助多种初始化策略来提高初始种群的质量和多样性。通过典型算例的仿真测试和对比,验证了所设计算法的有效性和鲁棒性。A discrete krill herd algorithm(DKH)is proposed to solve the no-wait flow shop scheduling problem(NWFSP)with the makespan criterion.Based on the characteristics of the optimization mechanism,the notion of“virtual food”in krill herd algorithm and the influenced crossover rules between krill individuals are defined.The concept and calculation method of the individual distance are redefined to measure the neighborhood range to realize the information exchange.The local search strategies of random swap,inverse and insert operator are employed to enhance the local search ability of DKH,and the multiple initialization strategies are redesigned to promote the qualities and diversities of the initial populations.Simulation results on the benchmark instances shows the effectiveness and robustness of the DKH.

关 键 词：离散磷虾群优化算法 优化机理 零等待流水车间调度 最小化完工时间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] N945[自动化与计算机技术—计算机科学与技术]