Ordonnancement de Tâches-Couplées Avec Contraintes d'Incompatibilité » książka
Ordonnancement de Tâches-Couplées Avec Contraintes d'Incompatibilité
ISBN-13: 9786131554797 / Francuski / Miękka / 2018 / 164 str.
Les travaux prA(c)sentA(c)s portent sur l'A(c)tude de la complexitA(c) et de l'approximation des problA]mes d'ordonnancement en prA(c)sence de tA ches-couplA(c)es sur un mono-processeur. Ces problA]mes sont motivA(c)s par la modA(c)lisation d'un problA]me de robotique portant sur une torpille sous-marine d'exploration. La torpille a pour objectif d'exA(c)cuter des tA ches d'acquisition et de traitement. Les tA ches d'acquisition sont semblables A des tA ches-couplA(c)es, et celles de traitement A des tA ches classiques. Certain capteurs utilisA(c)s pour les acquisitions ne peuvent pas Aatre utilisA(c)s en mAame temps pour cause d'interfA(c)rences. Un graphe de compatibilitA(c) reprA(c)sente cette contrainte. Nous mettons en avant l'impact de la contrainte de compatibilitA(c), nous forAant A utiliser la thA(c)orie des graphes pour analyser nos problA]mes. Nous donnons la classification des problA]mes possibles en faisant varier les paramA]tres des tA ches-couplA(c)es. Nous donnons des preuves de complexitA(c) pour certains problA]mes se trouvant A la limite entre la polynomialitA(c) et la NP-complA(c)tude selon les valeurs des paramA]tres. L'ensemble des rA(c)sultats est dA(c)composA(c) en trois chapitres prenant chacun en compte l'introduction d'une contrainte.
Les travaux présentés portent sur létude de la complexité et de lapproximation des problèmes dordonnancement en présence de tâches-couplées sur un mono-processeur. Ces problèmes sont motivés par la modélisation dun problème de robotique portant sur une torpille sous-marine dexploration. La torpille a pour objectif dexécuter des tâches dacquisition et de traitement. Les tâches dacquisition 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 dinterférences. Un graphe de compatibilité représente cette contrainte. Nous mettons en avant limpact 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. Lensemble des résultats est décomposé en trois chapitres prenant chacun en compte lintroduction dune contrainte.
Czytaj nas na:
KrainaKsiazek.PL - Księgarnia Internetowa
