  Two common objectives for evaluating a schedule are the makespan, or schedule
length, and the average completion time. This short note gives improved bounds
on the existence of schedules that simultaneously optimize both criteria. In
particular, for any rho> 0, there exists a schedule of makespan at most 1+rho
times the minimum, with average completion time at most (1-e)^rho times the
minimum. The proof uses an infininite-dimensional linear program to generalize
and strengthen a previous analysis by Cliff Stein and Joel Wein (1997).
