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: | Schulz Andreas S., Skutella Martin |
Keywords: | production |
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