A lower bound for on-line scheduling on uniformly related machines

Authors
Epstein, L Sgall, J
Citation
L. Epstein et J. Sgall, A lower bound for on-line scheduling on uniformly related machines, OPER RES L, 26(1), 2000, pp. 17-22
Citations number
11
Categorie Soggetti
Engineering Mathematics
Journal title
OPERATIONS RESEARCH LETTERS
ISSN journal
01676377 → ACNP
Volume
26
Issue
1
Year of publication
2000
Pages
17 - 22
Database
ISI
SICI code
0167-6377(200002)26:1<17:ALBFOS>2.0.ZU;2-C
Abstract
We consider the problem of on-line scheduling of jobs arriving one by one o n uniformly related machines, with or without preemption. We prove a lower bound of 2, both with and without preemption, for randomized algorithms wor king for an arbitrary number of machines. For a constant number of machines we give new lower bounds for the preemptive case. (C) 2000 Elsevier Scienc e B.V. All rights reserved.