We consider the problem of scheduling n jobs with
release dates on m identical parallel machines to
minimize the average completion time of the jobs. We
prove that the ratio of the average completion time
of the optimal nonpreemptive schedule to that of the
optimal preemptive schedule 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 considered by Hall,
Schulz, Shmoys and Wein.
