TY - JOUR
T1 - A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
AU - Sitters, René
AU - Yang, Liya
PY - 2018/7
Y1 - 2018/7
N2 - 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).
AB - 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).
KW - Approximation algorithm
KW - Precedence constraints
KW - Scheduling
KW - Total weighted completion time
UR - http://www.scopus.com/inward/record.url?scp=85048326206&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048326206&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2018.05.007
DO - 10.1016/j.orl.2018.05.007
M3 - Article
AN - SCOPUS:85048326206
SN - 0167-6377
VL - 46
SP - 438
EP - 442
JO - Operations Research Letters
JF - Operations Research Letters
IS - 4
ER -
