A LOWER-BOUND FOR RANDOMIZED ONLINE SCHEDULING ALGORITHMS

Authors
CHEN B VANVLIET A WOEGINGER GJ
Citation
B. Chen et al., A LOWER-BOUND FOR RANDOMIZED ONLINE SCHEDULING ALGORITHMS, Information processing letters, 51(5), 1994, pp. 219-222
Citations number
4
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
51
Issue
5
Year of publication
1994
Pages
219 - 222
Database
ISI
SICI code
0020-0190(1994)51:5<219:ALFROS>2.0.ZU;2-7
Abstract
We prove that any randomize dalgorithm for on-line scheduling jobs on m identical parallel machines must have a worst case ration at least m (m)/m(m)-(m-1)(m)) for every m, which tends to e/(e-1) approximate to 1.58 as m --> infinity. This answers a question posed in a recent pape r by Bartal, Fiat, Karloff and Vohra.