| 新颖的阻塞流水车间调度量子差分进化算法 |
| |
| 引用本文： | 齐学梅,王宏涛,陈付龙,汤其妹,孙云翔. 新颖的阻塞流水车间调度量子差分进化算法[J]. 计算机应用, 2015, 35(3): 663-667. DOI: 10.11772/j.issn.1001-9081.2015.03.663 |
| |
| 作者姓名： | 齐学梅 王宏涛 陈付龙 汤其妹 孙云翔 |
| |
| 作者单位： | 1. 安徽师范大学 数学计算机科学学院, 安徽 芜湖 241003;2. 安徽师范大学 网络与信息安全工程技术研究中心, 安徽 芜湖 241003 |
| |
| 基金项目： | 国家自然科学基金资助项目(61370050);安徽省自然科学基金资助项目(1308085QF118);安徽师范大学创新基金资助项目(2013CXJJ01);安徽师范大学研究生“千人培养计划”项目(151416) |
| |
| 摘 要： | 针对阻塞流水车间调度问题(BFSP),提出了一种新颖的量子差分进化(NQDE)算法,用于最小化最大完工时间。该算法将量子进化算法(QEA)与差分进化(DE)相结合,设计一种新颖的量子旋转机制控制种群进化方向,增强种群多样性;采用高效的基于变邻域搜索的量子进化算法(QEA-VNS)协同进化策略增强算法的全局搜索能力,进一步提高解的质量。基于Taillard's benchmark实例仿真,结果表明,所提算法在最优解数量上明显高于目前较好的启发式算法--INEH,改进了110个实例中64个实例的当前最优解;在性能上也优于目前有效的元启发式算法--新型蛙跳算法(NMSFLA)和混合量子差分进化(HQDE),产生最优解的平均百分比偏差(ARPD)均下降约6%。NQDE算法适合大规模阻塞流水车间调度问题。
|
| 关 键 词： | 阻塞流水车间调度 量子进化算法 差分进化 协同进化 最大完工时间 |
| 收稿时间： | 2014-10-13 |
| 修稿时间： | 2014-11-14 |
Novel quantum differential evolutionary algorithm for blocking flowshop scheduling |
| |
| 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. DOI: 10.11772/j.issn.1001-9081.2015.03.663 |
| |
| Authors: | QI Xuemei WANG Hongtao CHEN Fulong TANG Qimei SUN Yunxiang |
| |
| Affiliation: | 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 |
| |
| 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. |
| |
| Keywords: | blocking flowshop scheduling Quantum Evolutionary Algorithm (QEA) Differential Evolution (DE) co-evolution makespan |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
|
