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

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.