Bounds and approximation results for scheduling coupled-tasks with compatibility constraints

Rodolphe Giroudeau 1 Jean-Claude König 1 Benoit Darties 2, 1 Gilles Simonin 3
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 Le2i - Laboratoire Electronique, Informatique et Image [UMR6303]
3 Insight Centre for Data Analytics [Dublin]
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.
Keywords : coupled-task compatibility graph complexity approximation
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01313722
Contributor : Rodolphe Giroudeau <>
Submitted on : Wednesday, June 7, 2017 - 10:35:32 AM
Last modification on : Monday, February 11, 2019 - 11:50:15 AM
Long-term archiving on : Friday, September 8, 2017 - 12:27:36 PM

Files

PMS16.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01313722, version 1
  • ARXIV : 1706.02200

Collections

UNIV-BOURGOGNE | MAORE | LIRMM | MIPS | LE2I | UNIV-MONTPELLIER | UNIV-NANTES | ICB | UNIV-HESAM

Citation

Rodolphe Giroudeau, Jean-Claude König, Benoit Darties, Gilles Simonin. Bounds and approximation results for scheduling coupled-tasks with compatibility constraints. PMS: Project Management and Scheduling, Apr 2016, Valencia, Spain. pp.94-97. ⟨lirmm-01313722⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

256

Files downloads

204

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD