TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2004

COGA 5-Wheel

Page Content

to Navigation

Preprints 2004

On-line scheduling to minimize average completion time revisited
Citation key Report-022-2003
Author Nicole Megow and Andreas S. Schulz
Year 2003
Number 022
Note In Operations Research Letters 32, pp. 485-490, 2004.
Institution Technische Universität Berlin, Institut für Mathematik
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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe