Skip to Main content Skip to Navigation
Conference papers

Complexité et approximation pour un problème d'ordonnancement avec tâches couplées

Gilles Simonin 1 Rodolphe Giroudeau 1 Jean-Claude König 1
1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Nous étudions un problème d'ordonnancement avec des tâches-couplées en présence d'un graphe de compatibilité sur un monoprocesseur. Dans ce cadre, nous montrerons que ce problème est NP-complet. Nous développerons également un algorithme d'approximation en O(n^3) avec un ratio de (alpha+6)/6, où alpha est l'intervalle de temps entre les deux sous-tâches d'une tâche-couplée.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00270792
Contributor : Gilles Simonin <>
Submitted on : Monday, April 7, 2008 - 3:17:04 PM
Last modification on : Monday, February 11, 2019 - 11:50:15 AM
Long-term archiving on: : Friday, May 21, 2010 - 1:25:24 AM

Identifiers

  • HAL Id : lirmm-00270792, version 1

Collections

Citation

Gilles Simonin, Rodolphe Giroudeau, Jean-Claude König. Complexité et approximation pour un problème d'ordonnancement avec tâches couplées. RenPar'18 : Rencontres Francophones du Parallélisme, Feb 2008, Fribourg, Suisse. ⟨lirmm-00270792⟩

Share

Metrics

Record views

239

Files downloads

609