Technical Report 022-2003

Title
On-line scheduling to minimize average completion time revisited
Authors
Nicole Megow and Andreas S. Schulz
Publication
Operations Research Letters 32 (2004), pp. 485-490
Source
Download as [PDF] [ps.gz]
Classification
not available
Keywords
scheduling, on-line algorithms, approximation algorithms, deterministic, competitive analysis, average completion time
Abstract
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.