Gilles Simonin

Ordonnancement de tâches-couplées avec contraintes d'incompatibilité

Impact de la contrainte d'incompatibilité sur la complexité et l'approximation des problèmes d'ordonnancement en présence de tâches-couplées

• Broschiertes Buch

Produktbeschreibung

Les travaux présentés portent sur l'étude de la complexité et de l'approximation des problèmes d'ordonnancement en présence de tâches-couplées sur un mono-processeur. Ces problèmes sont motivés par la modélisation d'un problème de robotique portant sur une torpille sous-marine d'exploration. La torpille a pour objectif d'exécuter des tâches d'acquisition et de traitement. Les tâches d'acquisition sont semblables à des tâches-couplées, et celles de traitement à des tâches classiques. Certain capteurs utilisés pour les acquisitions ne peuvent pas être utilisés en même temps pour cause d'interférences. Un graphe de compatibilité représente cette contrainte. Nous mettons en avant l'impact de la contrainte de compatibilité, nous forçant à utiliser la théorie des graphes pour analyser nos problèmes. Nous donnons la classification des problèmes possibles en faisant varier les paramètres des tâches-couplées. Nous donnons des preuves de complexité pour certains problèmes se trouvant à la limite entre la polynomialité et la NP-complétude selon les valeurs des paramètres. L'ensemble des résultats est décomposé en trois chapitres prenant chacun en compte l'introduction d'une contrainte.

Produktdetails

• Verlag: Éditions universitaires européennes
• Seitenzahl: 164
• Erscheinungstermin: 13. Januar 2011
• Französisch
• Abmessung: 220mm x 150mm x 10mm
• Gewicht: 262g
• ISBN-13: 9786131554797
• ISBN-10: 613155479X
• Artikelnr.: 32755768

Autorenporträt

Gilles Simonin, docteur en informatique, études de mathématiqueset informatiques à l'université Montpellier II (LIRMM), ATER àl'université Montpellier III, recherche dans l'équipe APR auLIRMM en algorithmique, complexité, approximation et ordonnancement.