### An experimental study of online scheduling algorithmsAn experimental study of online scheduling algorithms

Access Restriction
Subscribed

 Author Albers, Susanne ♦ Schrder, Bianca Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2002 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Algorithms ♦ Experimentation ♦ Online algorithms ♦ Performance ♦ Scheduling 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 $\textit{m}$ identical parallel machines so as to minimize the makespan. Graham gave an elegant algorithm that is $(2-1/\textit{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. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2002-12-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 7 Starting Page 3

#### Open content in new tab

Source: ACM Digital Library