loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2004 Symposium on Applications and the Internet-Workshops (SAINT 2004 Workshops)
A Comparison among Grid Scheduling Algorithms for Independent Coarse-Grained Tasks
Tokyo, Japan
January 26-January 30
ISBN: 0-7695-2050-2
Noriyuki Fujimoto, Osaka University
Kenichi Hagihara, Osaka University
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 + \frac{{m(\log _e (m - 1) + 1)}}{n})-approximation algorithm RR for scheduling n independent coarse-grained tasks with the same length onto a grid with m processors. 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.
Citation:
Noriyuki Fujimoto, Kenichi Hagihara, "A Comparison among Grid Scheduling Algorithms for Independent Coarse-Grained Tasks," saint-w, pp.674, 2004 Symposium on Applications and the Internet-Workshops (SAINT 2004 Workshops), 2004
Usage of this product signifies your acceptance of the Terms of Use.