TY - JOUR
T1 - Scheduling unit-length jobs with precedence constraints of small height
AU - Berger, A.
AU - Grigoriev, A.
AU - Heggernes, P.
AU - Zwaan, van der, G.R.J.
PY - 2014
Y1 - 2014
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.
Keywords: Scheduling; Precedence constraints; Computational complexity; Polynomial-time 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.
Keywords: Scheduling; Precedence constraints; Computational complexity; Polynomial-time algorithms
U2 - 10.1016/j.orl.2014.01.008
DO - 10.1016/j.orl.2014.01.008
M3 - Article
SN - 0167-6377
VL - 42
SP - 166
EP - 172
JO - Operations Research Letters
JF - Operations Research Letters
IS - 2
ER -