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.
Mots-clés : Approximation Ordonnancement Tâche-couplée Compatibilité Complexité
Type de document :
Communication dans un congrès
RenPar'18 : Rencontres Francophones du Parallélisme, Feb 2008, Fribourg, Suisse. 2008, 〈http://gridgroup.tic.hefr.ch/renpar/〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00270792
Contributeur : Gilles Simonin <>
Soumis le : lundi 7 avril 2008 - 15:17:04
Dernière modification le : lundi 22 janvier 2018 - 11:54:01
Document(s) archivé(s) le : vendredi 21 mai 2010 - 01:25:24

Fichier

Fribourg_18-simonin.pdf

Identifiants

  • HAL Id : lirmm-00270792, version 1

Collections

APR | APR-LIRMM | LIRMM | MIPS | UNIV-MONTPELLIER

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. 2008, 〈http://gridgroup.tic.hefr.ch/renpar/〉. 〈lirmm-00270792〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

154

Téléchargements de fichiers

548

Contact

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