Résumé
Nous présentons dans cet article un nouveau type de problème d'ordonnancement sur monoprocesseur avec tâches-couplées en présence d'un graphe de compatibilité. Ce type de problème est motivé par l'étude d'une torpille autonome sous-marine. Dans un premier temps, nous présentons et modélisons la problématique générale, puis nous étudions la complexité de ce type de problèmes en présence de contrainte de compatibilité. Des résultats de N P-complétude sont obtenus et un algorithme de complexité polynomiale est donné pour résoudre deux problèmes en particulier. Enfin après une synthèse de ces résultats, nous présentons une vision globale de la complexité de cette classe de problème.