Model and Algorithms for Scheduling Independent Tasks on Heterogeneous Systems
In this paper,we study the problem of scheduling a set of independent tasks onto a heterogeneous system.The goal is to find a mapping of all tasks onto available resources such that the sum of costs of all tasks is minimized.While the difference of the number of tasks on any two machines is no more than one.We develop an integer programming(IP)formulation for modeling this problem.This problem is transformed to an assignment problem,and an optimal algorithm based on Hungary method is presented to solve this problem.To speedup the solution,two heuristics are also given.Experimental results show the correctness of the IP formulation and the effectiveness of our heuristics.
task scheduling heterogeneous computing unbalanced assignment problem Hungary method
Shang Mingsheng Wang Qingxian Fu Yan Li Jianping
国际会议
The International Conference Information Computing and Automation(2007国际信息计算与自动化会议)
成都
英文
691-694
2007-12-19（万方平台首次上网日期，不代表论文的发表时间）