The power of α-points in preemptive single machine scheduling

The power of α-points in preemptive single machine scheduling

0.00 Avg rating0 Votes
Article ID: iaor20041564
Country: United Kingdom
Volume: 5
Issue: 2
Start Page Number: 121
End Page Number: 133
Publication Date: Mar 2002
Journal: Journal of Scheduling
Authors: ,
Keywords: production
Abstract:

We consider the NP-hard preemptive single-machine scheduling problem to minimize the total weighted completion time subject to release dates. A natural extension of Smith's ratio rule is to preempt the currently active job whenever a new job arrives that has higher ratio of weight to processing time. We prove that the competitive ratio of this simple on-line algorithm is precisely 2. We also show that list scheduling in order of random α-points drawn from the same schedule results in an on-line algorithm with competitive ratio 4/3. Since its analysis relies on a well-known integer programming relaxation of the scheduling problem, the relaxation has performance guarantee 4/3 as well. On the other hand, we show that it is at best an 8/7-relaxation.

Reviews

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