Multi-objective workflow scheduling in cloud system based on cooperative multi-swarm optimization algorithm

Abstract

In order to improve the performance of multi-objective workflow scheduling in cloud system, a multi-swarm multiobjective optimization algorithm (MSMOOA) is proposed to satisfy multiple conflicting objectives. Inspired by division of the same species into multiple swarms for different objectives and information sharing among these swarms in nature, each physical machine in the data center is considered a swarm and employs improved multi-objective particle swarm optimization to find out non-dominated solutions with one objective in MSMOOA. The particles in each swarm are divided into two classes and adopt different strategies to evolve cooperatively. One class of particles can communicate with several swarms simultaneously to promote the information sharing among swarms and the other class of particles can only exchange information with the particles located in the same swarm. Furthermore, in order to avoid the influence by the elastic available resources, a manager server is adopted in the cloud data center to collect the available resources for scheduling. The quality of the proposed method with other related approaches is evaluated by using hybrid and parallel workflow applications. The experiment results highlight the better performance of the MSMOOA than that of compared algorithms.

Keywords

multi-objective workflow scheduling / multi-swarm optimization / particle swarm optimization (PSO) / cloud computing system

References

[1] YuJ, BuyyaR. Scheduling scientific workflow applications with deadline and budget constraints using genetic algorithms [J]. Scientific Programming, 2006, 14(3): 217-230

[2] ViswanathanS, VeeravalliB, RobertazziT G. Resource-aware distributed scheduling strategies for large-scale computational cluster/grid systems [J]. IEEE Transactions on Parallel and Distributed Systems, 2007, 18(10): 1450-1461

[3] DeelmanE, VahiK, JuveG, RyngeM, CallaghanS, MaechlingP, MayaniR, ChenW, SilvaR F, LivnyM, WengerK. PEGASUS, a workflow management system for science automation [J]. Future Generation Computer Systems, 2015, 46: 17-35

[4] PinedoM LScheduling: Theory, algorithms, and systems [M], 2012, New York, Springer

