[1]张晓东,王茜.多目标服务工作流混合粒子群调度算法[J].东南大学学报(自然科学版),2010,40(3):491-495.[doi:10.3969/j.issn.1001-0505.2010.03.011]
 Zhang Xiaodong,Wang Qian.Hybrid particle swarm optimization algorithm for multi-objective scheduling in service-workflows[J].Journal of Southeast University (Natural Science Edition),2010,40(3):491-495.[doi:10.3969/j.issn.1001-0505.2010.03.011]
点击复制

多目标服务工作流混合粒子群调度算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
40
期数:
2010年第3期
页码:
491-495
栏目:
计算机科学与工程
出版日期:
2010-05-20

文章信息/Info

Title:
Hybrid particle swarm optimization algorithm for multi-objective scheduling in service-workflows
作者:
张晓东 王茜
东南大学计算机科学与工程学院, 南京 210096; 东南大学计算机网络和信息集成教育部重点实验室, 南京 210096
Author(s):
Zhang Xiaodong Wang Qian
School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 210096, China
关键词:
服务工作流 有向无环图(DAG) 粒子群优化(PSO) 多目标优化 Pareto解集
Keywords:
service-workflow directed acrylic graph(DAG) particle swarm optimization(PSO) multi-objective optimization Pareto optimal set
分类号:
TP393
DOI:
10.3969/j.issn.1001-0505.2010.03.011
摘要:
针对NP难的服务工作流时间-费用优化问题,提出多目标混合粒子群算法(HMOPSO)来优化工作流调度问题.HMOPSO算法包括:初始种群生成、适应值分配、种群多样性保持、外部种群和极值选择.通过分析服务工作流的特征,构建有效的粒子结构使之离散化; 通过设定单目标最优初始解,优化初始种群; 通过引入外部种群和基于小生境技术的网格方法,获得分布均匀的Pareto最优解集.实验结果表明,HMOPSO具有更快的收敛速度和更好的寻优能力,并且在不同特征的问题实例上获得了数量众多、分布均匀、有较高质量的Pareto最优解集.
Abstract:
A multi-objective hybrid PSO(particle swarm optimization)method is proposed for the time-cost optimization problem in service-workflows, a NP-Hard problem. Characteristics of service-workflows are analyzed. Discrete particles are constructed. HMOPSO is included: initial population generation, fitness distribution, population diversity maintainance, outside population and extreme choice. The initial population is generated by setting optimal solutions to single-objective problems. To obtain an evenly distributed Pareto set, an outside population and a meshing method based on the niche technique are introduced. Experimental results show that the proposed algorithm is efficient and effective for the considered problem. Many evenly distributed Pareto sets with high quality are obtained for various characteristic instances.

参考文献/References:

[1] Yu J,Buyya R.Taxonomy of scientific workflow systems for grid computing[J].SIGMOD Record,2005,34(3):44-49.
[2] Blythe J,Jain S,Deelman E,et al.Task scheduling strategies for workflow-based applications in grids[C] //IEEE International Symposium on Cluster Computing and Grid.Cardiff,Wales,UK,2005:759-767.
[3] Buyya R,Abramson D,Giddy J,et al.Economic models for resource management and scheduling in grid computing[J].Concurrency and Computation:Practice and Experience Journal:Special Issue on Grid Computing Environments,2002,14(13/14/15):1507-1542.
[4] Abramson D,Buyya R,Giddy J.A computational economy for grid computing and its implementation in the nimrod-G resource broker[J].Future Generation Computer Systems Journal,2002,18(8):1061-1074.
[5] Lin M,Lin Z X.A cost-effective critical path approach for service priority selections in grid computing economy[J]. Decision Support Systems,2006,42(3):1628-1640.
[6] Pan Q K,Tasgetiren M F,Liang Y C.A discrete particle swarm optimization algorithm for the no-wait flow shop scheduling problem[J].Computers and Operations Research,2008,35(9):2807-2839.
[7] 张晓东,李小平,王茜.服务工作流的混合粒子群调度算法[J].通信学报,2008,29(8):87-93.
  Zhang Xiaodong,Li Xiaoping,Wang Qian,et al.Hybrid particle swarm optimization algorithm for cost minimization in service-workflows with due dates[J].Journal on Communications,2008,29(8):87-93.(in Chinese)
[8] Zitzler E,Laumanns M,Thiele L.SPEA2:improving the strength Pareto evolutionary algorithm[R].Zurich,Switzerland:Computer Engineering and Networks Laboratory,2001.
[9] Deb K,Pratap A,Agarwal S,et a1.A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[10] Coello C A,Pulido G T,Lechuga M S.Handling multiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation,2004,8(3):256-279.
[11] Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C] //Proc 6th Int Symposium on Micro Machine and Human Science.Nagoya,Japan,1995:39-43.
[12] 苑迎春,李小平,王茜.基于串归约的网格工作流费用优化方法[J].计算机研究与发展,2008,45(2):246-253.
  Yuan Yinchun,Li Xiaoping,Wang Qian.Cost optimization for scheduling grid workflows based on serial reduction[J]. Journal of Computer Research and Development,2008, 45(2):246-253.(in Chinese)
[13] Deb K. Multi-objective optimization using evolutionary algorithms [M].Chichester,UK:Wiley,2001.
[14] Sareni B,Krähenbühl L.Fitness sharing and niching methods revisited [J].IEEE Transaction on Evolutionary Computation,1998,2(3):97-106.
[15] Tan K C,Lee T H,Khor E F.Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization[J].IEEE Transaction on Evolutionary Computation,2001,5(6):565-588.

备注/Memo

备注/Memo:
作者简介: 张晓东(1972—),男,博士生; 王茜(联系人),女,教授,博士生导师,qwang@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(60873236,60973073)、国家高技术研究发展计划(863计划)资助项目(2008AA04Z103).
引文格式: 张晓东,王茜.多目标服务工作流混合粒子群调度算法[J].东南大学学报:自然科学版,2010,40(3):491-495. [doi:10.3969/j.issn.1001-0505.2010.03.011]
更新日期/Last Update: 2010-05-20