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).

, , ,
doi.org/10.1016/j.orl.2018.05.007
Operations Research Letters
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

Sitters, R., & 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