Un algorithme polynomial pour le problème ouvert du "coupled tasks"

Benoit Sonntag 1 Antony Vignier 2
1 ECOO - Environment for cooperation
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 MACSI - Industrial system modeling, analysis and operation
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Résumé : La résolution d'un cas particulier du problème d'ordonnancement appelé "coupled tasks" est traité dans ce papier. Une classification en terme de complexité réalisée dans [1] laisse apparaître un cas où la complexité d'un problème est encore ouvert. Il s'agit du cas où ai=a, Li=L, bi=b. Nous proposons un algorithme polynomial en O(n) pour résoudre ce problème. A ce jour il n'a jamais été mis en échec sur un grand nombre de jeux d'essais. La preuve d'optimalité de cet algorithme est établie dans quelques cas.
Type de document :
Article dans une revue
READEF'2000, 2000, pp.57-58
Liste complète des métadonnées

https://hal.inria.fr/inria-00099380
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:53:27
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00099380, version 1

Collections

Citation

Benoit Sonntag, Antony Vignier. Un algorithme polynomial pour le problème ouvert du "coupled tasks". READEF'2000, 2000, pp.57-58. 〈inria-00099380〉

Partager

Métriques

Consultations de la notice

118