最后期限动态分配的三步云工作流调度算法  

Three-step Cloud Workflow Scheduling Algorithm Based on Dynamic Deadline Distribution

作　　者：王子健 卢政昊 潘纪奎 孙福权 WANG Zi-jian;LU Zheng-hao;PAN Ji-kui;SUN Fu-quan(School of Mathematics and Statistics,Northeastern University at Qinhuangdao,Qinhuangdao 066000,China;College of Information Science and Engineering,Northeastern University,Shenyang 110000,China)

机构地区：[1]东北大学秦皇岛分校数学与统计学院,河北秦皇岛066000 [2]东北大学信息科学与工程学院,沈阳110000

出　　处：《小型微型计算机系统》2023年第2期248-255,共8页Journal of Chinese Computer Systems

基　　金：国家重点研发项目(2018YFB1402800)资助.

摘　　要：现如今,云环境中的工作流调度问题依然很有挑战性.它的一个重要任务是找到一种能够满足最后期限约束且执行成本最优的调度方案.三步的列表调度算法可以有效地解决这一问题.该算法首先将最后期限分配到每个任务,形成任务子期限;之后再利用两步列表调度策略为每个任务分配资源.然而现有的最后期限分配策略均只能形成静态的子期限,因此还可以进行进一步的优化.本文采用三步列表调度算法进行云工作流调度,并提出一种基于粒子群的动态最后期限分配方法(DY-DD).实验结果表明,相比于其它经典调度算法,本文提出的算法在成功率和执行成本上均具有优势.Nowadays,cloud workflow scheduling is still a challenging issue.One of its important tasks is to find a scheduling solution which meets the deadline and minimizes the cost.A three-step list scheduling algorithm can solve this problem.It first distributes the deadline to each task to form sub-deadline.Then two-step list scheduling strategy is applied to allocate resources to each task.However existing methods of deadline distribution can only form static sub-deadline,which can also be further optimized.We employ three-step list scheduling algorithm for cloud workflow scheduling,and propose a PSO-based dynamic deadline distribution(DY-DD).The experimental results show its advantage on cost and success rate.

关 键 词：云计算 工作流调度 最后期限 粒子群 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]