The power of α ‐points in preemptive single machine scheduling

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\over 3}$ . Since its analysis relies on a well‐known integer programming relaxation of the scheduling problem, the relaxation has performance guarantee ${4\over 3}$ as well. On the other hand, we show that it is at best an ${8\over 7}$ ‐relaxation. Copyright © 2002 John Wiley & Sons, Ltd.