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

René Sitters, Liya Yang

Research output: Contribution to journalArticle

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

LanguageEnglish
Pages438-442
Number of pages5
JournalOperations Research Letters
Volume46
Issue number4
DOIs
StatePublished - Jul 2018

Fingerprint

Total Weighted Completion Time
Release Dates
Release Time
Precedence Constraints
Single Machine Scheduling
Approximability
Single Machine
Approximation algorithms
Scheduling Problem
Approximation Algorithms
Scheduling
Approximation
Release dates
Single machine scheduling
Single machine

Keywords

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

Cite this

@article{c24f462a882d466a8168ccbd628807e3,
title = "A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective",
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).",
keywords = "Approximation algorithm, Precedence constraints, Scheduling, Total weighted completion time",
author = "Ren{\'e} Sitters and Liya Yang",
year = "2018",
month = "7",
doi = "10.1016/j.orl.2018.05.007",
language = "English",
volume = "46",
pages = "438--442",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "4",

}

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

VL - 46

SP - 438

EP - 442

JO - Operations Research Letters

T2 - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 4

ER -