 |
 |
|
|
| HAL : lirmm-00270792, version 1 |
| Fiche détaillée |  Récupérer au format |
|
|
| RenPar'18 : Rencontres Francophones du Parallélisme, Fribourg, Suisse : (2008) |
|
|
|
|
| Complexité et approximation pour un problème d'ordonnancement avec tâches couplées |
|
|
| Gilles Simonin 1Rodolphe Giroudeau 1 |
|
|
| (07/04/2008) |
|
|
|
| Nous étudions un problème d'ordonnancement avec des tâches-couplées en présence d'un graphe de compatibilité sur un monoprocesseur. Dans ce cadre, nous montrerons que ce problème est NP-complet. Nous développerons également un algorithme d'approximation en O(n^3) avec un ratio de (alpha+6)/6, où alpha est l'intervalle de temps entre les deux sous-tâches d'une tâche-couplée. |
|
|
|
|
|
|
|
|
|
|
|
| 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 – Tâche-couplée – Compatibilité – Complexité – Approximation |
|
|
|
| Liste des fichiers attachés à ce document : | |||||
|
|||||
|
|
|
| lirmm-00270792, version 1 | |
| http://hal-lirmm.ccsd.cnrs.fr/lirmm-00270792 | |
| oai:hal-lirmm.ccsd.cnrs.fr:lirmm-00270792 | |
| Contributeur : Gilles Simonin | |
| Soumis le : Lundi 7 Avril 2008, 15:17:04 | |
| Dernière modification le : Dimanche 11 Mai 2008, 19:07:58 | |
