Multi-objective cloud workflow scheduling algorithm based on grid variance

Xiaoan BAO; Yundi CAO; Na ZHANG; Junyan QIAN; Jianwen CAO

doi:10.11959/j.issn.1000-0801.2019035

您当前的位置：

首页 >

文章列表页 >

Multi-objective cloud workflow scheduling algorithm based on grid variance

research and development | 更新时间：2024-06-05

- Multi-objective cloud workflow scheduling algorithm based on grid variance
- Telecommunications Science Vol. 35, Issue 2, Pages: 1-13(2019)
- 作者机构：
  
  1. 浙江理工大学，浙江杭州 310018
  2. 桂林电子科技大学，广西桂林 541004
  3. 中国科学院软件研究所，北京100190
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.1000-0801.2019035
  CLC： TP393
- Published Online：2019-02，
  
  Published：20 February 2019
- 稿件说明：
移动端阅览
Xiaoan BAO, Yundi CAO, Na ZHANG, et al. Multi-objective cloud workflow scheduling algorithm based on grid variance[J]. Telecommunications science, 2019, 35(2): 1-13.
DOI：

Xiaoan BAO, Yundi CAO, Na ZHANG, et al. Multi-objective cloud workflow scheduling algorithm based on grid variance[J]. Telecommunications science, 2019, 35(2): 1-13. DOI： 10.11959/j.issn.1000-0801.2019035.

摘要

提出了基于格分布方差的多目标云工作流调度算法和差粒子自学习策略。首先，考虑任务调度的特性，进行粒子编码离散化。其次，利用 Pareto 最优工作流调度解集映射到自适应网格坐标系的策略，计算网格坐标系中每个Pareto最优解的格分布量。再次，采用格分布方差评估当前Pareto前端的多样性程度，并动态调整进化策略。最后，设计了差粒子自学习策略。仿真实验表明，通过该算法得到的工作流调度解集，在IGD和S性能指标上均优于MOPSO算法，在最优值方面优于ε-FDPSO和NSGA-Ⅱ算法。

Abstract

Multi-objective cloud workflow scheduling algorithm based on grid variance and the strategy of bad particles self-learning were presented.Firstly

the characteristics of task scheduling was token into consideration

and particle encoding was discredited.Secondly

the strategy of mapping Pareto optimal workflow scheduling set to self-adaptive grid coordinate system

and calculating the grid distribution value of each Pareto optimal solution was used.Thirdly

grid variance was adopted to evaluate the diversity of current Pareto front and dynamically adjust evolution strategies.Finally

the concept of being dominated times was introduced into bad particles self-learning strategy for filtering out bad particles in population.The simulation experiment shows that workflow scheduling solution set by this algorithm is better than the MOPSO algorithm on both IGD and S performance indexes

and the optimal value is superior to the ε-FDPSO and NSGA-Ⅱ algorithm.

关键词

Keywords

references

MASDARI M , VALIKARDAN S , SHAHI Z , et al . Towards workflow scheduling in cloud computing:a comprehensive analysis [J ] . Journal of Network and Computer Applications , 2016 , 66 ( 5 ): 64 - 82 .

AWADA U , KEQIU L , YANMING S . Energy consumption in cloud computing data centers [J ] . International Journal of Cloud Computing and Services Science , 2014 , 3 ( 3 ).

袁景凌 , 钟珞 , 杨光 , 等 . 绿色数据中心不完备能耗大数据填补及分类算法研究 [J ] . 计算机学报 , 2015 , 38 ( 12 ): 2499 - 2516 .

YUAN J L , ZHONG L , YANG G , et al . Towards filling and classification of incomplete energy big data for green data centers [J ] . Chinese Journal of Computers , 2015 , 38 ( 12 ): 2499 - 2516 .

张鹏 , 王桂玲 , 徐学辉 . 云计算环境下适于工作流的数据布局方法 [J ] . 计算机研究与发展 , 2013 , 50 ( 3 ): 636 - 647 .

ZHANG P , WANG G L , XU X H . A data placement approach for workflow in cloud [J ] . Journal of Computer Research and Development , 2013 , 50 ( 3 ): 636 - 647 .

沈尧 , 秦小麟 , 鲍芝峰 . 一种云环境中数据流的高效多目标调度方法 [J ] . 软件学报 , 2017 , 28 ( 3 ): 579 - 597 .

SHEN Y , QIN X L , BAO Z F . Effective multi-objective scheduling strategy of dataflow in cloud [J ] . Journal of Software , 2017 , 28 ( 3 ): 579 - 597 .

王琳杰 . 云计算中基于生物共生机制改进粒子群优化的任务调度方案 [J ] . 电信科学 , 2016 , 32 ( 9 ): 113 - 119 .

WANG L J . Task scheduling scheme based on improved particle swarm optimization with biological symbiosis mechanism in cloud computing [J ] . Telecommunications Science , 2016 , 32 ( 9 ): 113 - 119 .

TOPCUOGLU H , HARIRI S , WU M . Performance-effective and low-complexity task scheduling for heterogeneous computing [J ] . IEEE Transactions on Parallel Distributed Systems , 2002 , 13 ( 3 ): 260 - 274 .

ABRISHAMI S , NAGHIBZADEH M , EPEMA D H . Deadline-constrained workflow scheduling algorithm for infrastructure as a service cloud [J ] . Future Generation Computer Systems , 2013 , 29 ( 1 ): 158 - 169 .

