Research output

Scheduling unit-length jobs with precedence constraints of small height

Research output: Contribution to journalArticleAcademicpeer-review

Standard

Scheduling unit-length jobs with precedence constraints of small height. / Berger, A.; Grigoriev, A.; Heggernes, P.; van der Zwaan, G.R.J.

In: Operations Research Letters, Vol. 42, No. 2, 01.01.2014, p. 166-172.

Research output: Contribution to journalArticleAcademicpeer-review

Harvard

APA

Vancouver

Author

Berger, A. ; Grigoriev, A. ; Heggernes, P. ; van der Zwaan, G.R.J. / Scheduling unit-length jobs with precedence constraints of small height. In: Operations Research Letters. 2014 ; Vol. 42, No. 2. pp. 166-172.

Bibtex

@article{5e28b37948234eb6825a6d7921b5dba7,
title = "Scheduling unit-length jobs with precedence constraints of small height",
abstract = "We consider the problem of scheduling unit-length jobs on identical machines subject to precedence constraints. We show that natural scheduling rules fail when the precedence constraints form a collection of stars or a collection of complete bipartite graphs. We prove that the problem is in fact NP-hard on collections of stars when the input is given in a compact encoding, whereas it can be solved in polynomial time with standard adjacency list encoding. On a subclass of collections of stars and on collections of complete bipartite graphs we show that the problem can be solved in polynomial time even when the input is given in compact encoding, in both cases via non-trivial algorithms.",
author = "A. Berger and A. Grigoriev and P. Heggernes and {van der Zwaan}, G.R.J.",
note = "NO DATA USED",
year = "2014",
month = "1",
day = "1",
doi = "10.1016/j.orl.2014.01.008",
language = "English",
volume = "42",
pages = "166--172",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier Science",
number = "2",

}

RIS

TY - JOUR

T1 - Scheduling unit-length jobs with precedence constraints of small height

AU - Berger, A.

AU - Grigoriev, A.

AU - Heggernes, P.

AU - van der Zwaan, G.R.J.

N1 - NO DATA USED

PY - 2014/1/1

Y1 - 2014/1/1

N2 - We consider the problem of scheduling unit-length jobs on identical machines subject to precedence constraints. We show that natural scheduling rules fail when the precedence constraints form a collection of stars or a collection of complete bipartite graphs. We prove that the problem is in fact NP-hard on collections of stars when the input is given in a compact encoding, whereas it can be solved in polynomial time with standard adjacency list encoding. On a subclass of collections of stars and on collections of complete bipartite graphs we show that the problem can be solved in polynomial time even when the input is given in compact encoding, in both cases via non-trivial algorithms.

AB - We consider the problem of scheduling unit-length jobs on identical machines subject to precedence constraints. We show that natural scheduling rules fail when the precedence constraints form a collection of stars or a collection of complete bipartite graphs. We prove that the problem is in fact NP-hard on collections of stars when the input is given in a compact encoding, whereas it can be solved in polynomial time with standard adjacency list encoding. On a subclass of collections of stars and on collections of complete bipartite graphs we show that the problem can be solved in polynomial time even when the input is given in compact encoding, in both cases via non-trivial algorithms.

U2 - 10.1016/j.orl.2014.01.008

DO - 10.1016/j.orl.2014.01.008

M3 - Article

VL - 42

SP - 166

EP - 172

JO - Operations Research Letters

T2 - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 2

ER -