2018-07-01
A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
Publication
Publication
Operations Research Letters , Volume 46 - Issue 4 p. 438- 442
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 | |
|---|---|
| , , , | |
| doi.org/10.1016/j.orl.2018.05.007 | |
| Operations Research Letters | |
| Organisation | 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 |
|
