Scheduling unrelated machines by randomized rounding

Andreas S. Schulz and Martin Skutella

SIAM Journal on Discrete Mathematics, to appear. This article combines the results from our ESA'97 paper (see Technical Report 533-1996) and from Section 4 of our Random'97 paper (see Technical Report 549-1997).

approximation algorithm, randomized rounding, LP relaxation, scheduling, online algorithm

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.

Download as [PDF] [ps.gz]