| Article ID: | iaor20052154 |
| Country: | Netherlands |
| Volume: | 26 |
| Issue: | 1 |
| Start Page Number: | 17 |
| End Page Number: | 22 |
| Publication Date: | Feb 2000 |
| Journal: | Operations Research Letters |
| Authors: | Epstein Leah, Sgall Ji |
We consider the problem of on-line scheduling of jobs arriving one by one on uniformly related machines, with or without preemption. We prove a lower bound of 2, both with and without preemption, for randomized algorithms working for an arbitrary number of machines. For a constant number of machines we give new lower bounds for the preemptive case.