DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2022.21

Parameterized Complexity of a Parallel Machine Scheduling Problem

Authors: Maher Mallem, Claire Hanen, and Alix Munier-Kordon

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

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.

Cite as

Maher Mallem, Claire Hanen, and Alix Munier-Kordon. Parameterized Complexity of a Parallel Machine Scheduling Problem. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.IPEC.2022.21},
  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}
}

Search Results

Documents authored by Mallem, Maher

Parameterized Complexity of a Parallel Machine Scheduling Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message