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

doi:10.11959/j.issn.1000-0801.2019035

电信科学 ›› 2019, Vol. 35 ›› Issue (2): 1-13.doi: 10.11959/j.issn.1000-0801.2019035

• 研究与开发 • 下一篇

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

包晓安¹,曹云棣¹,张娜¹,钱俊彦²,曹建文³

¹ 浙江理工大学，浙江杭州 310018
² 桂林电子科技大学，广西桂林 541004
³ 中国科学院软件研究所，北京100190

修回日期:2019-01-01 出版日期:2019-02-01 发布日期:2019-02-23
作者简介:包晓安（1973- ），男，浙江理工大学教授，主要研究方向为云计算、自适应软件和智能信息处理。|曹云棣（1990- ），女，浙江理工大学硕士生，主要研究方向为云计算、智能计算与分布式处理。|张娜（1977- ），女，浙江理工大学副教授，主要研究方向为分布式数据处理、软件工程。|钱俊彦（1973- ），男，桂林电子科技大学教授，主要研究方向为软件工程、软件分析和云计算。|曹建文（1969- ），男，中国科学院软件研究所博士生导师，主要研究方向为高性能并行软件与算法的研究与开发。
基金资助:
国家自然科学基金资助项目(61502430);国家自然科学基金资助项目(61562015);广西省自然科学基金资助项目(2015GXNSFDA139038);浙江理工大学521人才培养计划资助项目

Multi-objective cloud workflow scheduling algorithm based on grid variance

Xiaoan BAO¹,Yundi CAO¹,Na ZHANG¹,Junyan QIAN²,Jianwen CAO³

¹ Zhejiang Sci-Tech University,Hangzhou 310018,China
² Guilin University of Electronic Technology,Guilin 541004,China
³ Chinese Academy of Sciences,Beijing 100190,China

Revised:2019-01-01 Online:2019-02-01 Published:2019-02-23
Supported by:
The National Natural Science Foundation of China(61502430);The National Natural Science Foundation of China(61562015);Guangxi Natural Science Foundation of China(2015GXNSFDA139038);521 Talent Project of Zhejiang Sci-Tech University

摘要/Abstract

摘要：

提出了基于格分布方差的多目标云工作流调度算法和差粒子自学习策略。首先，考虑任务调度的特性，进行粒子编码离散化。其次，利用 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.

Key words: cloud workflow scheduling, multi-objective optimization, particle swarm algorithm, grid variance, dynamic adjustment

中图分类号:

TP393

包晓安,曹云棣,张娜,钱俊彦,曹建文. 基于格分布方差的多目标云工作流调度算法[J]. 电信科学, 2019, 35(2): 1-13.

Xiaoan BAO,Yundi CAO,Na ZHANG,Junyan QIAN,Jianwen CAO. Multi-objective cloud workflow scheduling algorithm based on grid variance[J]. Telecommunications Science, 2019, 35(2): 1-13.

图/表 9

图1

图2

图3

图4

图5

表1

图6

图8

图9

参考文献 27

[1]	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.
[2]	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).
[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.
[4]	张鹏, 王桂玲, 徐学辉 . 云计算环境下适于工作流的数据布局方法[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.
[5]	沈尧, 秦小麟, 鲍芝峰 . 一种云环境中数据流的高效多目标调度方法[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.
[6]	王琳杰 . 云计算中基于生物共生机制改进粒子群优化的任务调度方案[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.
[7]	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.
[8]	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.
[9]	ZHENG W , SAKELLARIOU R . Budget-deadline constrained workflow planning for admission control[J]. Journal of Grid Compute, 2013,11(4): 633-651.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	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.
[16]	VERMAA , KAUSHAL S . A hybrid multi-objective particle swarm optimization for scientific workflow scheduling[J]. Parallel Computing, 2017(62): 1-19.
[17]	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.
[18]	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.
[19]	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.
[20]	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.
[21]	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.
[22]	胡旺, 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.
[23]	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.
[24]	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.
[25]	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.
[26]	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.
[27]	包晓安, 魏雪, 陈磊 ,等. 基于 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.

编号	计算速率/MIPS	带宽/(Mbit·s^-1)	单价/(美元·h^-1)	电压/V
1	967	870	3.13	1.5
	389			0.9
2	1 300	1 100	4.19	2.2
	650			1.0
3	1 250	854	3.67	2.2
	625			1.0
4	845	987	2.71	1.75
	338			0.9
5	1 077	730	3.26	1.5
	431			0.9
6	510	828	1.55	1.75
	204			0.9
7	1 290	921	3.73	2.2
	645			1.0
8	659	830	1.94	1.75
	267			0.9
9	1 160	568	3.45	1.5
	464			0.9
10	734	966	2.46	1.75
	294			0.9

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

Multi-objective cloud workflow scheduling algorithm based on grid variance

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 27

相关文章 8

Metrics

推荐阅读 0

[1]	朱洪涛, 郭庆. 基于用户群组的低轨卫星网络多星切换策略[J]. 电信科学, 2022, 38(4): 39-48.
[2]	李勇燕,吴坚平. 基于IPSO-MC融合算法的无线传感器节点定位[J]. 电信科学, 2020, 36(3): 11-18.
[3]	张煜培,赵知劲,郑仕链. 利用多目标PSO优化的累积时延和信道容量联合优化的频谱切换算法[J]. 电信科学, 2018, 34(7): 62-71.
[4]	邓伟,于卓智,张叶峰,陈雅琳,马永红. 电力调度量子密钥供给及动态调整策略[J]. 电信科学, 2018, 34(12): 146-154.
[5]	丁正超,魏振春,冯琳. 车载自组织网络中基于连接时长的RSU部署方案[J]. 电信科学, 2017, 33(4): 87-93.
[6]	文华. 运用备份服务位置和概率QoS模型的Web服务组合算法[J]. 电信科学, 2016, 32(10): 116-125.
[7]	徐璟庭,曲桦,赵季红. SDN中基于KMOBPSO的高可靠性控制器部署算法[J]. 电信科学, 2015, 31(6): 61-67.
[8]	康国胜,刘建勋,唐明董,徐宇. 基于差异演化算法的QoS全局最优动态Web服务选择[J]. 电信科学, 2011, 27(12): 67-71.