计算机科学 ›› 2022, Vol. 49 ›› Issue (11A): 210800154-6.doi: 10.11896/jsjkx.210800154
王子健1, 卢政昊1,2, 潘纪奎1,2, 孙福权1
WANG Zi-jian1, LU Zheng-hao1,2, PAN Ji-kui1,2, SUN Fu-quan1
摘要: 云环境中的工作流调度是如今最具挑战性的问题之一。它关注于在指定的服务质量需求下,以将相互依赖的任务映射到虚拟机的方式来执行工作流应用程序。云服务提供商以不同的价格提供不同性能的虚拟机。同样的工作流,配置不同的虚拟机,会产生不同的完工时间以及货币成本。云中工作流调度的主要问题之一是在满足用户给定的截止时间约束的前提下,找到一种更廉价的调度方法。为解决上述问题提出了一种云环境中满足截止时间约束且优化成本的工作流调度策略DCCO。它基于δ-alap对截止时间进行分配,并考虑了两个任务可能被分配到同一虚拟机的情况。实验结果表明,相比于其他经典调度算法,在不同类型工作流测试下,DCCO具有最高的成功率,且满足截止时间约束,同时可以优化执行成本。
中图分类号:
[1]JUVE G,CHERVENAK A,DEELMAN E,et al.Characterizing and profiling scientific workflows[J].Future Generation Computer Systems,2013,29(3):682-692. [2]ZHOU N,LIN W,FENG W,et al.Budget-deadline constrained approach for scientific workflows scheduling in a cloud environment[C]//2017 IEEE International Conference on Computational Science and Engineering(CSE) and IEEE International Conference on Embedded and Ubiquitous Computing(EUC).Guangzhou,China,2017,7-14. [3]ALKHANAK E N,LEE S P,REZAEI R,et al.Cost optimization approaches for scientific workflow scheduling in cloud and grid computing:A review,classifications,and open issues[J].Journal of Systems and Software,2016,10(1),3-52. [4]MARIA A R,RAJKUMAR B.Deadline Based Resource Provisioning and Scheduling Algorithm for Scientific Workflows on Clouds[J].IEEE Transactions on Cloud Computing,2014,2(2):222-235. [5]ISMAYILOV G,TOPCUOGLU H R.Neural network basedmulti-objective evolutionary algorithm for dynamic workflow scheduling in cloud computing[J].Future Generation Computer Systems,2020,102(4):307-322. [6]SAHAR S,REIHANEH K,SOMAYE G B,et al.Improvedmany-objective particle swarm optimization algorithm for scientific workflow scheduling in cloud computing[J].Computers & Industrial Engineering,2020,147(2):1-23. [7]MBOULA J E N,KAMLA V C,CLEMENTIN T D.Cost-time trade-off efficient workflow scheduling in cloud[J].Simulation Modelling Practice and Theory,2020,103(2):102-122. [8]ZHANG L,ZHOU L,SALAH A.Efficient scientific workflow scheduling for deadline-constrained parallel tasks in cloud computing environments[J]..Information Sciences,2020,531(3):31-46. [9]KAUR S,BAGGA P,HANS R,et al.Quality of Service(QoS) Aware Workflow Scheduling(WFS) in Cloud Computing:A Systematic Review[J].Arabian Journal for Science and Engineering,2018,3(1):1-31. [10]ZHU M M,CAO F,WU C Q.High-Throughput ScientificWorkflow Scheduling under Deadline Constraint in Clouds[J].Journal of Communications,2014,9(4):312-321. [11]SAEID A,MAHMOUD N,DICK H E,et al.Deadline-constrained workflow scheduling algorithms for Infrastructure as a Ser-vice Cloud[J].Future Generation Computer Systems,2013,29(5):158-169. [12]VERMA A.Budget constrained priority based genetic algorithm for workflow scheduling in cloud [C]//Communication & Computing.Chandigarh,India,2013,216-222. [13]JIAN C,WANG Y,TAO M,et al.Time-Constrained Workflow Scheduling In Cloud Environment Using Simulation Annealing Algorithm[J].Journal of Engineering Science & Technology Review,2013,6(5):33-37. [14]BILGAIYAN S,SAGNIKA S,DAS M.Workflow scheduling in cloud computing environment using Cat Swarm Optimization[C]//4th IEEE International Advance Computing(IACC).Busan,Korea,2014:680-685. [15]ZHOU Y,HUANG X.Scheduling Workflow in Cloud Computing Based on Ant Colony Optimization Algorithm[C]//Sixth International Conference on Business Intelligence & Financial Engineering.Hangzhou,China:2013:57-61. [16]GOGULAN R,KAVITHA A,KUMAR U K.An MultiplePheromone Algorithm for Cloud Scheduling With Various QoS Requirements[J].International Journal of Computer ence Issues,2012,9(3):66-70. [17]WU H,TANG Z,LI R.A priority constrained scheduling strategy of multiple workflows for cloud computing[C]//Interna-tional Conference on Advanced Communication Technology.IEEE,2012:1086-1089. [18]ZHANG X.Scheduling of cloud workflow on budget and deadline constraints[D].Chongqing:Chongqing University,2017. [19]GAO T Y.Research on algorithms of minimizing financial cost of cloud workflow under deadline constraints[D].Xi’an:Northwest University,2019. [20]YU K J,ZHANG J Z.Cloud workflow scheduling genetic algorithm of cost optimization under deadline constraint[J].Computer Engineering and Design,2018,39(7):1938-1945. [21]CHEN Y T,PEI S J,MIAO H.Cost-optimized scheduling algorithm for cloud scientific workflow with deadline constraint[J].Journal of Frontier of Computer Science ang Technology,2019,13(8)1307-1318. [22]WU Q,FUYUKI I,QINGSHENG Z,et al.Deadline-Constrained Cost Optimization Approaches for Workflow Scheduling in Clouds[J].IEEE Transactions on Parallel and Distributed Systems,2017,28(12):99-109. [23]JUVE G,CHERVENAK A,DEELMAN E,et al.Characterizing and profiling scientific workflows[J].Future Generation Computer Systems,2013,29(3):682-692. |
[1] | 鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩. 基于分层抽样优化的面向异构客户端的联邦学习 Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients 计算机科学, 2022, 49(9): 183-193. https://doi.org/10.11896/jsjkx.220500263 |
[2] | 邵子灏, 杨世宇, 马国杰. 室内信息服务的基础——低成本定位技术研究综述 Foundation of Indoor Information Services:A Survey of Low-cost Localization Techniques 计算机科学, 2022, 49(9): 228-235. https://doi.org/10.11896/jsjkx.210900260 |
[3] | 王灿, 刘永坚, 解庆, 马艳春. 基于软标签和样本权重优化的Anchor Free目标检测算法 Anchor Free Object Detection Algorithm Based on Soft Label and Sample Weight Optimization 计算机科学, 2022, 49(8): 157-164. https://doi.org/10.11896/jsjkx.210600240 |
[4] | 陈俊, 何庆, 李守玉. 基于自适应反馈调节因子的阿基米德优化算法 Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor 计算机科学, 2022, 49(8): 237-246. https://doi.org/10.11896/jsjkx.210700150 |
[5] | 李其烨, 邢红杰. 基于最大相关熵的KPCA异常检测方法 KPCA Based Novelty Detection Method Using Maximum Correntropy Criterion 计算机科学, 2022, 49(8): 267-272. https://doi.org/10.11896/jsjkx.210700175 |
[6] | 王兵, 吴洪亮, 牛新征. 基于改进势场法的机器人路径规划 Robot Path Planning Based on Improved Potential Field Method 计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020 |
[7] | 唐枫, 冯翔, 虞慧群. 基于自适应知识迁移与资源分配的多任务协同优化算法 Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation 计算机科学, 2022, 49(7): 254-262. https://doi.org/10.11896/jsjkx.210600184 |
[8] | 张翀宇, 陈彦明, 李炜. 边缘计算中面向数据流的实时任务调度算法 Task Offloading Online Algorithm for Data Stream Edge Computing 计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195 |
[9] | 赵冬梅, 吴亚星, 张红斌. 基于IPSO-BiLSTM的网络安全态势预测 Network Security Situation Prediction Based on IPSO-BiLSTM 计算机科学, 2022, 49(7): 357-362. https://doi.org/10.11896/jsjkx.210900103 |
[10] | 李亚茹, 张宇来, 王佳晨. 面向超参数估计的贝叶斯优化方法综述 Survey on Bayesian Optimization Methods for Hyper-parameter Tuning 计算机科学, 2022, 49(6A): 86-92. https://doi.org/10.11896/jsjkx.210300208 |
[11] | 康雁, 王海宁, 陶柳, 杨海潇, 杨学昆, 王飞, 李浩. 混合改进的花授粉算法与灰狼算法用于特征选择 Hybrid Improved Flower Pollination Algorithm and Gray Wolf Algorithm for Feature Selection 计算机科学, 2022, 49(6A): 125-132. https://doi.org/10.11896/jsjkx.210600135 |
[12] | 黄国兴, 杨泽铭, 卢为党, 彭宏, 王静文. 利用粒子滤波方法求解数据包络分析问题 Solve Data Envelopment Analysis Problems with Particle Filter 计算机科学, 2022, 49(6A): 159-164. https://doi.org/10.11896/jsjkx.210600110 |
[13] | 鲁晨阳, 邓苏, 马武彬, 吴亚辉, 周浩浩. 基于DBSCAN聚类的集群联邦学习方法 Clustered Federated Learning Methods Based on DBSCAN Clustering 计算机科学, 2022, 49(6A): 232-237. https://doi.org/10.11896/jsjkx.211100059 |
[14] | 陈钧吾, 余华山. 面向无尺度图的Δ-stepping算法改进策略 Strategies for Improving Δ-stepping Algorithm on Scale-free Graphs 计算机科学, 2022, 49(6A): 594-600. https://doi.org/10.11896/jsjkx.210400062 |
[15] | 刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems 计算机科学, 2022, 49(6A): 619-627. https://doi.org/10.11896/jsjkx.210600165 |
|