Scheduling unrelated machines by randomized rounding

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