Ordonnancement de T ches-Coupl es Avec Contraintes d'Incompatibilit

Les travaux prsents portent sur l'tude de la complexit et de l'approximation des problmes d'ordonnancement en prsence de tches-couples sur un mono-processeur. Ces problmes sont motivs par la modlisation d'un problme de robotique portant sur une torpille sous-marine d'exploration. La torpille a pour objectif d'excuter des tches d'acquisition et de traitement. Les tches d'acquisition sont semblables des tches-couples, et celles de traitement des tches classiques. Certain capteurs utiliss pour les acquisitions ne peuvent pas tre utiliss en mme temps pour cause d'interfrences. Un graphe de compatibilit reprsente cette contrainte. Nous mettons en avant l'impact de la contrainte de compatibilit, nous forant utiliser la thorie des graphes pour analyser nos problmes. Nous donnons la classification des problmes possibles en faisant varier les paramtres des tches-couples. Nous donnons des preuves de complexit pour certains problmes se trouvant la limite entre la polynomialit et la NP-compltude selon les valeurs des paramtres. L'ensemble des rsultats est dcompos en trois chapitres prenant chacun en compte l'introduction d'une contrainte.