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.

N1 - Conference code: 9

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

T2 - 9th International Conference on Discrete Optimization and Operations Research,

Y2 - 19 September 2016 through 23 September 2016

ER -