基于改进多目标微粒群算法的模具多项目反应调度

中国机械工程 ›› 2011, Vol. 22 ›› Issue (10): 1173-1179.

基于改进多目标微粒群算法的模具多项目反应调度

张沙清;陈新度;陈庆新;陈新

广东工业大学,广州,510006

出版日期:2011-05-25 发布日期:2011-05-31
基金资助:
国家高技术研究发展计划(863计划)资助项目(2006AA04Z132)；国家自然科学基金资助项目(50675039，50875051)；广东工业大学青年基金资助项目(20062014)
National High-tech R&D Program of China (863 Program) （No. 2006AA04Z132）;
National Natural Science Foundation of China（No. 50675039，50875051）

Reactive Scheduling for Multiple Mould and Die Projects Based on Improved Multi-objective Particle Swarm Optimization

Zhang Shaqing;Chen Xindu;Chen Qingxin;Chen Xin

Guangdong University of Technology,Guangzhou,510006

Online:2011-05-25 Published:2011-05-31
Supported by:

National High-tech R&D Program of China (863 Program) （No. 2006AA04Z132）;
National Natural Science Foundation of China（No. 50675039，50875051）

摘要/Abstract

摘要：

针对模具多项目执行过程中由于可再生资源发生故障、任务拖期以及随机插入新项目而导致的调度计划变更问题，提出了一种反应调度算法。利用生灭过程理论对可再生资源的不确定性进行分析，并采用基于优先规则的拓扑排序方法构建初始调度计划，建立了以调度计划变更产生的附加费用最小以及项目加权工期之和最小为目标的多目标反应调度模型，并提出一种改进的多目标微粒群算法进行模型求解。最后，通过仿真计算分析了反应调度算法的可行性与有效性。

关键词:

任务拖期, 资源不确定, 反应调度, 多目标微粒群算法

Abstract:

This paper proposed a reactive scheduling algorithm for multiple mould and die projects to deal with multiple stochastic disruptions during projects execution including uncertain renewable resources infeasibilities due to breakdowns, multiple tasks taking longer time than planning and random arrivals of new projects. Firstly, uncertain renewable resources availabilities were analyzed with the theory of birthdead process, and an initial schedule was constructed by using topological sorting method based on priority rules. Then, a multi-objective reactive scheduling model with the optimization objects of minimizing the weighted sum duration of projects and the disruptions cost, defined as the weighted sum of the deviations between the executing schedule before reactive scheduling and a new schedule after reactive scheduling was built, and an improved multi-objective particle swarm optimization was proposed to solve it. Finally, the feasibility and reliability of the reactive scheduling algorithm were analyzed by simulations.

Key words:

task duration enlarging, uncertain resource availability, reactive scheduling, multi-objective particle swarm optimization

中图分类号:

TH166

张沙清, 陈新度, 陈庆新, 陈新.

基于改进多目标微粒群算法的模具多项目反应调度

[J]. 中国机械工程, 2011, 22(10): 1173-1179.

ZHANG Sha-Qing, CHEN Xin-Du, CHEN Qiang-Xin, CHEN Xin.

Reactive Scheduling for Multiple Mould and Die Projects Based on Improved Multi-objective Particle Swarm Optimization

[J]. China Mechanical Engineering, 2011, 22(10): 1173-1179.

参考文献

