ON THE EXISTENCE OF SCHEDULES THAT ARE NEAR-OPTIMAL FOR BOTH MAKESPANAND TOTAL WEIGHTED COMPLETION-TIME

We give a simple proof that, for any instance of a very general class of scheduling problems, there exists a schedule of makespan at most tw ice that of the optimal possible and of total weighted completion time at most twice that of the optimal possible, We then refine the analys is, yielding variants of this theorem with improved constants, and giv e some algorithmic consequences of the technique. (C) 1997 Elsevier Sc ience B.V.