[5] TopcuogluH, HaririS, WuM. Performance-effective and low-complexity task scheduling for heterogeneous computing [J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274

[6] BraunT D, SiegelH J, BeckN, BölöniL L, MaheswaranM, ReutherA I, RobertsonJ P, TheysM D, YaoB, HensgenD, FrundR F. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems [J]. Journal of Parallel and Distributed computing, 2001, 61(6): 810-837

[7] CaoJ-w, HwangK, LiK-q, ZomayaA Y. Optimal multiserver configuration for profit maximization in cloud computing [J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(6): 1087-1096

[8] TsaiC, HuangW-c, ChiangM H, ChiangM C, YangC-sing. A hyper-heuristic scheduling algorithm for cloud [J]. IEEE Transactions on Cloud Computing, 2014, 2(2): 236-250

[9] LuoJ-y, RaoL, LiuXue. Temporal load balancing with service delay guarantees for data center energy cost optimization [J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(3): 775-784

[10] BuyyaR, YeoC S, VenugopalS, BrobergJ, BrandicL. Cloud computing and emerging IT platforms: Vision, hype, and reality for delivering computing as the 5th utility [J]. Future Generation Computer Systems, 2009, 25(6): 599-616

[11] FuZ-j, RenK, ShuJ-g, SunX-m, HuangF-xiao. Enabling personalized search over encrypted outsourced data with efficiency improvement [J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(9): 2546-2559

[12] XiaZ-h, WangX-h, SunX-m, WangQian. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data [J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 27(3): 340-352

[13] FuZ-j, SunX-m, LiuQ, ZhouL, ShuJ-gang. Achieving efficient cloud search services: Multi-keyword ranked search over encrypted cloud data supporting parallel computing [J]. IEICE Transactions on Communications, 2015190200

[14] RenY-j, ShenJ, WangJ, HanJ, LeeS Y. Mutual verifiable provable data auditing in public cloud storage [J]. Journal of Internet Technology, 2015, 16(2): 317-323

[15] GargS K, BuyyaR, SiegelH J. Scheduling parallel applications on utility grids: Time and cost trade-off management [C]. The Thirty-Second Australasian Conference on Computer Science. Australian: Australian Computer Society Inc., 2009151160

[16] TengS, HayL L, PengC E. Multi-objective ordinal optimization for simulation optimization problems [J]. Automatica, 2007, 43(11): 1884-1895

[17] ZhanF, CaoJ-w, LiK-q, KhanS U, HwangK. Multi-objective scheduling of many tasks in cloud platforms [J]. Future Generation Computer Systems, 2014, 37: 309-320

[18] TaoF, FengY, ZhangL, LiaoT W. CLPS-GA: A case library and Pareto solution-based hybrid genetic algorithm for energy-aware cloud service scheduling [J]. Applied Soft Computing, 2014, 19: 264-279

[19] DurilloJ J, NaeV, ProdanR. Multi-objective energy-efficient workflow scheduling using list-based heuristics [J]. Future Generation Computer Systems, 2014, 36: 221-236

[20] DurilloJ J, ProdanR. Multi-objective workflow scheduling in Amazon EC2 [J]. Cluster Computing, 2014, 17(2): 169-189

[21] FardH M, ProdanR, FahringerT. Multi-objective list scheduling of workflow applications in distributed computing infrastructures [J]. Journal of Parallel and Distributed Computing, 2014, 74(3): 2152-2165

[22] YassaS, ChelouahR, KadimaH, GranadoB. Multi-objective approach for energy-aware workflow scheduling in cloud computing environments [J]. The Scientific World Journal, 2013

[23] ChengJ-x, ZhangG-x, LiZ-d, LiY-quan. Multi-objective ant colony optimization based on decomposition for bi-objective traveling salesman problems[J]. Soft Computing, 2012, 16(4): 597-614

[24] GómezJ, GilC, BañosR, MárquezA L, MontoyaF G, MontoyaM G. A Pareto-based multi-objective evolutionary algorithm for automatic rule generation in network intrusion detection systems [J]. Soft Computing, 2013, 17(2): 255-263

[25] KennedyJ, EberhartR C. Particle swarm optimization [C]. The 1995 IEEE International Conference on Neural Network. Perth: IEEE, 199519421948

[26] CoelloC C A. Evolutionary multi-objective optimization: A historical view of the field [J]. IEEE Computational Intelligence Magazine, 2006, 1(1): 28-36

[27] GaoL, HailuA. Comprehensive learning particle swarm optimizer for constrained mixed-variable optimization problems [J]. International Journal of Computational Intelligence Systems, 2010, 3(6): 832-842

[28] HuY-f, DingY-s, HaoK-r, RenL-h, HanHua. An immune orthogonal learning particle swarm optimization algorithm for routing recovery of wireless sensor networks with mobile sink [J]. International Journal of Systems Science, 2014, 45(3): 337-350

[29] HuY-f, DingY-s, RenL-h, HaoK-r, HanHua. An endocrine cooperative particle swarm optimization algorithm for routing recovery of wireless sensor networks with multiple mobile sinks [J]. Information Sciences, 2015, 300: 100-113

[30] CoelloC A C, PulidoG T, LechugaM S. Handling multiple objectives with particle swarm optimization [J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 256-279

[31] LiuD-s, TanK C, GohC K, HoW K. A multiobjective memetic algorithm based on particle swarm optimization [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2007, 37(1): 42-50

[32] GaoH-y, CaoJ-long. Non-dominated sorting quantum particle swarm optimization and its application in cognitive radio spectrum allocation [J]. Journal of Central South University, 2013, 20(7): 1878-1888

[33] YenG G, DaneshyariM. Diversity-based information exchange among multiple swarms in particle swarm optimization [J]. International Journal of Computational Intelligence and Applications, 2008, 7(1): 57-75

[34] ParsopoulosK E, TasoulisD K, VrahatisM N. Multiobjective optimization using parallel vector evaluated particle swarm optimization [C]. The IASTED International Conference on Artificial Intelligence and Applications. America: IEEE, 2004, 2: 823-828

[35] DebK, PratapA, AgarwalS, MeyarivanT. A fast and elitist multiobjective genetic algorithm: NSGA-II [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197

[36] JuveG, ChervenakA, DeelmanE, BharathiS, MehtaG, VahiK. Characterizing and profiling scientific workflows [J]. Future Generation Computer Systems, 2013, 29(3): 682-692

[37] ChenW-w, DeelmanE. Workflowsim: A toolkit for simulating scientific workflows in distributed environments [C]. IEEE 8th International Conference on E-Science (e-Science). Chicago: IEEE, 201218

[38] BrooksD M, BoseP, SchusterS E, JacobsonH, KudvaP N, BuyuktosunogluA, WellmanJ, ZuubanV, GuptaM, CookP W. Power-aware microarchitecture: Design and modeling challenges for next-generation microprocessors [J]. IEEE Micro, 2000, 20(6): 26-44

[39] ZitzlerE, ThieleL, LaumannsM, FonsecaC M, FonsecaV G. Performance assessment of multiobjective optimizers: An analysis and review [J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2): 117-132