TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)Publications

COGA 5-Wheel

Page Content

to Navigation

List of all publications

Approximating Total Weighted Completion Time on Identical Parallel Machines with Precedence Constraints and Release Dates
Citation key Jaeger2018
Author Jäger, Sven
Pages 505–509
Year 2018
ISSN 0167-6377
DOI 10.1016/j.orl.2018.07.006
Journal Operations Research Letters
Volume 46
Number 5
Month September
Abstract We present a (2+2 ln 2 + ε)-approximation algorithm for the classical nonpreemptive scheduling problem to minimize the total weighted completion time of jobs on identical parallel machines subject to release dates and precedence constraints, improving upon the previously best known 4-approximation algorithm from 1998. The result carries over to the more general problem with precedence delays and generalizes a recent result by Li (2017) for the problem without release dates or delays.
Link to original publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe