 |
 |
|
|
| HAL : lirmm-00319561, version 1 |
| Fiche détaillée |  Récupérer au format |
|
|
| Majecstic, Marseille : (2008) |
|
|
|
|
| Étude de la complexité de problèmes d'ordonnancement avec tâches-couplées sur monoprocesseur |
|
|
| Gilles Simonin 1 |
|
|
| (08/09/2008) |
|
|
|
| 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. |
|
|
|
|
|
|
|
|
|
|
|
| 1 : | Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) |
|
|
|
CNRS : UMR5506 – Université Montpellier II - Sciences et Techniques du Languedoc |
|
|
|
|
|
|
|
|
|
| [INFO/APR : Algorithmique et Performances des Réseaux] |
|
|
|
|
| Domaine | : | Informatique/Recherche opérationnelle |
|
|
| Ordonnancement – complexité – tâches-couplées – monoprocesseur – compatibilité. |
|
|
|
| Liste des fichiers attachés à ce document : | |||||
|
|||||
|
|
|
| lirmm-00319561, version 1 | |
| http://hal-lirmm.ccsd.cnrs.fr/lirmm-00319561 | |
| oai:hal-lirmm.ccsd.cnrs.fr:lirmm-00319561 | |
| Contributeur : Gilles Simonin | |
| Soumis le : Lundi 8 Septembre 2008, 17:22:54 | |
| Dernière modification le : Jeudi 11 Septembre 2008, 16:33:24 | |
