计算机应用 ›› 2019, Vol. 39 ›› Issue (11): 3250-3256.DOI: 10.11772/j.issn.1001-9081.2019040700

• 人工智能 • 上一篇    下一篇

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

陈林烽1,2, 齐学梅1,2, 陈俊文1,2, 黄琤1,2, 陈付龙1,2   

  1. 1. 安徽师范大学 计算机与信息学院, 安徽 芜湖 241002;
    2. 网络与信息安全安徽省重点实验室(安徽师范大学), 安徽 芜湖 241002
  • 收稿日期:2019-04-24 修回日期:2019-06-18 出版日期:2019-11-10 发布日期:2019-08-21
  • 通讯作者: 齐学梅
  • 作者简介:陈林烽(1992-),男,安徽六安人,硕士研究生,主要研究方向:量子计算、智能调度;齐学梅(1963-),女,安徽安庆人,教授,硕士,主要研究方向:量子计算、智能调度;陈俊文(1996-),女,安徽宣城人,硕士研究生,主要研究方向:量子计算、数据挖掘;黄琤(1995-),男,安徽滁州人,硕士研究生,CCF会员,主要研究方向:信息物理融合系统、物联网安全;陈付龙(1978-),男,安徽六安人,教授,博士,CCF会员,主要研究方向:嵌入式与普适计算、信息物理融合系统。
  • 基金资助:
    国家自然科学基金资助项目(61572036)。

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

CHEN Linfeng1,2, QI Xuemei1,2, CHEN Junwen1,2, HUANG Cheng1,2, CHEN Fulong1,2   

  1. 1. School of Computer and Information, Anhui Normal University, Wuhu Anhui 241002, China;
    2. Anhui Provincial Key Laboratory of Network and Information Security(Anhui Normal University), Wuhu Anhui 241002, China
  • Received:2019-04-24 Revised:2019-06-18 Online:2019-11-10 Published:2019-08-21
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61572036).

摘要: 为了求解批量流水调度问题(LFSP)的最小化最大完工时间,提出一种量子候鸟协同优化(QMBCO)算法。首先,采用Bloch量子球面编码方案扩大解空间;然后,运用FL算法优化初始解,以弥补传统随机初始解的不足,保证初始种群具有较高的质量;最后,使用候鸟优化(MBO)算法及变邻域搜索(VNS)算法进行迭代,增强算法的全局搜索能力。采用随机生成不同规模的实例仿真,将QMBCO算法与目前较优的离散粒子群优化(DPSO)算法、MBO算法和量子布谷鸟协同搜索(QCCS)算法相比较。结果表明,在两种不同运行时间下QMBCO与DPSO、MBO、QCCS相比产生的最优解平均百分比偏差(ARPD)分别平均下降65%、34%和24%,证明了QMBCO算法的有效性和高效性。

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

Abstract: 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.

Key words: Lot-streaming Flow shop Scheduling Problem (LFSP), makespan, Migrating Birds Optimization (MBO) algorithm, quantum coding based on Bloch coordinates, Variable Neighborhood Search (VNS) algorithm, Average Relative Percentage Deviation (ARPD)

中图分类号: