Parameterized complexity of a coupled-task scheduling problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Journal of Scheduling Year : 2019

Parameterized complexity of a coupled-task scheduling problem

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.
Fichier principal
Vignette du fichier
ordo-fpt.pdf (202.1 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-02133404 , version 1 (03-04-2020)

Identifiers

Cite

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

Altmetric

Share

More