基于自适应惩罚函数的云工作流调度协同进化遗传算法

doi:10.11896/j.issn.1002-137X.2018.08.019

计算机科学 ›› 2018, Vol. 45 ›› Issue (8): 105-112.doi: 10.11896/j.issn.1002-137X.2018.08.019

基于自适应惩罚函数的云工作流调度协同进化遗传算法

徐健锐^1,2, 朱会娟³

江苏大学计算机科学与通信工程学院江苏镇江212013¹
江苏联合职业技术学院镇江分院江苏镇江212016²
中国科学院大学计算机与控制学院北京100049³

收稿日期:2017-07-04 出版日期:2018-08-29 发布日期:2018-08-29
作者简介:徐健锐(1975-),男,硕士,副教授,主要研究方向为复杂网络预测与评价、云计算与大数据分析、教育信息化及职业教育人才培养模式,E-mail:zjxjr@126.com(通信作者); 朱会娟(1984-),女,博士生,主要研究方向为数据清洗、数据融合、数据分析。
基金资助:
本文受国家自然科学基金项目(61302124),江苏省高校自然科学研究面上项目(16KJB520010)资助。

Coevolutionary Genetic Algorithm of Cloud Workflow Scheduling Based on Adaptive Penalty Function

XU Jian-rui^1,2, ZHU Hui-juan³

School of Computer Science and Telecommunication Engineering,Jiangsu University,Zhenjiang,Jiangsu 212013,China¹
Zhenjiang Branch,Jiangsu Union Technical Institute,Zhenjiang,Jiangsu 212016,China²
School of Computer and Control Engineering,University of Chinese Academy of Sciences,Beijing 100049,China³

Received:2017-07-04 Online:2018-08-29 Published:2018-08-29

摘要/Abstract

摘要： 云计算为大规模科学工作流应用的执行提供了更高效的运行环境。为了解决云环境中科学工作流调度的代价优化问题,提出了一种基于协同进化的工作流调度遗传算法CGAA。该算法将自适应惩罚函数引入严格约束的遗传算法中,通过协同进化的方法,自适应地调整种群个体的交叉与变异概率,以加速算法收敛并防止种群早熟。通过4种科学工作流的仿真实验结果表明,CGAA算法得到的调度方案在满足工作流调度截止时间约束与降低任务执行代价的综合性能方面优于同类型算法。

关键词: 科学工作流, 任务调度, 协同进化, 遗传算法, 云计算

Abstract: The cloud computing provides a more efficient operation environment for the execution of large-scale scienti-fic workflow application.To solve thecost optimization problem of the scientific workflow scheduling in the cloud environment,a workflow scheduling genetic algorithm based on coevolution was proposed.This algorithm introduces an adaptive penalty function into GA with the strict constraints.By the coevolutionary approach,it can adjustthe crossover and mutation probability of population individuals adaptively to accelerate the convergence of the algorithm and prevent the prematurity ofpopulation.The simulation experiment results of four kinds of scientific workflow in reality show that the scheduling scheme obtained by the CGAA algorithm performs better in satisfying the comprehensive perfor-mance of the workflow scheduling deadline constraints and reducing the total execution cost of tasks compared with the same types of algorithms.

Key words: Cloud computing, Coevolution, Genetic algorithm, Scientific workflow, Tasks scheduling

中图分类号:

TP393

徐健锐, 朱会娟. 基于自适应惩罚函数的云工作流调度协同进化遗传算法[J]. 计算机科学, 2018, 45(8): 105-112. https://doi.org/10.11896/j.issn.1002-137X.2018.08.019

XU Jian-rui, ZHU Hui-juan. Coevolutionary Genetic Algorithm of Cloud Workflow Scheduling Based on Adaptive Penalty Function[J]. Computer Science, 2018, 45(8): 105-112. https://doi.org/10.11896/j.issn.1002-137X.2018.08.019

参考文献

