A $(2+\epsilon )$-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

René Sitters, Liya Yang

We give a $(2+\epsilon )$-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent c…