一种求解FlowShop调度问题的混合量子进化算法*

作者：王小芹，王万良，徐新黎 日期：2009-11-16/span> 浏览：3829 查看PDF文档

一种求解FlowShop调度问题的混合量子进化算法*

王小芹，王万良，徐新黎
（浙江工业大学 信息工程学院，浙江 杭州 310032）

摘要：针对FlowShop调度问题，在量子进化算法的基础上，提出了一种求解置换流水车间调度问题的混合量子进化算法（HQEA），融合了量子进化算法和经典遗传算法的优点，并提出了一种新的针对置换流水车间调度问题的解码方法和一种新的量子门更新旋转角策略，最后针对一系列典型置换流水车间调度问题进行了对比仿真。研究结果表明，所提出的混合量子进化算法HQEA具有良好的全局搜索能力和较快的收敛速度。
关键词：量子进化算法；遗传算法；流水车间调度；置换流水车间调度问题
中图分类号：TP278文献标识码：A文章编号：1001-4551(2009)09-0005-04

Hybrid quantum inspired evolutionary algorithm for flowshop scheduling problem
WANG Xiaoqin, WANG Wanliang, XU Xinli
（College of Information Engineering, Zhejiang University of Technology, Hangzhou 310032, China）
Abstract: Aiming at flowshop scheduling problem, based on the quantum inspired evolutionary algorithm(QEA), a hybrid quantuminspired evolutionary algorithm(HQEA) was proposed for the permutation flowshop scheduling problem(PFSP) and merged the good features of QEA and traditional genetic algorithm(GA). A new decoding method for the PFSP and a new quantum gate update rotation angle strategy were applied to HQEA. Comparing experiments had been simulated on a series of wellknow PFSP, and the results show that the proposed HQEA has good global searching ability and rapid rate of convergence.
Key words: quantum inspired evolutionary algorithm(HQEA); genetic algorithm(GA); flowshop scheduling; permutation flow shop scheduling problem(FFSP)
参考文献(References):
［1］NARAYANAN A, MOORE M. Quantuminspired Genetic Algorithms［C］//IEEE International conference on Evolutionary Computation. Piscataway: ［s.n.］,1996:61-66.
［2］HAN K H. Genetic Quantum Algorithm and its Application to Combinatorial Optimization Problem［C］//Congress on Evolutionary Computation. San Diego: ［s.n.］,2000:1354-1360.
［3］HAN K H, KIM J H. Quantuminspired Evolutionary Algorithm for a Class of Combinatorial Optimization［J］. IEEE Trans. on Evolutionary Computation,2002,6(6):580-593.
［4］HAN K H, KIM J H. Quantuminspired evolutionary algorithms with a new termination criterion, Hε gate, and twophase scheme［J］. IEEE Transactions on Evolutionary Computation,2004,8(2):156-169.
［5］杨淑媛,焦李成,刘芳.量子进化算法［J］.工程数学学报,2006,23(2):235-246.
［6］王凌.量子进化算法研究进展［J］.控制与决策,2008,23(12):1321-1326.
［7］WANG L, WU H, ZHENG D Z. A quantuminspired genetic algorithm for scheduling problems［J］. Lecture Notes in Computer Science,2005,3612(PART Ⅲ):417-423.
［8］WANG L, WU H, TANG F. A Hybrid QuantumInspired Genetic Algorithm for Flow Shop Scheduling［J］. Lecture Notes in Computer Science,2005,3645(PART Ⅱ):636-644.
［9］LI B B, WANG L. A Hybrid QuantumInspired Genetic Algorithm for Multiobjective Flow Shop Scheduling［J］. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics,2007,37(3):576-591.
［10］ZOBOLAS G I, TARANTILIS C D, IOANNOU G. Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algoritm［J］. Computers and Operations Research,2009,36(4):1249-1267.
［11］CARLIER. Jacques ordonnancements a contraintes disjonctives［J］. Recherche Operationelle/Operations Research,1978,12（4）:333-350.
［12］REEVES C R. A genetic algorithm for flowshop sequencing［J］. Computers and Operations Research,1995,22（1）:5-13.