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 proceedingConference contributionResearchpeer-review

8 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationDiscrete Optimization and Operations Research - 9th International Conference, DOOR 2016, Proceedings
EditorsMichael Khachay, Panos Pardalos, Yury Kochetov, Vladimir Beresnev, Evgeni Nurminski
PublisherSpringer-Verlag GmbH and Co. KG
Pages105-120
Number of pages16
ISBN (Print)9783319449135
DOIs
Publication statusPublished - 1 Jan 2016
Event9th International Conference on Discrete Optimization and Operations Research, DOOR 2016 - Vladivostok, Russian Federation
Duration: 19 Sep 201623 Sep 2016

Publication series

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

Conference

Conference9th International Conference on Discrete Optimization and Operations Research, DOOR 2016
CountryRussian Federation
CityVladivostok
Period19.09.201623.09.2016

Keywords

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

State classification of scientific and technological information

  • 27 MATHEMATICS

Fingerprint Dive into the research topics of 'Precedence-constrained scheduling problems parameterized by partial order width'. Together they form a unique fingerprint.

Cite this