An Algorithm For Task Scheduling In A Heterogeneous Computing Environment

Grid Computing has been under research starting from late1980’s. Now it has become a very important computing paradigm especially for problems related to science, engineering, business and other fields which require an intensive computation. There exist many systems which employ grid computing with a lot of success. But as Grid Computing creates a very powerful computation environment it also brings many challenges, which normally do not exist in the traditional way of computing. Among the challenges, and most important, is scheduling. How to divide the big problem in to sub problems (sub tasks) and assign the sub problems (sub tasks) in to the many computation devices, which form the grid computing system, is a challenge. So the problem of scheduling comes as a very important challenge that must be dealt with, so that, to make the whole grid computing system a success. The matching of tasks to machines and scheduling the execution order of these tasks is referred to as mapping.The problem of mapping independent tasks in to heterogeneous computing systems so that the completion time of the last finishing computing system, called make-span, is minimum have been proved to be NP-Complete. As a result many heuristics exist in the literature for solving this problem. Among them, the algorithms HLTF(The Heterogeneous Largest Task First) and Segmented Min-Min have better make-spans with lower complexities.Here in this paper, we have devised a new heuristic called Heterogeneous Priority for Avoidance of Largest Penalty (HPALP) which implements the heuristics in HLJF and Segmented Min-Min by addressing the problem of HLTF’s lack of taking in to consideration the heterogeneity of machines and Segmented Min-Min’s not having a clear cut segments based on the heterogeneity of machines. The new proposed heuristic and several related ones have been implemented on a simulated Heterogeneous Computing (HC) environment which is based on simjava, the experimental results show that our heuristic outperforms the traditional ones.