competitive analysis – Optimization Online

On-Line Scheduling to Minimize Average Completion Time Revisited

Published: 2003/09/30, Updated: 2004/02/25

Approximation Algorithms, Combinatorial Optimization, Scheduling approximation algorithms, competitive analysis, on-line algorithm, scheduling

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. CitationWorking Paper 4435-03, Sloan School … Read more