Étude de la complexité de problèmes d'ordonnancement avec tâches-couplées sur monoprocesseur

Gilles Simonin 1
1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : Nous présentons dans cet article un nouveau type de problème d'ordonnancement sur monoprocesseur avec tâches-couplées en présence d'un graphe de compatibilité. Ce type de problème est motivé par l'étude d'une torpille autonome sous-marine. Dans un premier temps, nous présentons et modélisons la problématique générale, puis nous étudions la complexité de ce type de problèmes en présence de contrainte de compatibilité. Des résultats de N P-complétude sont obtenus et un algorithme de complexité polynomiale est donné pour résoudre deux problèmes en particulier. Enfin après une synthèse de ces résultats, nous présentons une vision globale de la complexité de cette classe de problème.
Type de document :
Communication dans un congrès
Majecstic'2008, Oct 2008, Marseille, France. 2008, 〈http://www.lsis.org/~addl/fr/manifs/majecstic08/〉
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00319561
Contributeur : Gilles Simonin <>
Soumis le : lundi 8 septembre 2008 - 17:22:54
Dernière modification le : lundi 22 janvier 2018 - 11:54:01
Document(s) archivé(s) le : jeudi 3 juin 2010 - 20:11:08

Fichier

majeStic2008_simonin.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00319561, version 1

Collections

Citation

Gilles Simonin. Étude de la complexité de problèmes d'ordonnancement avec tâches-couplées sur monoprocesseur. Majecstic'2008, Oct 2008, Marseille, France. 2008, 〈http://www.lsis.org/~addl/fr/manifs/majecstic08/〉. 〈lirmm-00319561〉

Partager

Métriques

Consultations de la notice

322

Téléchargements de fichiers

1023