License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.21
URN: urn:nbn:de:0030-drops-173774
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17377/
Go to the corresponding LIPIcs Volume Portal

Mallem, Maher ; Hanen, Claire ; Munier-Kordon, Alix

Parameterized Complexity of a Parallel Machine Scheduling Problem

pdf-format:
LIPIcs-IPEC-2022-21.pdf (5 MB)

Abstract

In this paper we consider the parameterized complexity of two versions of a parallel machine scheduling problem with precedence delays, unit processing times and time windows. In the first version - with exact delays - we assume that the delay between two jobs must be exactly respected, whereas in the second version - with minimum delays - the delay between two jobs is a lower bound on the time between them. Two parameters are considered for this analysis: the pathwidth of the interval graph induced by the time windows and the maximum precedence delay value. We prove that our problems are para-NP-complete with respect to any of the two parameters and fixed-parameter tractable parameterized by the pair of parameters.

BibTeX - Entry

@InProceedings{mallem_et_al:LIPIcs.IPEC.2022.21,
  author =	{Mallem, Maher and Hanen, Claire and Munier-Kordon, Alix},
  title =	{{Parameterized Complexity of a Parallel Machine Scheduling Problem}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{21:1--21:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17377},
  URN =		{urn:nbn:de:0030-drops-173774},
  doi =		{10.4230/LIPIcs.IPEC.2022.21},
  annote =	{Keywords: parameterized complexity, scheduling, precedence delays, pathwidth, chains, parallel processors}
}

Keywords: parameterized complexity, scheduling, precedence delays, pathwidth, chains, parallel processors
Collection: 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI