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.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00099380
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:53:27 AM
Last modification on : Thursday, January 11, 2018 - 6:19:48 AM

Identifiers

  • 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⟩

Share

Metrics

Record views

130