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

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

为了求解批量流水调度问题(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.