Complexité et approximation pour un problème d'ordonnancement avec tâches couplées - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2008

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

Gilles Simonin
Rodolphe Giroudeau
Jean-Claude König

Abstract

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.
Fichier principal
Vignette du fichier
Fribourg_18-simonin.pdf (106.12 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-00270792 , version 1 (07-04-2008)

Identifiers

  • HAL Id : lirmm-00270792 , version 1

Cite

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⟩
122 View
489 Download

Share

Gmail Facebook X LinkedIn More