批量流水调度问题的量子候鸟协同优化算法  

Quantum-inspired migrating birds co-optimization algorithm for lot-streaming flow shop scheduling problem

作　　者：陈林烽 齐学梅 陈俊文[1,2] 黄琤 陈付龙 CHEN Linfeng;QI Xuemei;CHEN Junwen;HUANG Cheng;CHEN Fulong(School of Computer and Information,Anhui Normal University,Wuhu Anhui 241002,China;Anhui Provincial Key Laboratory of Network and Information Security(Anhui Normal University),Wuhu Anhui 241002,China)

机构地区：[1]安徽师范大学计算机与信息学院,安徽芜湖241002 [2]网络与信息安全安徽省重点实验室(安徽师范大学),安徽芜湖241002

出　　处：《计算机应用》2019年第11期3250-3256,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61572036)~~

摘　　要：为了求解批量流水调度问题(LFSP)的最小化最大完工时间,提出一种量子候鸟协同优化(QMBCO)算法。首先,采用Bloch量子球面编码方案扩大解空间;然后,运用FL算法优化初始解,以弥补传统随机初始解的不足,保证初始种群具有较高的质量;最后,使用候鸟优化(MBO)算法及变邻域搜索(VNS)算法进行迭代,增强算法的全局搜索能力。采用随机生成不同规模的实例仿真,将QMBCO算法与目前较优的离散粒子群优化(DPSO)算法、MBO算法和量子布谷鸟协同搜索(QCCS)算法相比较。结果表明,在两种不同运行时间下QMBCO与DPSO、MBO、QCCS相比产生的最优解平均百分比偏差(ARPD)分别平均下降65%、34%和24%,证明了QMBCO算法的有效性和高效性。A Quantum-inspired Migrating Birds Co-Optimization(QMBCO)algorithm was proposed for minimizing the makespan in Lot-streaming Flow shop Scheduling Problem(LFSP).Firstly,the quantum coding based on Bloch coordinates was applied to expand the solution space.Secondly,an initial solution improvement scheme based on Framinan-Leisten(FL)algorithm was used to makeup the shortage of traditional initial solution and construct the random initial population with high quality.Finally,Migrating Birds Optimization(MBO)and Variable Neighborhood Search(VNS)algorithm were applied for iteration to achieve the information exchange between the worse individuals and superior individuals in proposed algorithm to improve the global search ability.A set of instances with different scales were generated randomly,and QMBCO was compared with Discrete Particle Swarm Optimization(DPSO),MBO and Quantum-inspired Cuckoo Co-Search(QCCS)algorithms on them.Experimental results show that compared with DPSO,MBO and QCCS,QMBCO has the Average Relative Percentage Deviation(ARPD)averagely reduced by 65%,34%and 24%respectively under two types of running time,verifying the effectiveness and efficiency of the proposed QMBCO algorithm.

关 键 词：批量流水调度问题 最大完工时间 候鸟优化算法 Bloch量子球面编码 变邻域搜索算法 平均百分比偏差 

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