Abstract: How to schedule dependent task efficiently is the key issue in cloud computing environment. The formal description of dependent task scheduler in cloud computing is presented. This paper adopts the weighted directed acyclic hypergraph as the mathematical model of the dependent task scheduling problem in cloud computing, whose vertex can be considered as the dependent task and directed hyperedge can be represented as the priority dependency among the tasks. Furthermore, it transforms the dependent task scheduling problem to the hypergraph partition problem and proposes the task partitioning algorithm based on the multilevel method and the weighted directed hypergraph. It also designs and implements the prototype system of the cloud computing dependent tasks schedule based on the multilevel method. It carries out the comparative experiments among the Min-Min algorithm, Max-Min algorithm and the proposed algorithm based on CloudSim simulation platform of cloud computing. The experiment and analysis show the proposed algorithm has better performance in terms of decreasing the task completing time and the improvement of resource load balancing.

Key words: cloud computing, task scheduling, weighted directed hypergraph, multi-level method, optimization algorithm

摘要： 如何对依赖任务进行高效合理的调度是云计算急需解决的关键问题之一。对云计算环境下的依赖任务调度系统进行了形式化描述。采用赋权有向无环超图来构造依赖任务调度问题的数学模型，结点对应于依赖任务，有向超边对应于任务之间的执行先后依赖关系。将云计算依赖任务调度问题转换为赋权有向超图的优化划分问题，提出了基于多水平方法和赋权有向超图的依赖任务划分优化算法。设计并实现了基于多水平方法的云计算依赖任务调度原型系统。在CloudSim云计算仿真实验平台下，与Min-Min算法、Max-Min算法进行了对比实验，实验数据对比表明该算法在减少依赖任务执行时间的同时，优化了资源负载均衡性能。

关键词: 云计算, 任务调度, 赋权有向超图, 多水平方法, 优化算法