Online scheduling of a single machine to minimize total weighted completion time

Online scheduling of a single machine to minimize total weighted completion time

0.00 Avg rating0 Votes
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: ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.