 | The ACM Journal of Experimental Algorithmics |
Volume 7, Article 3, 2002
An Experimental Study of Online Scheduling Algorithms
by
and
http://www.jea.acm.org/2002/AlbersOnline/
Abstract:
We present the first comprehensive experimental study of online algorithms
for Graham's scheduling problem. Graham's scheduling problem is a
fundamental problem in scheduling theory where a sequence of
jobs has to be scheduled on m identical parallel machines so as to minimize
the makespan. Graham gave an elegant algorithm that is (2-1/m)-competitive.
Recently a number of new online algorithms were developed that achieve
competitive ratios around 1.9. Since competitive analysis can only capture
the worst case behavior of an algorithm a question often asked is:
Are these new algorithms geared only towards a pathological
case or do they perform better in practice, too?
We address this question by analyzing the algorithms on various job sequences.
In our actual tests, we analyzed the algorithms
(1) on real world jobs
and (2) on jobs generated by probability distributions.
It turns out that the performance of the algorithms depends heavily
on the characteristics of the respective work load.
On job sequences that are generated by standard probability distributions,
Graham's strategy is clearly the best. However, on the real world jobs
the new algorithms often outperform Graham's strategy.
Our experimental study confirms theoretical results in the sense that
there are also job sequences in practice on which the new online algorithms
perform better. Our study can help to inform practitioners about the
new scheduling strategies as an alternative to Graham's algorithm.
Keywords: Online Algorithms, Experimentation, Performance, Scheduling
Categories: G.4 Mathematical Software: Algorithm Design and Analysis
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
|
|
|
|
Last updated and validated May 11, 2002, by editor@jea.acm.org