基于多Agent系统的粒子群遗传优化云工作流调度算法

南京大学学报(自然科学版) ›› 2017, Vol. 53 ›› Issue (6): 1114–.

基于多Agent系统的粒子群遗传优化云工作流调度算法

吴家豪1，彭志平2*，崔得龙2，李启锐2，何杰光2

出版日期:2017-11-27 发布日期:2017-11-27
作者简介:1.广东工业大学计算机学院，广州，510006；
2.广东石油化工学院计算机与电子信息学院，茂名，525000
基金资助:
基金项目：国家自然科学基金(61772145，61672174，61272382)，广东省科技计划项目(2015B020233019，2014A020208139)
收稿日期：2017－09－22
*通讯联系人，E－mail：pengzp@foxmail.com

Combining PSO and GA for workflow scheduling based on multi－agent system

Wu Jiahao1，Peng Zhiping2*，Cui Delong2，Li Qirui2，He Jieguang2

Online:2017-11-27 Published:2017-11-27
About author:1.Department of Computer，Guangdong University of Technology，Guangzhou，510006，China；
2．Department of Computer and Electronic Information，Guangdong University of Petrochemical Technology，Maoming，525000，China

摘要/Abstract

摘要： 随着大数据时代的来临，传统的工作流计算平台已经无法满足大量工作流应用的计算要求．因此，工作流应用开始由原有的基础设施转移到更加高效、可靠、廉价的云平台上．针对现有的云工作流调度算法执行时间最小化、作业最优分配以及调度算法的收敛时间问题，提出一种基于多Agent系统的粒子群遗传优化云工作流调度算法．该算法首先利用粒子的自身历史最优位置和粒子群历史最优位置优化全局最优解的搜索过程，然后将系统中每个粒子作为一个Agent，多Agent间相互竞争和协调，最后在多Agent系统中引入遗传算法，通过Agent间的信息交互进行有目标地交叉变异操作，不仅避免粒子群的盲目随机化以及陷入局部最优解，而且加速了搜索全局最优解的收敛过程．使用真实工作流数据进行模拟实验，实验结果证明该算法的有效性．

Abstract: With the arrival of big data era，workflow applications are transferring from original infrastructure to cloud computing platforms，which is more efficient，reliable and affordable to meet the computational requirements of a large number of workflow applications.Aiming at the problems of workflow job scheduling on cloud，such as the minimization of the execution time，the optimal allocation of the job scheduling and the convergence time of the scheduling algorithm，an improved algorithm named Combining Particle Swarm Optimization Algorithm(PSO) and Genetic Algorithm(GA) for Workflow Scheduling Based on Multi－Agent System was presented.This algorithm firstly uses both the particle’s own historical position and particle group history optimal position to optimize the global optimal solution of the search process，and then introduces multi－agent system，where each particle acts as an agent，and those agents complete and coordinate each other.Finally，genetic algorithm operates which depends on an information interaction between agents cross－variation based on the target，not only to avoid the blind randomization of particle swarm and falling into the local optimal solution，but also to accelerate the global optimal solution of the convergence process.In this paper，a real workflow data is used for simulate the experiments，and the experimental result shows the effectiveness of the algorithm.

吴家豪1，彭志平2*，崔得龙2，李启锐2，何杰光2. 基于多Agent系统的粒子群遗传优化云工作流调度算法[J]. 南京大学学报(自然科学版), 2017, 53(6): 1114–.

Wu Jiahao1，Peng Zhiping2*，Cui Delong2，Li Qirui2，He Jieguang2. Combining PSO and GA for workflow scheduling based on multi－agent system[J]. Journal of Nanjing University(Natural Sciences), 2017, 53(6): 1114–.

参考文献

