云环境中基于混合多目标粒子群的科学工作流调度算法

doi:10.11896/j.issn.1002-137X.2017.08.043

摘要/Abstract

摘要： 为了更高效地实现科学工作流任务的调度,研究了云环境中的工作流调度多目标优化问题,提出了一种基于非占优排序的混合多目标粒子群优化的工作流调度算法HPSO。首先,建立了截止时间与预算约束下工作流调度的多目标优化模型,模型引入三目标最优化,包括工作流执行跨度、执行代价及执行能耗；其次,设计了一种混合粒子群算法对相互冲突的三目标最优化进行求解,算法通过非占优排序的形式可以得到满足Pareto最优的工作流调度解集合；最后,通过3种科学工作流案例的仿真实验,与同类多目标调度算法NSGA-II,MOPSO和ε-Fuzzy进行了性能比较。实验结果表明,HPSO得到的调度解不仅收敛性更好,而且调度解的空间分布更加一致,更符合云环境中的工作流调度优化。

关键词: 云计算,工作流调度,粒子群优化,Pareto最优

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

杜艳明,肖建华. 云环境中基于混合多目标粒子群的科学工作流调度算法[J]. 计算机科学, 2017, 44(8): 252-259. https://doi.org/10.11896/j.issn.1002-137X.2017.08.043

DU Yan-ming and XIAO Jian-hua. Scientific Workflow Scheduling Algorithm Based on Hybrid Multi-objective Particle Swarm Optimization in Cloud Environment[J]. Computer Science, 2017, 44(8): 252-259. https://doi.org/10.11896/j.issn.1002-137X.2017.08.043

参考文献

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed