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

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