ZHENG W , SAKELLARIOU R . Budget-deadline constrained workflow planning for admission control [J ] . Journal of Grid Compute , 2013 , 11 ( 4 ): 633 - 651 .

ISRAEL C , JAVID T , RAJIV R , et al . GA-ETI:an enhanced genetic algorithm for the scheduling of scientific workflows in cloud environments [J ] . Future Generation Computer Systems , 2018 : 257 - 271 .

MEENA J , KUMAR M , VARDHAN M . Cost effective genetic algorithm for workflow scheduling in cloud under deadline constraint [J ] . IEEE Access , 2016 ( 4 ): 5065 - 5082 .

SINGH L , SINGH S . Deadline and cost based ant colony optimization algorithm for scheduling workflow applications in hybrid cloud [J ] . Journal of Scientific ＆ Engineering Research , 2014 , 5 ( 10 ): 1417 - 1420 .

RODRIGUEZ M A , 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 .

YASSA S , CHELOUAH R , KADIMA H , et al . Multi-objective approach for energy-aware workflow scheduling in cloud computing environment [J ] . The Science World Journal , 2013 : 1 - 13 .

DENG G S , LI Z M , ZHAO Y M , et al . MOEA/D for energy-aware scheduling on heterogeneous computing systems [C ] // 10th International Conference on Bio-Inspired Computing,Theories and Applications(BIC-TA 2015),Sep 25-28,2015,Hefei,China . Heidelberg:Springer , 2015 : 94 - 106 .

VERMAA , KAUSHAL S . A hybrid multi-objective particle swarm optimization for scientific workflow scheduling [J ] . Parallel Computing , 2017 ( 62 ): 1 - 19 .

NESMACHNOW S , ITURRIAGA S , DORRONSORO B , et al . Multiobjective energy-aware workflow scheduling in distributed datacenters [C ] // 6th International Conference on High Performance Computer Applications(ISUM 2015),March 9-13,2015,Mexico City,Mexico . Heidelberg:Springer , 2015 .

DURILLO J J , NAE V , PRODAN R . Multi-objective energy-efficient workflow scheduling using list-based heuristics [J ] . Future Generation Computer Systems , 2014 ( 36 ): 221 - 236 .

PRZYSTALKA P , KATUNIN A . Multi-objective meta-evolution method for large-scale optimization problems [M ] // Recent advances in computational optimization . Heidelberg:Springer , 2016 : 165 - 182 .

LEE Y C , ZOMAYAA Y . Energy conscious scheduling for distributed computing systems under different operating conditions [J ] . IEEE Transactions on Parallel Distributed System , 2011 , 22 ( 8 ): 1374 - 1381 .

GARG R , SINGHAK . Multi-objective workflow grid scheduling using ε-fuzzy dominance sort based discrete particle swarm optimization [J ] . Journal of Supercomputing , 2014 , 68 ( 2 ): 709 - 732 .

胡旺 , YEN G G , 张鑫 . 基于Pareto熵的多目标粒子群优化算法 [J ] . 软件学报 , 2014 , 25 ( 5 ): 1025 - 1050 .

HU W , YEN G G , ZHANG X . Multi-objective particle swarm optimization based on Pareto entropy [J ] . Journal of Software , 2014 , 25 ( 5 ): 1025 - 1050 .

PADMAVENI K , ARAVINDHAR D J . Hybrid memetic and particle swarm optimization for multi objective scientific workflows in cloud [C ] // IEEE International Conference on Cloud Computing in Emerging Markets,Oct 19-21,2016,Bangalore,India . Piscataway:IEEE Press , 2016 : 66 - 72 .

DOGAN A , OZGUNER F . Biobjective scheduling algorithms for execution time-reliability trade-off in heterogeneous computing systems [J ] . Journal of Computer , 2013 , 48 ( 3 ): 300 - 314 .

CHEN W , DEELMAN E . WorkflowSim:a tool kit for simulating scientific workflows in distributed environment [C ] // International Conference on E-Science,Oct 8-12,2012,Chicago,IL,USA . Washington DC:IEEE Computer Society , 2012 : 1 - 8 .

LI H , ZHANG Q F . Multiobjective optimization problems with complicated pareto sets,MOEA/D and NSGA-II [J ] . IEEE Transactions on Evolutionary Computation , 2008 , 13 ( 2 ): 284 - 302 .

包晓安 , 魏雪 , 陈磊 , 等 . 基于 mean-variance 的服务集群负载均衡方法 [J ] . 电信科学 , 2017 , 33 ( 1 ): 6 - 13 .

BAO X A , WEI X , CHEN L , et al . Load balancing method of service cluster based on mean-variance [J ] . Telecommunications Science , 2017 , 33 ( 1 ): 6 - 13 .

Views

578

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Construction and application of a multi-objective rolling horizon optimization mathematical model in intelligent dispatching for telecom operators

Research on constrained policy reinforcement learning based multi-objective optimization of computing power network

Wireless sensor node localization based on IPSO-MC

Quantum key supply and dynamic adjustment strategies for power dispatch

Spectrum handoff method by using joint optimization of cumulative delay and channel capacity based on multi-objective PSO

Related Author

XIN Sheng

LI Yuan

LIU Ying

MA Xiaoliang

LI Fang

Chang CAO

Yan ZHANG

Chao CUI

Related Institution

Guangzhou Branch of China Telecom Co., Ltd.

Ma Xiaoliang Innovation Studio for Model Workers and Creative Talents

China DataCom Co., Ltd.

Inspur Communication Information System Co., Ltd.

Research Institute of China United Network Communications Co., Ltd.

⁰