Novel quantum differential evolutionary algorithm for blocking flowshop scheduling

doi:10.11772/j.issn.1001-9081.2015.03.663

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (3): 663-667.DOI: 10.11772/j.issn.1001-9081.2015.03.663

Previous Articles Next Articles

Novel quantum differential evolutionary algorithm for blocking flowshop scheduling

QI Xuemei^1,2, WANG Hongtao^1,2, CHEN Fulong^1,2, TANG Qimei^1,2, SUN Yunxiang^1,2

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

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

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

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

通讯作者: 齐学梅
作者简介:齐学梅(1963-),女,安徽桐城人,副教授,硕士,主要研究方向:智能计算、量子计算;王宏涛(1989-),男,安徽舒城人,硕士研究生,主要研究方向:智能算法优化;陈付龙(1978-),男,安徽霍邱人,副教授,博士,主要研究方向:嵌入式计算、智能计算、信息物理融合系统
基金资助:
国家自然科学基金资助项目(61370050);安徽省自然科学基金资助项目(1308085QF118);安徽师范大学创新基金资助项目(2013CXJJ01);安徽师范大学研究生"千人培养计划"项目(151416)

Abstract

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

摘要：

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

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

CLC Number:

TP301.6

QI Xuemei, WANG Hongtao, CHEN Fulong, TANG Qimei, SUN Yunxiang. Novel quantum differential evolutionary algorithm for blocking flowshop scheduling[J]. Journal of Computer Applications, 2015, 35(3): 663-667.

齐学梅, 王宏涛, 陈付龙, 汤其妹, 孙云翔. 新颖的阻塞流水车间调度量子差分进化算法[J]. 计算机应用, 2015, 35(3): 663-667.

References

[1] HAN W, CUI Z, GU X. Blocking flow shop based on a new frog leaping algorithm[J]. Journal of East China University of Science and Technology, 2014,40(1):86-90. (韩炜,崔喆,顾幸生.基于新型蛙跳算法的带阻塞流水线调度问题[J].华东理工大学学报,2014,40(1):86-90.)
[2] DENG G, XU Z, GU X. A discrete artificial bee colony algorithm for minimizing the total flow time in the blocking flow shop scheduling[J]. Chinese Journal of Chemical Engineering, 2012,20(6):1067-1073.
[3] GRABOWSKI J, PEMPERA J. The permutation flowshop problem with blocking: a tabu search approach[J]. Omega, 2007,35(3):302-311.
[4] WANG L, PAN Q-K, TASGETIREN M F. Minimizing the total flow time in a flow shop with blocking by using hybrid harmony search algorithms[J]. Expert Systems with Applications, 2010,37(12):7929-36.
[5] ZHANG Q, CHEN Y. Hybrid particle swarm optimization algorithm for hybrid flow shop scheduling problem with blocking[J]. Information and Control, 2013,42(2):252-257.(张其亮,陈永生.带有阻塞限制的混合流水车间调度问题的混合粒子群求解算法[J].信息与控制,2013,42(2):252-257.)
[6] WANG L. Advances in quantum-inspired evolutionary algorithms[J]. Control and Decision, 2008,23(12):1321-1326.(王凌.量子进化算法研究进展[J].控制与决策,2008,23(12):1321-1326.)
[7] LI P, CHAI Y, XIONG Q. Quantum gate Elman neural network and its quantized extended gradient back-propagation training algorithm[J]. Acta Automatica Sinica, 2013,39(9):1511-1522.(李鹏华,柴毅,熊庆宇.量子门Elman神经网络及其梯度扩展的量子反向传播学习算法[J].自动化学报,2013,39(9):1511-1522.)
[8] WANG D, CHEN H, ZHU W, et al. Unitary matrix of multiple-valued quantum permutation gate[J]. Chinese Journal of Computers, 2012,35(3):639-644.(王东,陈汉武,朱皖宁,等.多值逻辑量子置换门的酉矩阵表示[J].计算机学报,2012,35(3):639-644.)
[9] LIU C, GEN H, LIU W. Secure quantum communication protocol based on symmetric W state and identity authentication[J]. Journal of Computer Applications, 2014,34(2):438-441.(刘超,耿焕同,刘文杰. 基于对称W态和身份认证的安全量子通信协议[J].计算机应用,2014,34(2):438-441.)
[10] REN Z, XIONG R, CHU J. Hybrid quantum differential evolutionary algorithm and its applications[J]. Control Theory and Applications, 2011,28(10):1349-1355.(任子武,熊蓉,褚健.混合量子差分进化算法及应用[J].控制理论与应用,2011,28(10):1349-1355.)
[11] DRAA A, MESHOUL S, TALBI H, et al. A quantum-inspired differential evolution algorithm for solving the N-queens problem[J]. The International Arab Journal of Information Technology, 2010,7(1):21-27.
[12] ZHENG T, YAMASHIRO M. Solving flow shop scheduling problems by quantum differential evolutionary algorithm[J]. International Journal of Advanced Manufacturing Technology, 2010,49:643-662.
[13] QI X, WANG H, CHEN F, et al. Improved genetic algorithm for multi-objective of PFSP[EB/OL].[2014-08-02]. http://www.cnki.net/kcms/doi/10.3778/j.issn.1002%A9%5C8331.1310%A9%5C0197.html.(齐学梅,王宏涛,陈付龙,等.求解多目标PFSP问题的改进遗传算法[EB/OL].[2014-08-02]. http://www.cnki.net/kcms/doi/10.3778/j.issn.1002%A9%5C8331.1310%A9%5C0197.html.)
[14] QIAN B, WANG L, HU R, et al. A DE-based approach to no-wait flow-shop scheduling[J]. Computers and Industrial Engineering, 2009,57(3):787-805.
[15] DAS S, ABRAHAM A, KONAR A. Particle swarm optimization and differential evolution algorithms: technical analysis, applications and hybridization perspectives[J]. Studies in Computational Intelligence, 2008,116:1-38.
[16] JARBOUI B, EDDALY M, SIARRY P. An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems[J]. Computers and Operations Research, 2009,36(9):2638-2646.
[17] TAILLARD E. Benchmarks for basic scheduling programs[J]. European Journal of Operational Research, 1993,64(2):278-285.
[18] QI X, LI X, WANG Q. Hybrid tabu search algorithms for permutation flow shops to minimize total flowtime[J]. Journal of Southeast University: Natural Science Edition, 2008,38(6):960-964.(齐学梅,李小平,王茜.最小化总完工时间的流水作业调度混合算法[J].东南大学学报:自然科学版,2008,38(6):960-964.)
[19] PAN Q-K, WANG L. Effective heuristics for the blocking flow shop scheduling problem with makespan minimization[J]. Omega, 2012,40(2):218-229.

