In this paper, we provide a new class of randomized approximation
algorithms for scheduling problems by directly interpreting solutions
to so-called time-indexed LPs as probabilities.
The most general model we consider is scheduling unrelated parallel
machines with release dates (or even network scheduling) so as to
minimize the average weighted completion time. The crucial
idea for these multiple
machine problems is not to use standard list scheduling but rather to
assign jobs randomly to machines (with probabilities taken from an
optimal LP solution) and to perform list scheduling on each of them.
For the general model, we give a (2 + ε)-approximation
algorithm. The best previously known approximation algorithm has a
performance guarantee of 16/3.
Moreover, our algorithm also improves upon the best
previously known approximation algorithms for the special case of
identical parallel machine scheduling (performance guarantee `(2.89 +
ε) in general and 2.85` for the average
completion time, respectively). 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.
For minimizing the average weighted completion time on a single
machine under release dates, a refined version of our algorithm
produces in O}(n log n) time a schedule that is
expected to be within a factor of 1.6853 of the
optimum.
An appropriately
adapted version is a 4/3-approximation algorithm for
preemptive single machine scheduling to minimize the average
weighted completion time subject to release dates. This improves upon
a 1.466-approximation algorithm due to Goemans, Wein, and
Williamson.
Finally, the results for identical parallel machine as well as single
machine scheduling apply to both the off-line and the on-line settings
with no difference in performance guarantees. In the on-line setting,
we are scheduling jobs that continually arrive to be processed and,
for each time t, we must construct the schedule until time t
without any knowledge of the jobs that will arrive afterwards.
