Schulz, Andreas S.Skutella, Martin2021-12-172021-12-1719992197-8085https://depositonce.tu-berlin.de/handle/11303/15940http://dx.doi.org/10.14279/depositonce-14713We 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.en510 Mathematikscheduling theoryapproximation algorithmon-line algorithmrandomized algorithmLP relaxationcombinatorial optimizationResearch Paper