Many approximation results for single machine scheduling problems
rely on the conversion of preemptive schedules into (preemptive or
non-preemptive) solutions. The initial preemptive schedule is
usually an optimal solution to a combinatorial relaxation or a
linear programming relaxation of the scheduling problem under
consideration. It therefore provides a lower bound on the optimal
objective function value. However, it also contains structural
information which is useful for the construction of provably good
feasible schedules. In this context, list scheduling in order of
so-called α-points has evolved as an important and successful
tool. We give a survey and a uniform presentation of several
approximation results for single machine scheduling with total
weighted completion time objective from the last years which rely on
the concept of α-points.
