Les travaux presentes portent sur l'etude de la complexite et de l'approximation des problemes d'ordonnancement en presence de taches-couplees sur un mono-processeur. Ces problemes sont motives par la modelisation d'un probleme de robotique portant sur une torpille sous-marine d'exploration. La torpille a pour objectif d'executer des taches d'acquisition et de traitement. Les taches d'acquisition sont semblables a des taches-couplees, et celles de traitement a des taches classiques. Certain capteurs utilises pour les acquisitions ne peuvent pas etre utilises en meme temps pour cause d'interferences. Un graphe de compatibilite represente cette contrainte. Nous mettons en avant l'impact de la contrainte de compatibilite, nous forcant a utiliser la theorie des graphes pour analyser nos problemes. Nous donnons la classification des problemes possibles en faisant varier les parametres des taches-couplees. Nous donnons des preuves de complexite pour certains problemes se trouvant a la limite entre la polynomialite et la NP-completude selon les valeurs des parametres. L'ensemble des resultats est decompose en trois chapitres prenant chacun en compte l'introduction d'une contrainte."