Étude de la complexité de problèmes d'ordonnancement avec tâches-couplées sur monoprocesseur - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2008

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

Gilles Simonin

Abstract

We present in this article a new type of scheduling problem on monoprocesssor with coupled-tasks and compatibility graph. This problem is motivated by the study of a submarine autonomous torpedo. In a first time, we present the general problem, then we study the com- plexity of differents problems with compatibility constraint. NP-complete results are proven and a polynomial algorithm is given in order to solve particular problems. Finally, the results and a complexity overall view of this problem class are summarized.
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.
Fichier principal
Vignette du fichier
majeStic2008_simonin.pdf (80.11 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-00319561 , version 1 (08-09-2008)

Identifiers

  • HAL Id : lirmm-00319561 , version 1

Cite

Gilles Simonin. Étude de la complexité de problèmes d'ordonnancement avec tâches-couplées sur monoprocesseur. Majecstic'2008, Oct 2008, Marseille, France. ⟨lirmm-00319561⟩
268 View
1522 Download

Share

Gmail Facebook X LinkedIn More