Please wait a minute...
浙江大学学报(工学版)
JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)
Service Computing     
Cloud workflow scheduling algorithm based on novelty ranking and multi-quality of service
YUAN You-wei-, YU Jia, ZHENG Hong-sheng, WANG Jiao-jiao
1. School of Computer Science and Technology, Hangzhou Dianzi University, Hangzhou 310018, China; 2. Key Laboratory of Complex Systems Modeling and Simulation, Ministry of Education, Hangzhou 310018, China
Download:   PDF(2212KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  A cloud service workflow scheduling algorithm based on novelty ranking and multiple quality of service (QoS) was proposed, aiming at the problem that the optimal scheduling based on user cost and system utilization was not considered in the existing researches. Frequency of the tasks performed by the resource node, waiting time and execution time of the resource node were added into the recommendation model. The simulated annealing algorithm was used to train the recommendation model, and the priority factor was calculated. The scheduler performed the scheduling and updated it according to the priority factor table. Simulation results show that the proposed algorithm is better than the Q-learning algorithm in terms of task execution time, and the combined index of user cost and system utilization is better than that of the Q-learning algorithm on CloudSim platform.

Published: 11 June 2017
CLC:  TP 311  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

YUAN You-wei-, YU Jia, ZHENG Hong-sheng, WANG Jiao-jiao. Cloud workflow scheduling algorithm based on novelty ranking and multi-quality of service. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(6): 1190-1196.


基于新颖性排名和多服务质量的云工作流调度算法

针对现有研究未能综合考虑以用户成本和系统利用率为目标进行优化调度的问题,提出基于新颖性排名和多服务质量（QoS）目标的云工作流调度算法.将资源节点执行任务的频度、任务的等待时间和执行时间作为因子加入推荐模型；使用模拟退火算法训练得到推荐模型,计算出优先级因子；调度器根据优先级因子表进行调度并对其进行更新.在CloudSim平台上进行模拟调度仿真实验,结果证明：所提出算法的任务执行时间优于Q值学习（Q-learning）算法,且用户成本和系统使用率的综合指标更好.

参考文献(References)：
［1］ 刘鹏.云计算［M］.电子工业出版社,2015: 1.
［2］ 郑敏,曹健,姚艳.面向价格动态变化的云工作流调度算法［J］.计算机集成制造系统,2013, 19 (8): 1849-1858.
ZHENG Min, CAO Jian, YAO Yan. Cloud workflow scheduling algorithm oriented to dynamic price changes ［J］. Computer Integrated Manufacturing Systems, 2013, 19(8): 1849-1858.
［3］ LEE Y C, HAN H, ZOMAYA A Y, et al. Resource-efficient workflow scheduling in clouds ［J］. Knowledge-Based Systems, 2015, 80(8): 153-162.
［4］ 黄婷婷,梁意文.云工作流任务调度的模拟退火遗传改进算法［J］.微电子学与计算机,2016, 33 (1): 42-46.
HUANG Ting-ting, LIANG Yi-wen. An improved simulated annealing genetic algorithm for workflow scheduling in cloud platform ［J］. Microelectronics and computer, 2016, 33(1):
42-46.
［5］ CASAS I, TAHERI J, RANJAN R, et al. A balanced scheduler with data reuse and replication for scientific workflows in cloud computing systems ［J］. Future Generation
Computer Systems, 2016, In Press. http:∥dx.doi.org/10.1016/j.future.2015.12.005. 
［6］ STARLINGER J, COHENBOULAKIA S, KHANNA S, et al. Effective and efficient similarity search in scientific workflow repositories ［J］. Future Generation Computer Systems, 2016, 56(3): 584-594.
［7］ WANG Y, HUANG K, WANG F. Scheduling online mixed-parallel workflows of rigid tasks in heterogeneous multicluster environments ［J］. Future Generation Computer Systems, 2016, 60(7): 35-47.
［8］ KIANPISHEH S, CHARKARI N M, KARGAHI M. Reliability-driven scheduling of time/cost-constrained grid workflows ［J］. Future Generation Computer Systems, 2016, 55(2): 1-16.
［9］ 刘井响,杨雪峰,叶鑫.基于批量处理策略的云工作流调度方法［J］.计算机集成制造系统,2015, 21(2):336-343.
LIU Jing-xiang, YANG Xue-feng, YE Xin. Cloud workflow scheduling method based on batch processing strategy ［J］. Computer Integrated Manufacturing Systems, 2015, 21(2): 336-343.
［10］ 文一凭,刘建勋,陈聪阳.隐私与成本感知的云工作流调度方法［J］.计算机集成制造系统,2016, 22(2):294-301.
WEN Yi-ping, LIU Jian-xun, CHEN Cong-yang. Privacy-aware and cost-aware workflow scheduling in clouds ［J］. Computer Integrated Manufacturing Systems, 2016, 22(2):
294-301.
［11］ POOLA D, RAMAMOHANARAO K, BUYYA R. Fault-tolerant workflow scheduling using spot instances on clouds ［J］. Procedia Computer Science, 2014, 29(3): 523-533.
［12］ 杨玉丽,彭新光,黄名选,等.基于离散粒子群优化的云工作流调度［J］.计算机应用研究,2014, 31(12):3677-3681.
YANG Yu-li, PENG Xin-guang, HUANG Ming-xuan, et al. Cloud workflow scheduling based on discrete particle swarm optimization ［J］. Application Research of Computers, 2014, 31 (12): 3677-3681.
［13］ 曹斌,王小统,熊丽荣,等.时间约束云工作流调度的粒子群搜索方法［J］.计算机集成制造系统,2016, 22(2): 372-380.
CAO Bin, WANG Xiao-tong, XIONG Li-rong, et al. Searching method for particle swarm optimization of cloud workflow scheduling with time constraint ［J］. Computer Integrated
Manufacturing Systems, 2016,22(2): 372-380.
［14］ 李智勇,陈少淼,杨波,等.异构云环境多目标Memetic优化任务调度方法［J］.计算机学报,2016, 39(2):377-390.
LI Zhiyong, CHEN Shao-miao, YANG Bo, et al. Multi-objective memetic algorithm for task scheduling on heterogeneous cloud. Chinese Journal of Computers, 2016, 39(2): 377-390.
［15］ 魏豪,周抒睿,张锐,等.基于应用特征的PaaS弹性资源管理机制［J］.计算机学报,2016, 39(2): 223-236. 
WEI Hao, ZHOU Shu-rui, ZHANG Rui, et al. Application feature based elastic resource management mechanism on PaaS ［J］. Chinese Journal of Computers, 2016, 39(2): 223-236.
［16］ ZENG L, VEERAVALLI B, ZOMAYA A Y. An integrated task computation and data management scheduling strategy for workflow applications in cloud environments ［J］.
Journal of Network and Computer Applications, 2015, 50(4): 39-48.
［17］ FATIH AKTAS M, HALDEMAN G, PARASHAR M. Scheduling and flexible control of bandwidth and intransit services for end-to-end application workflows ［J］. Future Generation Computer Systems, 2016,56(3): 284-294.
［18］ 项亮.推荐系统实践［M］.北京：人民邮电出版社,2012: 174-175.
［19］ CALHEIROS R N, RANJAN R, BELOGLAZOY A, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning
algorithms ［J］. Software: Practice and Experience, 2011, 41(1): 23-50.
［20］ CUI D, KE W, PENG Z, et al. Multiple DAGs workflow scheduling algorithm based on reinforcement learning in cloud computing ［C］∥ International Symposium on Intelligence Computation and Applications 2015. Guangzhou: Springer, 2015: 305-311.
[1] You-wei WANG,Li-zhou FENG. Improved AdaBoost algorithm using group degree and membership degree based noise detection and dynamic feature selection[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2021, 55(2): 367-376.
[2] Jia-hao LIAO,Zhi-wen YU,Yi-meng LIU,Bin GUO. Design and implementation of mobile crowdsensing platform[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2020, 54(10): 1915-1922.
[3] Zi-long JI,Jun-zhong JI. Learning effective connectivity network structure based on parallel searching of double firefly populations[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2020, 54(4): 694-703.
[4] Wan-liang WANG,Xiao-han YANG,Yan-wei ZHAO,Nan GAO,Chuang LV,Zhao-juan ZHANG. Image enhancement algorithm with convolutional auto-encoder network[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2019, 53(9): 1728-1740.
[5] Zhi-yuan WAN,Jia-heng TAO,Jia-kun LIANG,Zhen-gong CAI,Cheng CHANG,Lin QIAO,Qiao-ni ZHOU. Large-scale empirical study on machine learning related questions on Stack Overflow[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2019, 53(5): 819-828.
[6] Kai-long ZHU,YU-liang LU,Hui HUANG,Zhao-kun DENG,Yi-jie DENG. Construction approach for control flow graph from binaries using hybrid analysis[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2019, 53(5): 829-836.
[7] WANG Haiyan, CHENG Yan . Dual service selection method based on coefficient of variation[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(6): 1197-1204.
[8] XU Rong-bin, SHI Jun, ZHANG Peng-fei, XIE Ying. Similarity measurement of transition mapping relation using Petri net[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(6): 1205-1213.
[9] CHANG Chao, LIU Ke-sheng, TAN Long-dan, JIA Wen-chao. Data flow analysis for C program based on graph model[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2017, 51(5): 1007-1015.
[10] WANG Ji kui . Bayesian conflicting Web data credibility algorithm[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(12): 2380-2385.
[11] TU Ding, CHEN Ling, CHEN Gen cai, WU Yong, WANG Jing chang. Hierarchical online NMF for detecting and tracking topics[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(8): 1618-1626.
[12] YANG Sha, YE Zhen yu, WANG Shu gang, TAO Hai, LI Shi jian. Perception enhanced intelligent robotic arm system[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2016, 50(6): 1155-1159.
[13] LUO Lin, SU Hong ye, BAN Lan. Nonparametric bayesian based on  mixture of dirichlet process in application of fault detection[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(11): 2230-2236.
[14] WANG Hong-hao, WANG Hui-quan, JIN Zhong-he. Rollback-able on-board software upgrade method based on incremental link[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(4): 724-731.
[15] WANG Ji-kui, LI Shao-bo. Quality evaluation algorithm for conflicting data sources based on true value finding[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2015, 49(2): 303-318.