We give a (2+ϵ)-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture on the approximability of this scheduling problem (Skutella, 2016).

Additional Metadata
Keywords Approximation algorithm, Precedence constraints, Scheduling, Total weighted completion time
Persistent URL dx.doi.org/10.1016/j.orl.2018.05.007
Journal Operations Research Letters
Sitters, R.A, & Yang, L. (2018). A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective. Operations Research Letters, 46(4), 438–442. doi:10.1016/j.orl.2018.05.007