Please wait a minute...
J4  2012, Vol. 46 Issue (5): 842-847    DOI: 10.3785/j.issn.1008-973X.2012.05.011
自动化技术、电气工程     
基于离散量子微粒群优化的作业车间调度
张建明, 谢磊, 毛婧敏, 董方
浙江大学 智能系统与控制研究所,工业控制技术国家重点实验室,浙江 杭州 310027
Discrete quantum-behaved particle swarm optimization
for job-shop scheduling
ZHANG Jian-ming, XIE Lei, MAO Jing-min, DONG Fang
Institute of CyberSystems and Control, State Key Laboratory of Industrial Control Technology,
Zhejiang University, Hangzhou  310027, China
 全文: PDF  HTML
摘要:

针对强非确定性多项式难的作业车间调度(JSP)问题,提出一种离散量子微粒群优化算法(DQPSO).该算法基于量子态波函数描述微粒群粒子位置,结合遗传算法中的交叉、变异操作,采用随机键编码方法对连续空间内的解进行离散化,使得DQPSO能够直接用于求解车间生产调度这类组合优化问题.另外,针对JSP的复杂性,通过引入2层结构的局部搜索策略,构造在局部优化解附近不同搜索半径的微粒,增强算法的搜索能力,进一步提高解的多样性和寻优质量.应用结果表明,对大部分作业车间调度测试算例,DQPSO表现出更有效的寻优性能.

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.

出版日期: 2012-05-01
:     
基金资助:

国家自然科学基金资助项目(60974100,60904039);中央高校基本科研业务费专项资金资助项目.

通讯作者: 谢磊,男,副教授.     E-mail: leix@iipc.zju.edu.cn
作者简介: 张建明(1968-),男,副教授,从事智能优化算法、控制理论等研究. E-mail: jmzhang@iipc.zju.edu.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  

引用本文:

张建明, 谢磊, 毛婧敏, 董方. 基于离散量子微粒群优化的作业车间调度[J]. J4, 2012, 46(5): 842-847.

ZHANG Jian-ming, XIE Lei, MAO Jing-min, DONG Fang. Discrete quantum-behaved particle swarm optimization
for job-shop scheduling. J4, 2012, 46(5): 842-847.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2012.05.011        http://www.zjujournals.com/eng/CN/Y2012/V46/I5/842

[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 nonidentical job sizes using quantumbehaved 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 quantumbehaved 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 quantumbehaved 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 quantumbehaved 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. Shortterm combined economic emission hydrothermal scheduling using improved quantumbehaved particle swarm optimization [J]. Expert Systems with Applications, 2010. 37(6): 4232-4241.
[8] COELHO L D. Gaussian quantumbehaved 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 quantumbehaved 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 twocrossovers [J]. Chinese Physics Letters, 2009. 26(12): 147-153.
[13] CHENG H C, CHIANG T C,FU L C. A twostage 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 jobshop scheduling problems [J]. Computers & Operations Research, 2001. 28(6): 585-596.
[15] SHA D Y,HSU CY. A hybrid particle swarm optimization for job shop scheduling problem [J]. Computers & Industrial Engineering, 2006. 51(4): 791-808.

[1] 宁志华,何乐年,胡志成. 一种高压高可靠性开关电源控制芯片[J]. J4, 2014, 48(3): 377-383.
[2] 李林,陈家旺,顾临怡,王峰. 轴向柱塞泵/马达变量阀配流机构[J]. J4, 2014, 48(1): 29-34.
[3] 陈钊,余锋,陈婷婷. 基于日志结构的闪存均衡回收策略[J]. J4, 2014, 48(1): 92-99.
[4] 蒋湛,姚晓明,林兰芬. 基于特征自适应的本体映射方法[J]. J4, 2014, 48(1): 76-84.
[5] 陈迪仕 ,张宇,李平. 微小型无人直升机地面效应建模[J]. J4, 2014, 48(1): 154-160.
[6] 霍新新,褚金奎,韩冰峰,姚斐.  基于多个压电换能器的接口电路[J]. J4, 2013, 47(11): 2038-2045.
[7] 杨鑫,许端清,杨冰. 基于不规则性的并行计算方法[J]. J4, 2013, 47(11): 2057-2064.
[8] 王玉强,张宽地,陈晓东. 胶黏钢-混凝土组合梁的界面行为数值分析[J]. J4, 2013, 47(9): 1593-1598.
[9] 崔何亮, 张丹, 施斌.  布里渊分布式传感的空间分辨率及标定方法[J]. J4, 2013, 47(7): 1232-1237.
[10] 彭勇,徐小剑. 集料分布对沥青混合料劈裂强度影响数值分析[J]. J4, 2013, 47(7): 1186-1191.
[11] 金波,陈诚,李伟. 具有半球形足端的六足机器人步态修正算法[J]. J4, 2013, 47(5): 768-774.
[12] 伍晓榕,裘乐淼,张树有,孙良峰,郭传龙. 模糊语境下的复杂系统关联FMEA方法[J]. J4, 2013, 47(5): 782-789.
[13] 钟世英, 吴晓君, 蔡武军, 凌道盛, 蒋祝金, 王顺玉. 月面软着陆足垫水平拖曳模型试验装置研制[J]. J4, 2013, 47(3): 465-471.
[14] 袁幸,朱永生,张优云,洪军,祁文昌. 基于正反问题的滚动轴承损伤程度评估[J]. J4, 2012, 46(11): 1960-1967.
[15] 杨飞,朱株,龚小谨,刘济林. 基于三维激光雷达的动态障碍实时检测与跟踪[J]. J4, 2012, 46(9): 1565-1571.