IMPROVED BOUNDS ON RELAXATIONS OF A PARALLEL MACHINE SCHEDULING PROBLEM

We consider the problem of scheduling n jobs with release dates on m i dentical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion time of th e optimal nonpreemptive schedule to that of the optimal preemptive sch edule is at most 7/3, improving a bound of (3 - 1/m) due to Phillips, Stein and Wein. We then use our technique to give an improved bound on the quality of a linear programming relaxation of the problem conside red by Hall, Schulz, Shmoys and Wein.