On-Line Scheduling to Minimize Average Completion Time Revisited

Nicole Megow (nmegowmath.TU-Berlin.DE)
Andreas S. Schulz (schulzmit.edu)

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.

Keywords: scheduling, on-line algorithm, approximation algorithm, competitive analysis

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Approximation Algorithms )

Category 3: Applications -- OR and Management Sciences (Scheduling )

Citation: Working Paper 4435-03, Sloan School of Management, Massachusetts Institute of Technology, September 2003, revised November 2003. Accepted for publication in Operations Research Letters, November 2003.

Download: [Postscript]

Entry Submitted: 09/30/2003
Entry Accepted: 10/01/2003
Entry Last Modified: 02/25/2004

Modify/Update this entry