Skip to Main content Skip to Navigation
Conference papers

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

Gilles Simonin 1
1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00319561
Contributor : Gilles Simonin <>
Submitted on : Monday, September 8, 2008 - 5:22:54 PM
Last modification on : Thursday, May 24, 2018 - 3:59:21 PM
Long-term archiving on: : Thursday, June 3, 2010 - 8:11:08 PM

File

majeStic2008_simonin.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00319561, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

433

Files downloads

1664