A fully polynomial approximation scheme for the weighted earliness-tardiness problem

A fully polynomial approximation scheme for the problem of scheduling n job s on a single machine to minimize total weighted earliness and tardiness is presented. A new technique is used to develop the scheme. The main feature of this technique is that it recursively computes lower and upper bounds o n the value of partial optimal solutions. Therefore, the scheme does not re quire any prior knowledge of lower and upper bounds on the value of a compl ete optimal solution. This distinguishes it from all the existing approxima tion schemes.