Scheduling to minimize average completion time: off-line and on-line algorithms

Time-indexed linear programming formulations have recently received a great deal of attention for their practical effectiveness in solving a number of single-machine scheduling problems. We show that these formulations are also an important tool in the design of approximation algorithms with good worst-case performance guarantees. We give simple new rounding techniques to convert an optimal fractional solution into a feasible schedule for which we can prove a constant-factor performance guarantee, thereby giving the first theoretical evidence of the strength of these relaxations. Specifically, we consider the problem of minimizing the total weighted job completion time on a single machine subject to precedence constraints, and give a polynomialtime (4 + ffl)-approximation algorithm, for any ffl ? 0; the best previously known guarantee for this problem was superlogarithmic. With somewhat larger constants, we also show how to extend this result to the case with release date constraints, ...