In this paper, we provide a new class of randomized
approximation
algorithms for parallel machine scheduling problems. The most
general model we consider is scheduling unrelated machines with
release dates (or even network scheduling) so as to minimize the
average weighted completion time. We introduce an LP relaxation in
time-indexed variables for this problem. The crucial idea to derive
approximation results is not to use standard list scheduling, but
rather to assign jobs randomly to machines (by interpreting
LP solutions as probabilities), and to perform list
scheduling on each of them. Our main result is a
(2+varepsilon)-approximation algorithm for this general model
which improves upon performance guarantee 16/3 due to
Hall, Shmoys, and Wein. In the absence of nontrivial release dates,
we get a (3/2+varepsilon)-approximation. At the same
time we prove corresponding bounds on the quality of the LP
relaxation.
A perhaps surprising implication for identical parallel machines is
that jobs are randomly assigned to machines, in which each machine
is equally likely. In addition, in this case the algorithm has
running time O(n log n) and performance guarantee 2. Moreover,
the value of the nonpreemptive schedule computed by the algorithm is
also within a bound of 2 of the value of an optimal preemptive
schedule, which implies a bound on the power of preemption. Finally,
the approximation results for identical parallel machine
scheduling apply to both the offline and the online settings with
no difference in performance guarantee.
