A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

René Sitters*, Liya Yang

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

42 Downloads (Pure)

Abstract

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

Original languageEnglish
Pages (from-to)438-442
Number of pages5
JournalOperations Research Letters
Volume46
Issue number4
Early online date13 Jun 2018
DOIs
Publication statusPublished - Jul 2018

Keywords

  • Approximation algorithm
  • Precedence constraints
  • Scheduling
  • Total weighted completion time

Fingerprint

Dive into the research topics of 'A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective'. Together they form a unique fingerprint.

Cite this