TY - GEN
T1 - Precedence-constrained scheduling problems parameterized by partial order width
AU - van Bevern, René
AU - Bredereck, Robert
AU - Bulteau, Laurent
AU - Komusiewicz, Christian
AU - Talmon, Nimrod
AU - Woeginger, Gerhard J.
PY - 2016/1/1
Y1 - 2016/1/1
N2 - Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1–2):533–562), we show that P2|prec, pj∈{1, 2}|Cmax, the problem of finding a non-preemptive minimummakespan schedule for precedence-constrained jobs of lengths 1 and 2 on two parallel identical machines, is W[2]-hard parameterized by the width of the partial order giving the precedence constraints. To this end, we show that Shuffle Product, the problem of deciding whether a given word can be obtained by interleaving the letters of k other given words, is W[2]-hard parameterized by k, thus additionally answering a question posed by Rizzi and Vialette (CSR 2013). Finally, refining a geometric algorithm due to Servakh (Diskretn. Anal. Issled. Oper. 7(1):75–82), we show that the more general Resource-Constrained Project Scheduling problem is fixed-parameter tractable parameterized by the partial order width combined with the maximum allowed difference between the earliest possible and factual starting time of a job.
AB - Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1–2):533–562), we show that P2|prec, pj∈{1, 2}|Cmax, the problem of finding a non-preemptive minimummakespan schedule for precedence-constrained jobs of lengths 1 and 2 on two parallel identical machines, is W[2]-hard parameterized by the width of the partial order giving the precedence constraints. To this end, we show that Shuffle Product, the problem of deciding whether a given word can be obtained by interleaving the letters of k other given words, is W[2]-hard parameterized by k, thus additionally answering a question posed by Rizzi and Vialette (CSR 2013). Finally, refining a geometric algorithm due to Servakh (Diskretn. Anal. Issled. Oper. 7(1):75–82), we show that the more general Resource-Constrained Project Scheduling problem is fixed-parameter tractable parameterized by the partial order width combined with the maximum allowed difference between the earliest possible and factual starting time of a job.
KW - Makespan minimization
KW - Parallel identical machines
KW - Parameterized complexity
KW - Resource-constrained project scheduling
KW - Shuffle product
UR - http://www.scopus.com/inward/record.url?scp=84987962201&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-44914-2_9
DO - 10.1007/978-3-319-44914-2_9
M3 - Conference contribution
AN - SCOPUS:84987962201
SN - 9783319449135
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 105
EP - 120
BT - Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings
A2 - Khachay, Michael
A2 - Pardalos, Panos
A2 - Kochetov, Yury
A2 - Beresnev, Vladimir
A2 - Nurminski, Evgeni
PB - Springer-Verlag GmbH and Co. KG
T2 - 9th International Conference on Discrete Optimization and Operations Research, DOOR 2016
Y2 - 19 September 2016 through 23 September 2016
ER -