Skip to Main content Skip to Navigation
Conference papers

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.
Keywords : complexité coupled-tasks ordonnancement
Document type :
Conference papers
Complete list of metadata
https://hal.inria.fr/inria-00099380
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:53:27 AM
Last modification on : Friday, February 4, 2022 - 3:30:02 AM

Identifiers

  • HAL Id : inria-00099380, version 1

Collections

INRIA | CNRS | LORIA | UNIV-LORRAINE | INRIA2

Citation

Benoit Sonntag, Antony Vignier. Un algorithme polynomial pour le problème ouvert du "coupled tasks". ROADEF'2000 - 3ème congrès de la société Française de Recherche Opérationnelle et d'Aide à la Décision, Jan 2000, Nantes, France. pp.57-58. ⟨inria-00099380⟩

Export

BibTeX TEI DC DCterms EndNote Datacite

Share

Metrics

Record views

48

 

Contact                    Legal Notice                    Personal Data