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

Abstract: Workflow scheduling is a kind of economical and effective method in engineering management area. For optimizing the economical cost and scheduling efficiency of cloud workflow scheduling, a workflow scheduling algorithm based on Directed Acyclic Graph DAG partition PBWS is proposed. With the goal of optimizing synchronously the workflow scheduling efficiency and cost, our algorithm divides the scheduling solution into three stages: DAG partition of the workflow structure, partition structure adjustment and resource allocation. DAG partition of the workflow structure is to get the initial tasks partition graph when guarantees the execution order-dependency between tasks, the partition structure adjustemnt is to re-allocate tasks in different partitions with a goal of reducing execution makespan and the resource allocaiton is to determine the most cost-efficient mateches between tasks and resources ensuring the minization of the total idel time of resource. We construct some simulation experiments for algorithms by the five types of scientific workflow DAG model. The experimental results show PBWS can greatly reduce the execution cost of wrokflow in terms of cost by a large margin with litter overhead on execution makespan and realize the synchronous optimization of the scheuduling efficiency and the scheduling cost, whose overall performance performs better than the same type of algorithms.