[1]　Shishira S R，Kandasamy A，Chandrasekaran K，et al.Survey on meta heuristic optimization techniques in cloud computing.In：Proceedings of 2016 International Conference on Advances in Computing，Communications and Informatics(ICACCI)．Jaipur，India：IEEE.2016：1434－1440.　
[2] Thomas E，Zaigham M，Ricardo P．云计算：概念、技术与架构．龚奕利，贺莲，胡　创译．机械工业出版社，2014，14－18.
[3] Wu F H，Wu Q B，Tan Y S．Workflow scheduling in cloud：A survey.The Journal of Supercomputing，2015，71(9)：3373－3418.
[4] Durillo J J，Prodan R．Workflow scheduling on federated clouds.In：European Conference on Parallel Processing.Springer Berlin Heidelberg，2014：45－50.
[5] Topcuoglu H，Hariri S，Wu M Y．Performance－effective and low－complexity task scheduling for heterogeneous computing.IEEE Transactions on Parallel and Distributed Systems，2002，13(3)：260－274.
[6] El－Rewini H，Lewis T G．Scheduling parallel program tasks onto arbitrary target machines.Journal of Parallel and Distributed Computing，1990，9(2)：138－153.
[7] Liu G Q，Poh K L，Xie M．Iterative list scheduling for heterogeneous computing.Journal of Parallel and Distributed Computing，2005，65(5)：654－665.　
[8] Arabnejad H，Barbosa J G．List scheduling algorithm for heterogeneous systems by an optimistic cost table.IEEE Transactions on Parallel and Distributed Systems，2014，25(3)：682－694.
[9] Salza P，Ferrucci F，Sarro F．Deploy and execute parallel genetic algorithms in the cloud.In：Proceedings of the 2016 on Genetic and Evolutionary Computation Conference(CECCO 2016)．Denver，CO，USA：ACM，2016：121－122.
[10] Li H H，Chen Z G，Zhan Z H，et al.Renumber coevolutionary multiswarm particle swarm optimization for multi－objective workflow scheduling on cloud computing environment.In：Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation.Madrid，Spain：ACM，2015：1419－1420.
[11] Shojafar M，Javanmardi S，Abolfazli S，et al.FUGE：A joint meta－heuristic approach to cloud job scheduling algorithm using fuzzy theory and a genetic method.Cluster Computing，2015，18(2)：829－844.
[12] Zhang F，Cao J W，Li K Q．Multi－objective scheduling of many tasks in cloud platforms.Future Generation Computer Systems，2014，37：309－320.
[13] 郭　禾，陈　征，于玉龙等．带通信开销的DAG工作流费用优化模型与算法．计算机研究与发展，2015，52(6)：1400－1408.(Guo H，Chen Z，Yu Y L，et al.A communication aware DAG workflow cost optimization model and algorithm.Journal of Computer Research and Development，2015，52(6)：1400－1408.)
[14] Pandey S，Wu L L，Guru S M，et al.A particle swarm optimization－based heuristic for scheduling workflow applications in cloud computing environments.In：Proceedings of the IEEE International Conference on Advanced Information Networking and Applications.Aina，Perth，Australia：IEEE，2010：400－407.
[15] Zuo L Y，Shu L，Dong S B，et al.A multi－objective optimization scheduling method based on the ant colony algorithm in cloud computing.IEEE Access，2015，3：2687－2699.
[16] Kianpisheh S，Charkari N M，Kargahi M．Ant colony based constrained workflow scheduling for heterogeneous computing systems.Cluster Computing，2016，19(3)：1053－1070.
[17] Hafez M G，Elgamel M S．Agent－based cloud computing：A survey.In：Proceedings of the IEEE International Conference on Future Internet of Things and Cloud(FiCloud)．Vienna，Austria：IEEE，2016：285－292.
[18] 肖　正，吴承荣，张世永．多Agent系统合作与协调机制研究综述．计算机科学，2007，34(5)：139－143.(Xiao Z，Wu C R，Zhang S Y．A survey of cooperation and coordination in multi－agent system.Computer Science，2007，34(5)：139－143.)　
[19] Padmavathi S，Dharani V P，Maithrreye S，et al.Multi－agent framework for cloud service composition.In：Proceedings of the 2016 International Conference on Emerging Trends in Engineering，Technology and Science(ICETETS)．Pudukkottai，India：IEEE，2016：1－5.
[20] 侯　富，毛新军，吴　伟．一种基于多Agent系统的云服务自组织管理方法．软件学报，2015，26(4)：835－848.(Hou F，Mao X J，Wu W．Self－organizing management approach for cloud services based on multi－agent system.Journal of Software，2015，26(4)：835－848.)
[21] Wei Y，Blake M B．Proactive virtualized resource management for service workflows in the cloud.Computing，2016，98(5)：523－538.
[22] Chen W W，Deelman E．Workflow Sim：A toolkit for simulating scientific workflows in distributed environments.In：Proceedings of the IEEE International Conference on E－Science.Chicago，IL，USA：IEEE，2012：1－8.
[23] Bharathi S，Chervenak A，Deelman E，et al.Characterization of scientific workflows.In：Proceedings of 2008 3rd Workshop on Workflows in Support of Large－Scale Science.Austin，TX，USA：IEEE，2008：1－10.
[24] Van Den Bergh F．An analysis of particle swarm optimizers.Ph.D.Dissertation.Pretoria：University of Pretoria，2002：87－110.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed