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.

关键词： Task scheduling Grid computing Linear planning Optimal scheduling scheme Distributed scheduling algorithm

作者: ZHEN-YU WANG CAN-CHENG YANG

作者单位: School of Computer Science and Engineering, South China University of Technology, 510641, Guangzhou, China

会议类型: 国际会议

会议名称: 2007 International Conference on Machine Learning and Cybernetics(IEEE第六届机器学习与控制论国际会议)

会议地点: 香港

会议语种:英文

页码: 3157-3163

在线出版日期: 2007-08-19（万方平台首次上网日期，不代表论文的发表时间）