[1]KASHLEV A,LU S.A System Architecture for Running BigData Workflows in the Cloud[C]∥IEEE InternationalConfe-rence on Services Computing.IEEE,2014:51-58.
[2]LIU L,ZHANG M,LIN Y,et al.A survey on workflow mana-gement and scheduling in cloud computing[C]∥14th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.IEEE,2014:837-846.
[3]WU F,WU Q,TAN Y.Workflow scheduling in cloud:a survey[J].Journal of Supercomputing,2015,71(9):3373-3418.
[4]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.
[5]WANG X,YEO C S,BUYYA R.Optimizing the makespan and reliability for workflow applications with reputation and a look-ahead genetic algorithm[J].Future Generation Compututer Systems,2011,27(8):1124-1134.
[6]HUANG T T,LIANG Y W.Improved simulated annealing algorithm of cloud workflow tasks scheduling.Micro-electro-nics and Computer,2016,1(33):42-46.(in Chinese)黄婷婷,梁意文.云工作流任务调度的模拟退火遗传改进算法[J].微电子学与计算机,2016,1(33):42-46.
[7]FELLER E,RILLING L,MORIN C.Energy-aware ant colonybased workload placement in clouds[C]∥Proceedings of the 2014 IEEE/ACM 13th International Conference on Grid Computing.IEEE Computer Society,2014:26-33.
[8]HUANG J.The workflow task scheduling algorithm based onthe GA model in the cloud computing environment[J].Journal of Software,2014,9(4):873-880.
[9]CAO B,WANG X T,XIONG L R,et al.Particle swarm sear-ching method of cloud workflow scheduling under time constraint.Computer Intergrated Manufacturing Systems,2016,22(2):372-380.(in Chinese)曹斌,王小统,熊丽荣,等.时间约束云工作流调度的粒子群搜索方法[J].计算机集成制造系统,2016,22(2):372-380.
[10]LI Y L,SHAO W,WANG J T,et al.An improved NSGA-II and its application for reconfigurable pixel antenna design[J].Radio Engineering,2014,23(2):733-738.
[11]ZHU Z,ZHANG G,LI M,et al.Evolutionary Multi-Objective Workflow Scheduling in Cloud[J].IEEE Transactions on Parallel & Distributed Systems,2016,27(5):1344-1357.
[12]RAHMAN M,HASSAN R,RANJAN R,et al.Adaptive workflow scheduling for dynamic grid and cloud computing environment[J].Concurrency Compututation Practicew Experience,2013,25(13):1816-1842.
[13]RODRIGO C,RAJIV R,ANTON B,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.
[14]CHEN W,DEELMAN E.WorkflowSim:a toolkit for simulating scientific workflows in distributed environments[C]∥IEEE 8th International Conference on E-Science (e-Science).IEEE,2012:1-8.
[15]JUVE G,CHERVENAK A,DEELMAN E,et al.Characterizing and profiling scientific workflows[J].Future Generation Computer Systems,2013,29(3):682-692.
[16]Amazon.Amazon EC2 Pricing[EB/OL].http://aws.amazon.com/ec2/pricing.
[17]TOPCUOGLU H,HARIRI S,WU M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Transactions on Parallel Distributed Systems,2012,13(3):260-274.
[18]PANDEY S,WU L,GURU S M,et al.A particle swarm optimizationbased heuristic for scheduling workflow applications in cloud computing environments[C]∥24th IEEE International Conference on Advanced Information Networking and Applications.IEEE,2014:400-407.

相关文章 15

[1]	杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[2]	田冰川, 田臣, 周宇航, 陈贵海, 窦万春. 减少Hadoop集群中网络队头阻塞的调度算法 Reducing Head-of-Line Blocking on Network in Hadoop Clusters 计算机科学, 2022, 49(3): 11-22. https://doi.org/10.11896/jsjkx.210900117
[3]	高诗尧, 陈燕俐, 许玉岚. 云环境下基于属性的多关键字可搜索加密方案 Expressive Attribute-based Searchable Encryption Scheme in Cloud Computing 计算机科学, 2022, 49(3): 313-321. https://doi.org/10.11896/jsjkx.201100214
[4]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[5]	谭双杰, 林宝军, 刘迎春, 赵帅. 基于机器学习的分布式星载RTs系统负载调度算法 Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning 计算机科学, 2022, 49(2): 336-341. https://doi.org/10.11896/jsjkx.201200126
[6]	吴善杰, 王新. 基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法 Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks 计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110
[7]	王政, 姜春茂. 一种基于三支决策的云任务调度优化算法 Cloud Task Scheduling Algorithm Based on Three-way Decisions 计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023
[8]	郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131
[9]	王金恒, 单志龙, 谭汉松, 王煜林. 基于遗传优化PNN神经网络的网络安全态势评估 Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network 计算机科学, 2021, 48(6): 338-342. https://doi.org/10.11896/jsjkx.201200239
[10]	潘瑞杰, 王高才, 黄珩逸. 云计算下基于动态用户信任度的属性访问控制 Attribute Access Control Based on Dynamic User Trust in Cloud Computing 计算机科学, 2021, 48(5): 313-319. https://doi.org/10.11896/jsjkx.200400013
[11]	陈玉平, 刘波, 林伟伟, 程慧雯. 云边协同综述 Survey of Cloud-edge Collaboration 计算机科学, 2021, 48(3): 259-268. https://doi.org/10.11896/jsjkx.201000109
[12]	王文娟, 杜学绘, 任志宇, 单棣斌. 基于因果知识和时空关联的云平台攻击场景重构 Reconstruction of Cloud Platform Attack Scenario Based on Causal Knowledge and Temporal- Spatial Correlation 计算机科学, 2021, 48(2): 317-323. https://doi.org/10.11896/jsjkx.191200172
[13]	蒋慧敏, 蒋哲远. 企业云服务体系结构的参考模型与开发方法 Reference Model and Development Methodology for Enterprise Cloud Service Architecture 计算机科学, 2021, 48(2): 13-22. https://doi.org/10.11896/jsjkx.200300044
[14]	左剑凯, 吴杰宏, 陈嘉彤, 刘泽源, 李忠智. 异构无人机编队防御及评估策略研究 Study on Heterogeneous UAV Formation Defense and Evaluation Strategy 计算机科学, 2021, 48(2): 55-63. https://doi.org/10.11896/jsjkx.191100053
[15]	高帅, 夏良斌, 盛亮, 杜宏亮, 袁媛, 韩和同. 基于投影圆度和遗传算法的空间圆柱面拟合方法 Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm 计算机科学, 2021, 48(11A): 166-169. https://doi.org/10.11896/jsjkx.201100057

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于自适应惩罚函数的云工作流调度协同进化遗传算法

Coevolutionary Genetic Algorithm of Cloud Workflow Scheduling Based on Adaptive Penalty Function

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0