Creative Commons Attribution 4.0 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: https://drops.dagstuhl.de/opus/volltexte/2022/17377/
Mallem, Maher ; Hanen, Claire ; Munier-Kordon, Alix
Parameterized Complexity of a Parallel Machine Scheduling Problem
| pdf-format: |
|
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 | |
| Seminar: | 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 14.12.2022 |
