Bounds and approximation results for scheduling coupled-tasks with compatibility constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2016

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

Résumé

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.
Fichier principal
Vignette du fichier
PMS16.pdf (121.53 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01313722 , version 1 (07-06-2017)

Identifiants

Citer

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⟩
205 Consultations
155 Téléchargements

Altmetric

Partager

More