Title
On-line scheduling to minimize average completion time revisited
Authors
-
Publication
Operations Research Letters 32 (2004), pp. 485-490
Source
-
Classification
-
not available
Keywords
-
scheduling, on-line algorithms, approximation
algorithms, deterministic, competitive analysis, average completion time
-
-
We consider the scheduling problem of minimizing the average
weighted completion time on identical parallel machines when jobs
are arriving over time. For both the preemptive and the
nonpreemptive setting, we show that straightforward extensions of
Smith's ratio rule yield smaller competitive ratios than the
previously best-known deterministic on-line algorithms.