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.