 |
HAL-LIRMM - Open Archive |  |
Conference papers
Bounds and approximation results for scheduling coupled-tasks with compatibility constraints
Abstract : This article is devoted to propose some lower and upper bounds for the coupled-tasks scheduling problem in presence of compatibility constraints according to classical complexity hypothesis ($\mathcal{P} \neq \mathcal{NP}$, $\mathcal{ETH}$). Moreover, we develop an efficient polynomial-time approximation algorithm for the specific case for which the topology describing the compatibility constraints is a quasi split-graph.
Cited literature [14 references]
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01313722
Contributor : Rodolphe Giroudeau <>
Submitted on : Wednesday, June 7, 2017 - 10:35:32 AM
Last modification on : Friday, July 17, 2020 - 2:54:11 PM
Long-term archiving on: : Friday, September 8, 2017 - 12:27:36 PM
Contributor : Rodolphe Giroudeau <>
Submitted on : Wednesday, June 7, 2017 - 10:35:32 AM
Last modification on : Friday, July 17, 2020 - 2:54:11 PM
Long-term archiving on: : Friday, September 8, 2017 - 12:27:36 PM
Files
PMS16.pdf
Files produced by the author(s)