计算机应用 ›› 2015, Vol. 35 ›› Issue (3): 663-667.DOI: 10.11772/j.issn.1001-9081.2015.03.663

• 先进计算 • 上一篇    下一篇

新颖的阻塞流水车间调度量子差分进化算法

齐学梅1,2, 王宏涛1,2, 陈付龙1,2, 汤其妹1,2, 孙云翔1,2   

  1. 1. 安徽师范大学 数学计算机科学学院, 安徽 芜湖 241003;
    2. 安徽师范大学 网络与信息安全工程技术研究中心, 安徽 芜湖 241003
  • 收稿日期:2014-10-13 修回日期:2014-11-14 出版日期:2015-03-10 发布日期:2015-03-13
  • 通讯作者: 齐学梅
  • 作者简介:齐学梅(1963-),女,安徽桐城人,副教授,硕士,主要研究方向:智能计算、量子计算;王宏涛(1989-),男,安徽舒城人,硕士研究生,主要研究方向:智能算法优化;陈付龙(1978-),男,安徽霍邱人,副教授,博士,主要研究方向:嵌入式计算、智能计算、信息物理融合系统
  • 基金资助:

    国家自然科学基金资助项目(61370050);安徽省自然科学基金资助项目(1308085QF118);安徽师范大学创新基金资助项目(2013CXJJ01);安徽师范大学研究生"千人培养计划"项目(151416)

Novel quantum differential evolutionary algorithm for blocking flowshop scheduling

QI Xuemei1,2, WANG Hongtao1,2, CHEN Fulong1,2, TANG Qimei1,2, SUN Yunxiang1,2   

  1. 1. School of Mathematics and Computer Science, Anhui Normal University, Wuhu Anhui 241003, China;
    2. Network and Information Security Engineering Research Center, Anhui Normal University, Wuhu Anhui 241003, China
  • Received:2014-10-13 Revised:2014-11-14 Online:2015-03-10 Published:2015-03-13

摘要:

针对阻塞流水车间调度问题(BFSP),提出了一种新颖的量子差分进化(NQDE)算法,用于最小化最大完工时间。该算法将量子进化算法(QEA)与差分进化(DE)相结合,设计一种新颖的量子旋转机制控制种群进化方向,增强种群多样性;采用高效的基于变邻域搜索的量子进化算法(QEA-VNS)协同进化策略增强算法的全局搜索能力,进一步提高解的质量。基于Taillard's benchmark实例仿真,结果表明,所提算法在最优解数量上明显高于目前较好的启发式算法——INEH,改进了110个实例中64个实例的当前最优解;在性能上也优于目前有效的元启发式算法——新型蛙跳算法(NMSFLA)和混合量子差分进化(HQDE),产生最优解的平均百分比偏差(ARPD)均下降约6%。NQDE算法适合大规模阻塞流水车间调度问题。

关键词: 阻塞流水车间调度, 量子进化算法, 差分进化, 协同进化, 最大完工时间

Abstract:

A Novel Quantum Differential Evolutionary (NQDE) algorithm was proposed for the Blocking Flowshop Scheduling Problem (BFSP) to minimize the makespan. The NQDE algorithm combined Quantum Evolutionary Algorithm (QEA) with Differential Evolution (DE) algorithm, and a novel quantum rotating gate was designed to control the evolutionary trend and increase the diversity of population. An effective Quantum-inspired Evolutionary Algorithm-Variable Neighborhood Search (QEA-VNS) co-evolutionary strategy was also developed to enhance the global search ability of the algorithm and to further improve the solution quality. The proposed algorithm was tested on the Taillard's benchmark instances, and the results show that the number of optimal solutions obtained by NQDE is bigger than the current better heuristic algorithm-Improved Nawaz-Enscore-Ham Heuristic (INEH) evidently. Specifically, the optimal solutions of 64 instances in the 110 instances are improved by NQDE. Moreover, the performance of NQDE is superior to the valid meta-heuristic algorithm-New Modified Shuffled Frog Leaping Algorithm (NMSFLA) and Hybrid Quantum DE (HQDE), and the Average Relative Percentage Deviation (ARPD) of NQDE algorithm decreases by 6% contrasted with the latter ones. So it is proved that NQDE algorithm is suitable for the large scale BFSP.

Key words: blocking flowshop scheduling, Quantum Evolutionary Algorithm (QEA), Differential Evolution (DE), co-evolution, makespan

中图分类号: