Abstract:

In this paper, the scheduling of independent tasks on the tree-based grid where resources have different computation and communication speeds is discussed. In contrast to minimizing the total execution time of tasks, this paper proposes an improved integral linear planning model. In order to overcome the time complexity when calculating the optimal number of tasks assigned to each node of the multi-level tree, the Push-Pull method is adopted to transform the linear planning of multi-level tree into a single-level one, thus greatly reducing the time complexity. Moreover, according to the calculated approximate number of the assigned optimal tasks, a static distributed heuristic task scheduling algorithm is put forward. Analytical and experimental results show that the proposed algorithm has better performance than other ones in the condition of scheduling lots of independent tasks on heterogeneous tree-based grid.

Key words: task scheduling, grid computing, linear planning, optimal task scheduling, distributed scheduling algorithm