计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (10): 291-298.doi: 10.11896/jsjkx.220800039

• 计算机网络 • 上一篇    下一篇

云环境中面向可靠性约束的工作流调度策略研究

李金亮1,2, 林兵2,3, 陈星1,2   

  1. 1 福州大学计算机与大数据学院 福州350108
    2 福建省网络计算与智能信息处理重点实验室 福州350108
    3 福建师范大学物理与能源学院 福州350117
  • 收稿日期:2022-08-03 修回日期:2022-12-24 出版日期:2023-10-10 发布日期:2023-10-10
  • 通讯作者: 林兵(WheelLX@163.com)
  • 作者简介:(211027178@fzu.edu.cn)
  • 基金资助:
    国家自然科学基金(62072108);福建省自然科学基金杰青项目(2020J06014);福建省高校产学合作项目(2022H6024)

Reliability Constraint-oriented Workflow Scheduling Strategy in Cloud Environment

LI Jinliang1,2, LIN Bing2,3, CHEN Xing1,2   

  1. 1 College of Computer and Data Science,Fuzhou University,Fuzhou 350108,China
    2 Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information Processing,Fuzhou 350108,China
    3 College of Physics and Energy,Fujian Normal University,Fuzhou 350117,China
  • Received:2022-08-03 Revised:2022-12-24 Online:2023-10-10 Published:2023-10-10
  • About author:LI Jinliang,born in 1998,postgraduate,is a member of China Computer Federation.His main research interests include cloud computing and heuristic algorithms.LIN Bing,born in 1986,Ph.D,associate professor,postgraduate supervisor,is a member of China Computer Federation.His main research interests include cloud computing and intelligent computing and its application.
  • Supported by:
    National Natural Science Foundation of China(62072108),Natural Science Foundation of Fujian Province for Distinguished Young Scholars(2020J06014) and Fujian University Industry-University Cooperation Project(2022H6024).

PDF (PC)

1912

摘要： 随着越来越多的计算密集型依赖应用被卸载到云环境中执行,工作流调度问题受到了广泛的关注。针对云环境多目标优化的工作流调度问题,考虑到任务执行过程中服务器可能会发生性能波动和宕机等问题,基于模糊理论,使用三角模糊数表示任务执行时间和数据传输时间,提出了一种基于遗传算法的自适应粒子群优化算法(Adaptive Particle Swarm Optimization based GA,APSOGA),目的是在工作流的可靠性约束下,综合优化工作流的完成时间和执行代价。该算法为了避免传统粒子群优化算法存在的过早收敛问题,引入了遗传算法的随机两点交叉操作和单点变异操作,有效地提升了算法的搜索性能。实验结果表明,与其他策略相比,基于APSOGA的调度策略能够有效地降低云环境中面向可靠性约束的科学工作流的模糊总代价。

关键词: 云计算, 可靠性约束, 不确定性, 多目标优化, 三角模糊数

Abstract: As more and more computationally intensive dependent applications are offloaded to the cloud environment for execution,the problem of workflow scheduling has received extensive attention.Aiming at the workflow scheduling problem of multi-objective optimization in cloud environment,and considering that the server may experience performance fluctuations and downtime during task execution,based on fuzzy theory,a triangular fuzzy number is used to represent task execution time and data transmission time.A genetic algorithm-based adaptive particle swarm optimization based GA(APSOGA) is proposed.The purpose is to comprehensively optimize the completion time and execution cost of the workflow under the reliability constraints of the workflow.In order to avoid the premature convergence problem of the traditional particle swarm optimization algorithm,the proposed algorithm introduces the random two-point crossover operation and single-point mutation operation of the genetic algorithm,which effectively improves the search performance of the algorithm.Experimental results show that,compared with other strategies,APSOGA-based scheduling strategy can effectively reduce the time and cost of reliability-constrained scientific workflows in cloud environments.

Key words: Cloud computing, Reliability constraints, Uncertainty, Multi-objective optimization, Triangular fuzzy number

中图分类号: 

  • TP393
