基于格分布方差的多目标云工作流调度算法

包晓安; 曹云棣; 张娜; 钱俊彦; 曹建文

doi:10.11959/j.issn.1000-0801.2019035

您当前的位置：

首页 >

文章列表页 >

基于格分布方差的多目标云工作流调度算法

研究与开发 | 更新时间：2024-06-05

- 基于格分布方差的多目标云工作流调度算法
- Multi-objective cloud workflow scheduling algorithm based on grid variance
- 电信科学 2019年35卷第2期页码：1-13
- 作者机构：
  
  1. 浙江理工大学，浙江杭州 310018
  2. 桂林电子科技大学，广西桂林 541004
  3. 中国科学院软件研究所，北京100190
- 作者简介：
  
  [ "包晓安（1973- ），男，浙江理工大学教授，主要研究方向为云计算、自适应软件和智能信息处理。" ]
  [ "曹云棣（1990- ），女，浙江理工大学硕士生，主要研究方向为云计算、智能计算与分布式处理。" ]
  [ "张娜（1977- ），女，浙江理工大学副教授，主要研究方向为分布式数据处理、软件工程。" ]
  [ "钱俊彦（1973- ），男，桂林电子科技大学教授，主要研究方向为软件工程、软件分析和云计算。" ]
  [ "曹建文（1969- ），男，中国科学院软件研究所博士生导师，主要研究方向为高性能并行软件与算法的研究与开发。" ]
- 基金信息：
  
  国家自然科学基金资助项目;The National Natural Science Foundation of China(61502430);国家自然科学基金资助项目;The National Natural Science Foundation of China(61562015);广西省自然科学基金资助项目;Guangxi Natural Science Foundation of China(2015GXNSFDA139038);浙江理工大学521人才培养计划资助项目;521 Talent Project of Zhejiang Sci-Tech University
- DOI：10.11959/j.issn.1000-0801.2019035
  中图分类号： TP393
- 网络出版日期：2019-02，
  
  纸质出版日期：2019-02-20
- 稿件说明：
移动端阅览
包晓安, 曹云棣, 张娜, 等. 基于格分布方差的多目标云工作流调度算法[J]. 电信科学, 2019,35(2):1-13.

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.
包晓安, 曹云棣, 张娜, 等. 基于格分布方差的多目标云工作流调度算法[J]. 电信科学, 2019,35(2):1-13. DOI： 10.11959/j.issn.1000-0801.2019035.

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 .

浏览量

578

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

多目标滚动时域优化的数学模型在运营商智能派单中的构建与应用

基于策略约束强化学习的算网多目标优化研究

基于IPSO-MC融合算法的无线传感器节点定位

电力调度量子密钥供给及动态调整策略

利用多目标PSO优化的累积时延和信道容量联合优化的频谱切换算法