量子萤火虫算法及在无等待流水调度上的应用  

Quantum Glowworm Swarm Algorithm and Its Application to No-wait Flowshop Scheduling

作　　者：齐学梅[1,2] 王宏涛[1,2] 杨洁[1,2] 汤其妹 陈付龙[1,2] 叶和平[1,2] 

机构地区：[1]安徽师范大学数学计算机科学学院,安徽芜湖241003 [2]安徽师范大学网络与信息安全工程技术研究中心,安徽芜湖241003

出　　处：《信息与控制》2016年第2期211-217,共7页Information and Control

基　　金：国家自然科学基金资助项目(61370050;61572036);安徽省高校自然科学重点研究基金资助项目(KJ2016A272)

摘　　要：针对无等待流水车间调度问题,提出了一种新颖的量子萤火虫优化算法用于最小化总完工时间.首先,将量子进化机制嵌入萤火虫算法中,并设计一种快速的局部邻域搜索方法,在每次迭代时只搜索部分邻域,同时采用目标增量计算邻域解变化,这样极大地加快了算法迭代速度,加速了算法收敛.最后,应用Taillard基准测试实例仿真,与目前较优的启发式算法IHA(improved heuristic algorithm)和群智能算法DGSO(discrete glowworm swarm optimization)、GA-VNS(genetic algorithm-variable neighborhood search)及DHS(discrete harmony search)相比较,产生最好解的平均百分比偏差均下降了40%以上.实验结果验证了所提算法在求解无等待流水调度中的优越性.We propose a novel quantum glowworm swarm optimization algrorithm for minimizing total flow time in no-wait flowshop scheduling. First,we embed the quantum evolutionary mechanism into the glowworm swarm algorithm.Then,we design a fast local neighborhood search algorithm to search the partial neighborhood of each iteration and calculate a neighborhood solution with a target increment. This algorithm not only greatly improves the solution quality,but also increase the speed of convergence. Based on Taillard＇s benchmark simulation,the results show that the average relative percentage deviation from the best-known solution is reduced by more than 40%,compared with the optimal heuristic algorithm IHA and the swarm intelligence algorithms DGSO,GA-VNS,and DHS. These experimental results verify the superiority of the proposed algorithm in performing no-wait flowshop scheduling.

关 键 词：萤火虫优化 量子进化 局部邻域搜索 无等待流水调度 总完工时间 

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