Precedence-constrained scheduling problems parameterized by partial order width

René van Bevern; Robert Bredereck; Laurent Bulteau; Christian Komusiewicz; Nimrod Talmon; Gerhard J. Woeginger

doi:10.1007/978-3-319-44914-2_9

Precedence-constrained scheduling problems parameterized by partial order width

René van Bevern, Robert Bredereck, Laurent Bulteau, Christian Komusiewicz, Nimrod Talmon, Gerhard J. Woeginger

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

28 Citations (Scopus)

Abstract

Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1–2):533–562), we show that P2|prec, p_j∈{1, 2}|C_max, 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.

Original language	English
Title of host publication	Discrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings
Editors	Michael Khachay, Panos Pardalos, Yury Kochetov, Vladimir Beresnev, Evgeni Nurminski
Publisher	Springer
Pages	105-120
Number of pages	16
ISBN (Print)	9783319449135
DOIs	https://doi.org/10.1007/978-3-319-44914-2_9
Publication status	Published - 2016
Event	9th International Conference on Discrete Optimization and Operations Research, DOOR 2016 - Vladivostok, Russian Federation Duration: 19 Sept 2016 → 23 Sept 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9869 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Discrete Optimization and Operations Research, DOOR 2016
Country/Territory	Russian Federation
City	Vladivostok
Period	19/09/16 → 23/09/16

Bibliographical note

Publisher Copyright:
© Springer International Publishing Switzerland 2016.

Funding

R. van Bevern—Supported by project 16-31-60007 mol_a_dk of the Russian Foundation for Basic Research.

Keywords

Makespan minimization
Parallel identical machines
Parameterized complexity
Resource-constrained project scheduling
Shuffle product

Access to Document

10.1007/978-3-319-44914-2_9

Cite this

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. https://doi.org/10.1007/978-3-319-44914-2_9

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, 2016. pp. 105-120 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ae2e150e6f6e490787204612946de508,

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.}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 9th International Conference on Discrete Optimization and Operations Research, DOOR 2016 ; Conference date: 19-09-2016 Through 23-09-2016",

year = "2016",

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",

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",

}

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, pp. 105-120, 9th International Conference on Discrete Optimization and Operations Research, DOOR 2016, Vladivostok, Russian Federation, 19/09/16. https://doi.org/10.1007/978-3-319-44914-2_9

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, 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 › Academic › peer-review

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 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

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, DOOR 2016

Y2 - 19 September 2016 through 23 September 2016

ER -

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. 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

Precedence-constrained scheduling problems parameterized by partial order width

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this