Novel quantum differential evolutionary algorithm for blocking flowshop scheduling

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	JIA Heming, JIANG Zichao, LI Yao, SUN Kangjian. Simultaneous feature selection optimization based on improved spotted hyena optimizer algorithm [J]. Journal of Computer Applications, 2021, 41(5): 1290-1298.
[2]	CHEN Linfeng, QI Xuemei, CHEN Junwen, HUANG Cheng, CHEN Fulong. Quantum-inspired migrating birds co-optimization algorithm for lot-streaming flow shop scheduling problem [J]. Journal of Computer Applications, 2019, 39(11): 3250-3256.
[3]	FENG Shuaidong, CHEN Lijia, LIU Mingguo. Random structure based design method for multiplierless ⅡR digital filters [J]. Journal of Computer Applications, 2018, 38(9): 2621-2625.
[4]	ZHANG Xin, ZOU Dexuan, SHEN Xin. Hybrid two-norm particle swarm optimization algorithm with crossover term [J]. Journal of Computer Applications, 2018, 38(8): 2148-2156.
[5]	LIU Bao, DONG Minggang, JING Chao. Multi-objective differential evolution algorithm with improved ranking-based mutation [J]. Journal of Computer Applications, 2018, 38(8): 2157-2163.
[6]	YUAN Yichuan, YANG Zhou, LUO Tingxing, QIN Jin. Multi-population-based competitive differential evolution algorithm for dynamic optimization problem [J]. Journal of Computer Applications, 2018, 38(5): 1254-1260.
[7]	LI Longshu, WENG Qingqing. Self-adaptive differential evolution algorithm based on opposition-based learning [J]. Journal of Computer Applications, 2018, 38(2): 399-404.
[8]	ZHANG Qiang, ZOU Dexuan, GENG Na, SHEN Xin. Adaptive differential evolution algorithm based on multiple mutation strategies [J]. Journal of Computer Applications, 2018, 38(10): 2812-2821.
[9]	ZHANG Bin, LI Yanhui, GUO Hao. Cross-population differential evolution algorithm based on opposition-based learning [J]. Journal of Computer Applications, 2017, 37(4): 1093-1099.
[10]	DONG Xiaogang, DENG Changshou, TAN Yucheng, PENG Hu, WU Zhijian. Cooperative differential evolution algorithm for large-scale optimization problems [J]. Journal of Computer Applications, 2017, 37(11): 3219-3225.
[11]	LI Kangshun, ZUO Lei, LI Wei. Novel differential evolution algorithm based on simplex-orthogonal experimental design [J]. Journal of Computer Applications, 2016, 36(1): 143-149.
[12]	WANG Shenwen, ZHANG Wensheng, QIN Jin, XIE Chengwang, GUO Zhaolu. Naïve differential evolution algorithm [J]. Journal of Computer Applications, 2015, 35(5): 1333-1335.
[13]	REN Xiuli, WANG Chong. Multi-path routing protocol based on three-dimensional space and regional co-evolution in wireless sensor network [J]. Journal of Computer Applications, 2015, 35(3): 610-614.
[14]	YUAN Lei, LIANG Dingwen, CAI Zhihua, WU Zhao, GU Qiong. Short-term traffic flow prediction algorithm based on orthogonal differential evolution unscented Kalman filter [J]. Journal of Computer Applications, 2015, 35(11): 3151-3156.
[15]	MA Zhenyuan, YE Shujin, LIN Zhiyong, LIANG Yubin, HUANG Han. Enhanced differential evolution algorithm with non-prior-knowledge DFP local search under Memetic framework [J]. Journal of Computer Applications, 2015, 35(10): 2766-2770.