[1]LI H,WANG D,ZHOU M C,et al.Multi-Swarm Co-Evolution Based Hybrid Intelligent Optimization for Bi-Objective Multi-Workflow Scheduling in the Cloud[J].IEEE Transactions on Parallel and Distributed Systems,2021,33(9):2183-2197.
[2]RIZVI N,RAMESH D.HBDCWS:heuristic-based budget anddeadline constrained workflow scheduling approach for heterogeneous clouds[J].Soft Computing,2020,24(24):18971-18990.
[3]LIU J,REN J,DAI W,et al.Online multi-workflow scheduling under uncertain task execution time in IaaS clouds[J].IEEE Transactions on Cloud Computing,2019,9(3):1180-1194.
[4]ZHANG X.Multi-objective optimization of workflow scheduling in uncertain cloud environment[J].Computer Engineering and Design,2021,42(7):1948-1956.
[5]GAO D,WANG G G,PEDRYCZ W.Solving fuzzy job-shopscheduling problem using DE algorithm improved by a selection mechanism[J].IEEE Transactions on Fuzzy Systems,2020,28(12):3265-3275.
[6]SUN L,LIN L,GEN M,et al.A hybrid cooperative coevolution algorithm for fuzzy flexible job shop scheduling[J].IEEE Transactions on Fuzzy Systems,2019,27(5):1008-1022.
[7]YE L,XIA Y,YANG L,et al.Dynamic Scheduling StochasticMultiworkflows With Deadline Constraints in Clouds[J].IEEE Transactions on Automation Science and Engineering,2022.doi:10.1109/TASE.2022.3204313.
[8]GHAHRAMANI M H,ZHOU M C,HON C T.Toward cloud computing QoS architecture:Analysis of cloud systems and cloud services[J].IEEE/CAA Journal of Automatica Sinica,2017,4(1):6-18.
[9]WANG Y,ZUO X.An effective cloud workflow scheduling approach combining PSO and idle time slot-aware rules[J].IEEE/CAA Journal of Automatica Sinica,2021,8(5):1079-1094.
[10]LI H,WANG D,ZHOU M C,et al.Multi-Swarm Co-Evolution Based Hybrid Intelligent Optimization for Bi-Objective Multi-Workflow Scheduling in the Cloud[J].IEEE Transactions on Parallel and Distributed Systems,2021,33(9):2183-2197.
[11]FARAGARDI H R,SEDGHPOUR M R S,FAZLIAHMADI S,et al.GRP-HEFT:A budget-constrained resource provisioning scheme for workflow scheduling in IaaS clouds[J].IEEE Tran-sactions on Parallel and Distributed Systems,2019,31(6):1239-1254.
[12]WANG P,LEI Y,AGBEDANU P R,et al.Makespan-driven workflow scheduling in clouds using immune-based PSO algorithm[J].IEEE Access,2020,8:29281-29290.
[13]TAGHINEZHAD-NIAR A,PASHAZADEH S,TAHERI J.QoS-aware online scheduling of multiple workflows under task execution time uncertainty in clouds[J].Cluster Computing,2022,25(6):3767-3784.
[14]PHAM T P,FAHRINGER T.Evolutionary multi-objectiveworkflow scheduling for volatile resources in the cloud[J].IEEE Transactions on Cloud Computing,2020,10(3):1780-1791.
[15]CAO H,XU X,LIU Q,et al.Uncertainty-aware resource provisioning for workflow scheduling in edge computing environment[C]//2019 18th IEEE International Conference on Trust,Security and Privacy in Computing and Communications/13th IEEE International Conference on Big Data Science and Engineering(TrustCom/BigDataSE).IEEE,2019:734-739.
[16]LI K,ZHANG G,ZHU Z.A decomposition-based multi-objective workflow scheduling algorithm in cloud enviroment[J].Computer Engineering & Science,2016,38(8):1588-1594.
[17]LIN B,GUO W,CHEN G.Scheduling strategy for scienceworkflow with deadline constraint on multi-cloud[J].Journal on Communication,2018,39(1):56-69.
[18]MENG S,HUANG W,YIN X,et al.Security-aware dynamicscheduling for real-time optimization in cloud-based industrial applications[J].IEEE Transactions on Industrial Informatics,2020,17(6):4219-4228.
[19]LIN C,LIN B,CHEN X.Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment[J].Computer Science,2022,49(2):312-320.
[20]PALACIOS J J,GONZALEZ-RODRIGUEZ I,VELA C R,et al.Coevolutionary makespan optimisation through different ranking methods for the fuzzy flexible job shop[J].Fuzzy Sets and Systems,2015,278:81-97.
[21]LEE E S,LI R J.Comparison of fuzzy numbers based on theprobability measure of fuzzy events[J].Computers & Mathematics with Applications,1988,15(10):887-896.
[22]SAKAWA M,KUBOTA R.Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms[J].European Journal of Operational Research,2000,120(2):393-407.
[23]MASDARI M,SALEHI F,JALALI M,et al.A survey of PSO-based scheduling algorithms in cloud computing[J].Journal of Network and Systems Management,2017,25(1):122-158.
[24]GUO W,LIN B,CHEN G,et al.Cost-driven scheduling fordeadline-based workflow across multiple clouds[J].IEEE Transactions on Network and Service Management,2018,15(4):1571-1585.
[25]SHI Y,EBERHART R.A modified particle swarm optimizer[C]//1998 IEEE International Conference on Evolutionary Computation Proceedings.IEEE World Congress on Computational Intelligence(Cat.No.98TH8360).IEEE,1998:69-73.
[26]BHARATHI S,CHERVENAK A,DEELMAN E,et al.Characterization of scientific workflows[C]//2008 third Workshop on Workflows in support of Large-scale Science.IEEE,2008:1-10.
[27]JUVE G,CHERVENAK A,DEELMAN E,et al.Characterizing and profiling scientific workflows[J].Future Generation Computer Systems,2013,29(3):682-692.
[28]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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发