DAG分割模型下的云工作流调度策略

为了优化云工作流调度的经济代价和执行效率，提出一种基于有向无循环图（DAG）分割的工作流调度算法PBWS。以工作流调度效率与代价同步优化为目标，算法将调度求解过程划分为三个阶段进行：工作流DAG结构分割、分割结构调整及资源分配。工作流DAG结构分割阶段在确保任务间执行顺序依赖的同时求解初始的任务分割图；分割结构调整阶段以降低执行跨度为目标，在不同分割间对任务进行重分配；资源分配阶段旨在选择代价最高效的任务与资源映射关系，确保资源的总空闲时间最小。利用五种科学工作流DAG模型对算法进行了仿真实验。结果表明。PBWS算法仅以较小的执行跨度为开销，极大降低了工作流执行代价，实现了调度效率与调度代价的同步优化，其综合性能是优于同类型算法的。

Cloud workflow scheduling strategy in DAG partition model

For optimizing the economical cost and scheduling efficiency of cloud workflow scheduling, this paper proposed a workflow scheduling algorithm PBWS based on DAG(directed acyclic graph) partition. With the goal of optimizing synchronously the workflow scheduling efficiency and cost, this algorithm divided the scheduling solution into three stages: DAG partition of the workflow structure, partition structure adjustment and resource allocation. DAG partition of the workflow structure was to get the initial tasks partition graph when guaranteeing the execution order-dependency between tasks. The partition structure adjustment was to re-allocate tasks in different partitions with a goal of reducing execution makespan. The resource allocation was to determine the most cost-efficient matches between tasks and resources ensuring the minimization of the total idle time of resource. This paper constructed some simulation experiments for algorithms by the five types of scientific workflow DAG model. The experimental results show PBWS algorithm can greatly reduce the execution cost of workflow in terms of cost by a little of overhead on execution makespan and realize the synchronous optimization of the scheduling efficiency and the scheduling cost, whose overall performance performs better than the same type of algorithms.