Parameterized complexity of a coupled-task scheduling problem

Stéphane Bessy (1) , Rodolphe Giroudeau (2)

1 ALGCO - Algorithmes, Graphes et Combinatoire
2 MAORE - Methods, Algorithms for Operations REsearch

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.

Mots clés: Kernel lower bound; Coupled-task scheduling model; FPT algorithms

Domaines: Recherche opérationnelle [math.OC]

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⟩