Name
Abstract | ||
|---|---|---|
In this article, we investigate the parameterized complexity of coupled-task scheduling in the presence of compatibility constraints given by a compatibility graph. In this model, each task contains two sub-tasks delayed by an idle time. Moreover, a sub-task can be performed during the idle time of another task 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 have a completion time before a fixed due date? It is known that this problem is \(\mathsf { NP}\)-complete. We prove that it is fixed-parameter tractable (\(\mathsf {FPT}\)) parameterized by k the standard parameter if the total duration of each task is bounded by a constant, whereas the problem becomes \({\mathsf {W}}[1]\)-hard otherwise. We also show that in the former case, the problem does not admit a polynomial kernel under some standard complexity assumptions. Moreover, we obtain an \(\mathsf {FPT}\) algorithm when the problem is parameterized by the size of a vertex cover of the compatibility graph. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s10951-018-0581-1 | Journal of Scheduling |
Keywords | Field | DocType |
Coupled-task scheduling model, $$\mathsf {FPT}$$FPT algorithms, $${\mathsf {W}}[1]$$W[1]-hardness, Kernel lower bound | Discrete mathematics,Graph,Mathematical optimization,Parameterized complexity,Job shop scheduling,Scheduling (computing),Computer science,Polynomial kernel,Vertex cover,Idle time,Bounded function | Journal |
Volume | Issue | ISSN |
22.0 | 3 | 1099-1425 |
Citations | PageRank | References |
1 | 0.36 | 22 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| Rodolphe Giroudeau | 2 | 64 | 18.61 |