TY - GEN

T1 - An experimental study of online scheduling algorithms

AU - Albers, Susanne

AU - Schröder, Bianca

PY - 2001

Y1 - 2001

N2 - We present the first comprehensive experimental study of online algorithms for Graham's scheduling problem. In Graham's schedulingproblem, which is a fundamental and extensively studied problem in schedulingtheory, 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 analyzingthe algorithms on various job sequences. We have implemented a general testing environment that allows a user to generate jobs, execute the algorithms on arbitrary job sequences and obtain a graphical representation of the results. 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 and gives some new insights into the problem. In particular, it shows that the techniques used by the new online algorithms are also interesting from a practical point of view.

AB - We present the first comprehensive experimental study of online algorithms for Graham's scheduling problem. In Graham's schedulingproblem, which is a fundamental and extensively studied problem in schedulingtheory, 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 analyzingthe algorithms on various job sequences. We have implemented a general testing environment that allows a user to generate jobs, execute the algorithms on arbitrary job sequences and obtain a graphical representation of the results. 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 and gives some new insights into the problem. In particular, it shows that the techniques used by the new online algorithms are also interesting from a practical point of view.

UR - http://www.scopus.com/inward/record.url?scp=84896771815&partnerID=8YFLogxK

U2 - 10.1007/3-540-44691-5_2

DO - 10.1007/3-540-44691-5_2

M3 - Conference contribution

AN - SCOPUS:84896771815

SN - 3540425128

SN - 9783540425120

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 11

EP - 22

BT - Algorithm Engineering - 4th International Workshop, WAE 2000, Proceedings

A2 - Naher, Stefan

A2 - Wagner, Dorothea

PB - Springer Verlag

T2 - 4th International Workshop on Algorithm Engineering, WAE 2000

Y2 - 5 September 2000 through 8 September 2000

ER -