Un algorithme polynomial pour le problème ouvert du "coupled tasks" - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2000

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

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.

Domaines

Autre [cs.OH]
Fichier non déposé

Dates et versions

inria-00099380 , version 1 (26-09-2006)

Identifiants

  • HAL Id : inria-00099380 , version 1

Citer

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⟩
51 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More