A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

We present a e/(e−1)-approximation algorithm for the nonpreemptive scheduling problem to minimize the total weighted completion time of jobs on a single machine subject to release dates and precedence constraints. The previously best known approximation algorithm dates back to 1997; its performance guarantee can be made arbitrarily close to the Euler constant  e  (Schulz and Skutella, 1997).