The most common objective function of task scheduling problems is makespan. However, on a computational grid, the 2nd optimal makespan may be much longer than the optimal makespan because the computing power of a grid varies over time. So, if the performance measure is makespan, there is no approximation algorithm in general for scheduling onto a grid.
In contrast, recently the authors proposed the computing power consumed by a schedule as a criterion of the schedule and, for the criterion, gave (1+m(log(m-1)+1)/n) -approximation algorithm RR for scheduling nindependent coarse-grained tasks with the same length onto a grid with mprocessors. RR does not use any prediction information on the underlying resources. RR is the first approximation algorithm for grid scheduling.
However, so far any performance comparison among related heuristic algorithms is not given. This paper shows experimental results on the comparison of the consumed computing power of a schedule among RR and five related algorithms. It turns out that RR is next to the best of algorithms that need the prediction information on processor speeds and task lengths though RR does not require such information.
Source: Aminer
Authors: Noriyuki Fujimoto | Kenichi Hagihara
Scheduling Algorithms for Grid Computing: State of the Art and Open Problems
>> More Project Downloads on Grid Computing
>> Design, Modeling and Simulation Projects