ON-LINE SCHEDULING OF A SINGLE MACHINE TO MINIMIZE TOTAL WEIGHTED COMPLETION TIME
Professor Chris Potts, Faculty of Mathematical Studies, University of Southampton

Abstract: This talk considers the on-line scheduling of a single machine in which jobs arrive over time, and preemption is not allowed. The goal is to minimize the total weighted completion time. We show that a simple modification of the shortest weighted processing time rule has a competitive ratio of 2. This result is established using a new proof technique which does not rely explicitly on a lower bound on the optimal objective function value. Since it is known that no on-line algorithm can have a competitive ratio of less than 2, we have resolved the open issue of determining the minimum competitive ratio for this problem.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 12 March 2001.

back