Skip to Main content Skip to Navigation
Journal articles

Parameterized complexity of a coupled-task scheduling problem

Stéphane Bessy 1 Rodolphe Giroudeau 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this article, we investigate the parameterized complexity of coupled-task scheduling in the presence of compatibility constraint given by a compatibility graph. In this model, each task contains two sub-tasks delayed by an idle time, and a sub- task of a task can be performed during the idle time of another one if, and only if, the two tasks are compatible. We consider a parameterized version of the scheduling problem: is there a schedule in which at least k coupled-tasks possess a completion time before a fixed due date? It is known that this problem is NP-complete ([23] and [24]), and we prove that it is fixed-parameter tractable (FPT ) if the total duration time of each task is bounded by a constant, whereas the problem becomes W[1]-hard if it is not the case. We also show that in the former case the problem does not admit a polynomial kernel under some standard complexity assumptions. Moreover, we obtain also an FPT algorithm when the problem is parameterized by the size of a vertex cover of the compatibility graph.
Document type :
Journal articles
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02133404
Contributor : Rodolphe Giroudeau <>
Submitted on : Friday, April 3, 2020 - 9:37:42 AM
Last modification on : Friday, April 3, 2020 - 9:39:17 AM

File

ordo-fpt.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Stéphane Bessy, Rodolphe Giroudeau. Parameterized complexity of a coupled-task scheduling problem. Journal of Scheduling, Springer Verlag, 2019, 22 (3), pp.305-313. ⟨10.1007/s10951-018-0581-1⟩. ⟨lirmm-02133404⟩

Share

Metrics

Record views

151

Files downloads

55