Three characteristics encountered frequently in real-world
machine scheduling are jobs released over time, precedence constraints
between jobs, and average performance optimization. The general constrained
one-machine scheduling problem to minimize the average weighted
completion time not only captures these features, but also is an
important building block for more complex problems involving multiple
machines.
In this context, the conversion of preemptive to nonpreemptive schedules has
been established as a strong and useful tool for the design of approximation
algorithms. The preemptive problem is already NP-hard, but
one can generate good preemptive schedules from LP relaxations in
time-indexed variables. However, a straightforward
combination of these two components does not directly lead to improved
approximations. By showing schedules in slow motion, we introduce a new point
of view on the generation of preemptive schedules from LP-solutions
which also enables us to give a better analysis.
Specifically, this leads to a randomized approximation algorithm for
the general constrained one-machine scheduling problem with expected
performance guarantee e. This improves upon the best previously
known worst-case bound of 3. In the process, we also give randomized
algorithms for related problems involving precedences that
asymptotically match the best previously known performance
guarantees.
In addition, by exploiting a different technique, we give a simple
3/2-approximation algorithm for unrelated parallel machine
scheduling to minimize the average weighted completion time.
It relies on random machine assignments where these random
assignments are again guided by an optimum solution to an LP
relaxation. For the special case of
identical parallel machines, this algorithm is as simple as the one of
Kawaguchi and Kyan, but allows for a remarkably simpler
analysis. Interestingly, its derandomized version actually is the algorithm
of Kawaguchi and Kyan.
