PRACTICAL SCHEDULING ALGORITHMS OF INDEPENDENT TASKS ON TREE-BASED GRID COMPUTING PLATFORM

摘要

This paper discusses scheduling independent tasks on tree-based grid computing platforms, where resources have different speeds of computation and communication.Instead of minimizing the total execution time, which has been proven to be NP-hard [1], we improve integral linear planning model in [2].Using this model, the time complexity is high to obtain optimal number of tasks assigned to each computing node of multi-level tree.To address this problem, Push-Pull method is given, which transforms the linear planning of multi-lever tree into single-level tree and therefore the time complexity is greatly reduced.Based on the optimal tasks assignment to each node, a static distributed heuristic task scheduling algorithm is put forward.Experimental results show that the algorithm achives better performance than other algorithms.