云计算中一种高效的工作流调度方法

A HIGH-EFFICIENCY WORKFLOW SCHEDULING IN CLOUD COMPUTING

为了解决云计算科学工作流的调度问题,提出一种基于执行跨度和资源利用率为优化目标的工作流调度算法。在工作流结构层次基础上,将任务节点与虚拟机间的映射关系求解划分为两个阶段:第一阶段以最小最大标准化方式对层次的每个任务估计计算时间进行标准化操作,并计算任务阈值,从而将层次中的每个任务划分为大批任务和小批任务集合;第二阶段通过从估计计算时间矩阵中选择最小执行时间将任务调度至相应虚拟机上,并更新相应执行时间矩阵。分析算法的时间复杂度,通过算例详细说明算法执行过程。通过大规模仿真实验与4个基准算法进行对比分析。实验结果表明,在不同类型科学工作流测试下,该算法不仅可以最小化工作流的执行跨度,还可以确保更高的云资源利用率。

In order to solve the scheduling problem of scientific workflow in cloud computing,we propose a workflow scheduling algorithm based on execution makespan and resource utilization.Based on the leveling of workflow structure,our algorithm divides the mapping relationship solving between the task node and virtual machines into two stages.In the first stage,the estimated computation time of each task at each level was normalized by min-max normalization method,and the task threshold was calculated,so that each task at each level was divided into large and small batches.In the second stage,the tasks were scheduled to the VMs by choosing minimum execution time from estimated computation time and the matrix was updated.The time complexity of our algorithm was analyzed,and the process of our algorithm was described at detail by a numerical example.The algorithm was compared with four baseline algorithms through large-scale simulation experiments.The results show that our algorithm can not only minimize the execution makespan of workflow,but has a higher resource utilization rate of cloud in the test of different types of scientific workflow.