Article ID: | iaor20072290 |
Country: | United States |
Volume: | 29 |
Issue: | 3 |
Start Page Number: | 686 |
End Page Number: | 697 |
Publication Date: | Aug 2004 |
Journal: | Mathematics of Operations Research |
Authors: | Potts Chris N., Anderson Edward J. |
This paper considers the online 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 two. This result is established using a new proof technique that does not rely explicitly on a lower bound on the optimal objective function value. Because it is known that no online algorithm can have a competitive ratio of less than two, we have resolved the open issue of determining the minimum competitive ratio for this problem.