Computer Science ›› 2017, Vol. 44 ›› Issue (8): 252-259.doi: 10.11896/j.issn.1002-137X.2017.08.043

Previous Articles     Next Articles

Scientific Workflow Scheduling Algorithm Based on Hybrid Multi-objective Particle Swarm Optimization in Cloud Environment

DU Yan-ming and XIAO Jian-hua   

  • Online:2018-11-13 Published:2018-11-13

Abstract: For realizing the more efficient scheduling of scientific workflow tasks,the multi-objective optimization problem of workflow scheduling in cloud environment was researched and a workflow scheduling algorithm HPSO of hybrid particle swarm optimization based on non-dominance sort was presented.First,the multi-objective optimization model of workflow scheduling under budget and deadline constraint is established,which introduces three optimizaiton objectives,including the execution makespan of workflow,the execution cost and the execution energy consumption.Second,a hybrid particle swarm optimizaiton algorithm is designed to solve this three conflicting objectives optimization.Our algorithm can obtain the solutions set of workflow scheduling satisfying Pareto optimal by non-dominance sort.Finally,through the simulation experiments of three types of scientific workflow case,we compared the proposed algorithm to the same types of multi-objective scheduling algorithms,such as NSGA-II,MOPSO and ε-Fuzzy.The experimental results show that the scheduling solution obtained by HPSO not noly has better convergence,but also has better uniform spacing distribution among the solutions,which can better accord with the workflow scheduling optimization in cloud environment.

Key words: Cloud computing,Workflow scheduling,Particle swarm optimizaiton,Pareto optimal

[1] SKOURLETOPOULOS G,MAVROMOUSTAKIS C X,MASTORAKIS G,et al.Big Data and Cloud Computing:A Survey of the State-of-the-Art and Research Challenges[M]∥Advances in Mobile Cloud Computing and Big Data in the 5G Era.Springer International Publishing,2017.
[2] JIAN C,WANG Y,TAO M,et al.Time-constrainted workflow scheudling in cloud environment using simulation annealing algorithm[J].Journal of Engineering Science and Technology Review,2013,6(5):33-37.
[3] VERMA A,KAUSHAL S.Deadline constraint heuristic-based genetic algorithm for workflow scheduling in cloud[J].International Journal of Grid & Utility Computing,2014,5(2):96-106.
[4] ZHOU Y,HUANG X.Scheduling Workflow in Cloud Computing Based on Ant Colony Optimization Algorithm[C]∥Sixth International Conference on Business Intelligence and Financial Engineering.IEEE,2014:57-61.
[5] VERMA A,KAUSHAL S.Bi-Criteria Priority based Particle Swarm Optimization workflow scheduling algorithm for cloud[C]∥Engineering and Computational Sciences.IEEE,2014:1-6.
[6] JIA Y,BUYYA R.A Taxonomy of Workflow Management Systems for Grid Computing[J].Journal of Grid Computing,2005,3(3):171-200.
[7] KWOK Y K,AHMAD I.Dynamic critical-path scheduling:An effective technique for allocating task graphs to multiprocessors[J].IEEE Transactions on Parallel & Distributed Systems,1996,7(5):506-521.
[8] SIH G C,LEE E A.A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures[J].IEEE Transactions on Parallel & Distributed Systems,1993,4(2):175-187.
[9] TOPCUOGLU H,HARIRI S,WU M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Transactions Parallel Distributed Systems,2012,3(3):260-274.
[10] LEE Y C,ZOMAYA A Y.Stretch Out and Compact:Workflow Scheduling with Resource Abundance[C]∥ IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.IEEE,2013:219-226.
[11] YAN G,YU J,YANG X Y.Reliability-aware workflow scheduling strategy on cloud computing platform[J].Journal of Computer Applications,2014,4(3):673-677.(in Chinese) 闫歌,于炯,杨兴耀.基于可靠性的云工作流调度策略[J].计算机应用,2014,4(3):673-677.
[12] ZENG L,VEERAVALLI B,LI X.SABA:A security-aware and budget-aware workflow scheduling strategy in clouds[J].Journal of Parallel & Distributed Computing,2015,75:141-151.
[13] RODRIGUEZ M,BUYYA R.Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds[J].IEEE Transactions on Cloud Computing,2014,2(2):222-235.
[14] SU S,LI J,HUANG Q,et al.Cost-efficient task scheduling for executing large programs in the cloud[J].Parallel Computing,2013,39(4-5):177-188.
[15] GARG R,SINGH A K.Multi-objective workflow grid scheduling using ε-fuzzy dominance sort based discrete particle swarm optimization[J].Journal of Supercomputing,2014,8:709-732.
[16] DOGAN A,OZGUNER F.Biobjective scheduling algorithms for execution time-reliability trade-off in heterogeneous computing systems[J].Journal of Computer,2013,8(3):300-314.
[17] PADMAVENI K,ARAVINDHAR D J.Hybrid Memetic andParticle Swarm Optimization for Multi Objective Scientific Workflows in Cloud[C]∥ IEEE International Conference on Cloud Computing in Emerging Markets.IEEE Computer Society,2016:66-72.
[18] DURILLO J,NAE V,PRODAN R.Multi-objective energy-efficient workflow scheduling using list-based heuristics[J].Future Generation Computer Systems,2014,36(3):221-236.
[19] DURILLO J J,PRODAN R,BARBOSA J G.Pareto tradeoffscheduling of workflows on federated commercial Clouds[J].Simulation Modelling Practice & Theory,2015,58:95-111.
[20] POOLA D,GARG S K,BUYYA R,et al.Robust Scheduling of Scientific Workflows with Deadline and Budget Constraints in Clouds[C]∥IEEE,International Conference on Advanced Information NETWORKING and Applications.IEEE,2014:858-865.
[21] VERMA A,KAUSHAL S.Cost-Time Efficient Scheduling Plan for Executing Workflows in the Cloud[J].Journal of Grid Computing,2015,13(4):1-12.
[22] LIU C,ZENG Q,DUAN H,et al.E-Net Modeling and Analysis of Emergency Response Processes Constrained by Resources and Uncertain Durations[J].IEEE Transactions on Systems Man & Cybernetics Systems,2014,45(1):84-96.
[23] SUN S X,ZENG Q,WANG H.Process-Mining-Based Workflow Model Fragmentation for Distributed Execution[J].IEEE Transactions on Systems,Man and Cybernetics-Part A:Systems and Humans,2011,41(2):294-310.
[24] MEZMAZ M,MELAB N,KESSACI Y,et al.A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems[J].Journal of Parallel & Distributed Computing,2011,71(11):1497-1508.
[25] PRZYSTAKA P,KATUNIN A.Multi-Objective Meta-Evolution Method for Large-Scale Optimization Problems[M]∥Recent Advances in Computational Optimization.Springer International Publishing,2016:165-182.
[26] KENNEDY J,EBERHART R.Particle swarm optimization[C]∥IEEE International Conference on Neural Networks.IEEE,1995:1942-1948.
[27] JUVE G,CHERENAK A,DEELMAN E,et al.Characterizing and profiling scientific workflows[J].Future Generation Computer System,2013,9(3):682-692.
[28] DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!