|
|
|
Discrete quantum-behaved particle swarm optimization
for job-shop scheduling |
| ZHANG Jian-ming, XIE Lei, MAO Jing-min, DONG Fang |
Institute of CyberSystems and Control, State Key Laboratory of Industrial Control Technology,
Zhejiang University, Hangzhou 310027, China |
|
|
|
Abstract A novel discrete quantum-behaved particle swarm optimization (DQPSO) approach was proposed to address Job-shop scheduling (JSP) problem. JSP is a complex combinatorial optimization problem with many variations, and it is strong nondeterministic polynomial time (NP)-complete. The proposed DQPSO approach utilized the principle of quantum-PSO and described the particle positions with quantum wave function. Crossover and mutation operators in GA were involved which makes DQPSO applicable for searching in combinatorial space directly.In addition, a new two-layer local searching algorithm was also incorporated into the DQPSO algorithm. The two-layer local searching algorithm randomly generated new particles around the local optimums, which in turn updated solutions with high quality and diversity.The application demonstrated that DQPSO can achieve better results on most benchmark scheduling problems．
|
|
Published: 01 May 2012
|
|
|
基于离散量子微粒群优化的作业车间调度
针对强非确定性多项式难的作业车间调度(JSP)问题,提出一种离散量子微粒群优化算法(DQPSO).该算法基于量子态波函数描述微粒群粒子位置,结合遗传算法中的交叉、变异操作,采用随机键编码方法对连续空间内的解进行离散化,使得DQPSO能够直接用于求解车间生产调度这类组合优化问题.另外,针对JSP的复杂性,通过引入2层结构的局部搜索策略,构造在局部优化解附近不同搜索半径的微粒,增强算法的搜索能力,进一步提高解的多样性和寻优质量.应用结果表明,对大部分作业车间调度测试算例,DQPSO表现出更有效的寻优性能.
|
|
| ［1］ RODAMMER F A,WHITE K P. A recent survey of production scheduling ［J］. Systems, Man and Cybernetics, IEEE Transactions on, 1988. 18(6): 841-851．
［2］ WANG Y, CHEN H P,SHAO H. Minimizing makespan for parallel batch processing machines with nonidentical job sizes using quantumbehaved particle swarm optimization ［J］. Intelligent Decision Making Systems, 2010. 2(1): 32-39．
［3］ EBERHART R,KENNEDY J. A new optimizer using particle swarm theory ［C］ ∥Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Nagoya: IEEE press, 1995: 39-43．
［4］ SUN J, XU W,FENG B. A global search strategy of quantumbehaved particle swarm optimization ［C］ ∥Cybernetics and Intelligent Systems, 2004 IEEE Conference on. Singapore: IEEE press, 2004: 111-116．
［5］ ZHOU D, SUN J, LAI C H, et al. An improved quantumbehaved particle swarm optimization and its application to medical image registration ［J］. International Journal of Computer Mathematics, 2011. 88(6): 1208-1223．
［6］ TIAN N, SUN J, XU W B, et al. An improved quantumbehaved particle swarm optimization with perturbation operator and its application in estimating groundwater contaminant source ［J］. Inverse Problems in Science and Engineering, 2011. 19(2): 181-202．
［7］ SUN C F,LU S F. Shortterm combined economic emission hydrothermal scheduling using improved quantumbehaved particle swarm optimization ［J］. Expert Systems with Applications, 2010. 37(6): 4232-4241．
［8］ COELHO L D. Gaussian quantumbehaved particle swarm optimization approaches for constrained engineering design problems ［J］. Expert Systems with Applications, 2010. 37(2): 1676-1683．
［9］ HUANG Z, WANG Y J, YANG C J, et al. A new improved quantumbehaved particle swarm optimization model ［C］ ∥2009 4th Ieee Conference on Industrial Electronics and Applications. Xi’an: IEEE press, 2009: 1551-1555．
［10］ BEAN J C. Genetic algorithms and random keys for sequencing and optimization ［J］. ORSA Journal on Computing, 1994. 6(2): 154-160．
［11］ MURATA T, ISHIBUCHI H,TANAKA H. Genetic algorithms for flowshop scheduling problems ［J］. Computers & Industrial Engineering, 1996. 30(4): 1061-1071．
［12］ DUAN H B,XING Z H. Improved quantum evolutionary computation based on particle swarm optimization and twocrossovers ［J］. Chinese Physics Letters, 2009. 26(12): 147-153．
［13］ CHENG H C, CHIANG T C,FU L C. A twostage hybrid memetic algorithm for multiobjective job shop scheduling ［J］. Expert Systems with Applications, 2011. 38(9): 10983-10998．
［14］ WANG L,ZHENG D Z. An effective hybrid optimization strategy for jobshop scheduling problems ［J］. Computers & Operations Research, 2001. 28(6): 585-596．
［15］ SHA D Y,HSU CY. A hybrid particle swarm optimization for job shop scheduling problem ［J］. Computers & Industrial Engineering, 2006. 51(4): 791-808. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
