Standard
Precedence-constrained scheduling problems parameterized by partial order width. / van Bevern, René; Bredereck, Robert; Bulteau, Laurent et al.
Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings. ed. / Michael Khachay; Panos Pardalos; Yury Kochetov; Vladimir Beresnev; Evgeni Nurminski. Springer-Verlag GmbH and Co. KG, 2016. p. 105-120 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9869 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
van Bevern, R, Bredereck, R, Bulteau, L, Komusiewicz, C, Talmon, N & Woeginger, GJ 2016,
Precedence-constrained scheduling problems parameterized by partial order width. in M Khachay, P Pardalos, Y Kochetov, V Beresnev & E Nurminski (eds),
Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9869 LNCS, Springer-Verlag GmbH and Co. KG, pp. 105-120, 9th International Conference on Discrete Optimization and Operations Research, DOOR 2016, Vladivostok, Russian Federation,
19.09.2016.
https://doi.org/10.1007/978-3-319-44914-2_9
APA
van Bevern, R., Bredereck, R., Bulteau, L., Komusiewicz, C., Talmon, N., & Woeginger, G. J. (2016).
Precedence-constrained scheduling problems parameterized by partial order width. In M. Khachay, P. Pardalos, Y. Kochetov, V. Beresnev, & E. Nurminski (Eds.),
Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings (pp. 105-120). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9869 LNCS). Springer-Verlag GmbH and Co. KG.
https://doi.org/10.1007/978-3-319-44914-2_9
Vancouver
van Bevern R, Bredereck R, Bulteau L, Komusiewicz C, Talmon N, Woeginger GJ.
Precedence-constrained scheduling problems parameterized by partial order width. In Khachay M, Pardalos P, Kochetov Y, Beresnev V, Nurminski E, editors, Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings. Springer-Verlag GmbH and Co. KG. 2016. p. 105-120. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-44914-2_9
Author
van Bevern, René ; Bredereck, Robert ; Bulteau, Laurent et al. /
Precedence-constrained scheduling problems parameterized by partial order width. Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings. editor / Michael Khachay ; Panos Pardalos ; Yury Kochetov ; Vladimir Beresnev ; Evgeni Nurminski. Springer-Verlag GmbH and Co. KG, 2016. pp. 105-120 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{2213742279e4479e923772a8d0d3b801,
title = "Precedence-constrained scheduling problems parameterized by partial order width",
abstract = "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.",
keywords = "Makespan minimization, Parallel identical machines, Parameterized complexity, Resource-constrained project scheduling, Shuffle product",
author = "{van Bevern}, Ren{\'e} and Robert Bredereck and Laurent Bulteau and Christian Komusiewicz and Nimrod Talmon and Woeginger, {Gerhard J.}",
year = "2016",
month = jan,
day = "1",
doi = "10.1007/978-3-319-44914-2_9",
language = "English",
isbn = "9783319449135",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "105--120",
editor = "Michael Khachay and Panos Pardalos and Yury Kochetov and Vladimir Beresnev and Evgeni Nurminski",
booktitle = "Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings",
address = "Germany",
note = "9th International Conference on Discrete Optimization and Operations Research, DOOR 2016 ; Conference date: 19-09-2016 Through 23-09-2016",
}
RIS
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 -