[1]Herroelen W, Leus R. Project Scheduling under Un certainty;Survey and Research Potentials[J]. Euro pean Journal of Operation Research, 2005,65 (2): 289-306.
[2]Neumann K. Scheduling of Projects with Stochastic Evolution Strueture[M]//Jozefowska J, Weglarz J. Project Scheduling-- Recent Models, Algorithms and Applications. Boston, Mass. , USA: Kluwer Aca- demic Publishers, 1999.
[3]Neumann K,Steinhardt U. GERT Nelworks and the Time- oriented Evaluation of Proiects (Lecture Notes in Economics and Mathematical Systems)[M]. New York : Springer-- Verlag, 1979.
[4]廖仁.模具虚拟企业项目调度研究 [D].广东工业大学,2003:
[5]苏志龙,陈庆新,陈新,孙健.CPC环境下的模具虚拟企业项目粗规划[J].机械工程学报,2003,39(1):38-46.
[6]李英杰[1],陈庆新[1],陈新度[1],陈新[1].多属性虚拟企业部分并行协商项目规划[J].计算机集成制造系统,2005,11(6):810-817.
[7]王延斌[1],王刚[1],赵立忠[1],高国安[1].基于蚁群算法的模具制造动态调度研究[J].计算机集成制造系统,2006,12(7):1028-1036.
[8]张沙清[1],陈新度[1],陈庆新[1],陈新[1].不确定环境下模具制造项目群随机调度[J].计算机集成制造系统,2009,15(7):1389-1396.
[9]张沙清[1],陈新度[1],陈庆新[1],陈新[1].基于多步Q学习的模具制造项目群随机调度算法[J].中国机械工程,2009(12):1439-1445.
[10]程序[1],吴澄[1].粒子群优化算法求解多模式项目再调度问题[J].计算机集成制造系统,2009,15(1):97-101.
[11]Lambrechts O, Demeulemeester E, Herroelen W. Proactive and Reactive Strategies for Resource-- constrained Project Scheduling with Uncertain Re- source Availabilities[J]. Journal of Scheduling, 2008,2(11) :121-136.
[12]Vonder S, Demeulemeester E, Herroelen W, et al. The Trade--off between Stability and Makespan in Resource-- constrained Project Scheduling[J]. In- ternational Journal of Production Research, 2006, 44(2) :215-236.
[13]Veldhuizen D, Lamont G. Multi objective Evolu- tionary Algorithms: Analyzing the State- of- the-- art [J]. IEEE Transactions on Evolutionary Computation, 2000,18(2) : 125-147.
[14]李中凯[1],谭建荣[1],冯毅雄[1],方辉[1].基于拥挤距离排序的多目标粒子群优化算法及其应用[J].计算机集成制造系统,2008,14(7):1329-1336.
[15]Wayne L.运筹学概率模型应用范例与解法[M].李乃文,崔群法,林细财,等,译.4版.北京:清华大学出版社,2006.
[16]Coello C,Salzzar M. MOPSO:A Proposal for Mul- tiple Objective Particle Swarm Optimization[C]// IEEE Proceedings of 2002 Congress on Evolution- ary Computation. Washington D. C. , USA: IEEE, 2002:1051-1056.
[17]张沙清[1,2],陈新度[1],陈庆新[1],陈新[1].资源不确定环境下模具多项目预测—反应式调度算法[J].计算机集成制造系统,2010,16(12):2688-2696.
[18]赵志刚[1],李陶深[1],杨林峰[1].求多目标优化问题的粒子群优化算法[J].计算机工程与应用,2009,45(29):37-40.
[19]张利彪[1],周春光[1],马铭[1],刘小华[1].基于粒子群算法求解多目标优化问题[J].计算机研究与发展,2004,41(7):1286-1291.
[20]Abido M A. Environmental/Economic Power Dis- patch Using Multi--objective Evolutionary Algo- rithms[J]. IEEE Transactions on Power Systems, 2003,18(4) : 1529-1537.
[21]陈黎飞[1],姜青山[2],王声瑞[3].基于层次划分的最佳聚类数确定方法[J].软件学报,2008(1):62-72.
[22]周刘喜[1],张兴华[1],李纬[1].一种改进的多目标粒子群优化算法[J].计算机工程与应用,2009,45(33):38-41.
[23]Zitzler E, Deb N, Thiele L, Comparison of Multi-- objective Evolutionary Algorithms: Empirical Re- sults[J ]. Evolutionary Computation, 2000,8 (2) : 173-195.
[24]王辉[1],钱锋[2].基于拥挤度与变异的动态微粒群多目标优化算法[J].控制与决策,2008,23(11):1238-1242.