Complexité et approximation pour un problème d'ordonnancement avec tâches couplées

Résumé : Nous étudions un problème d'ordonnancement avec des tâches-couplées en présence d'un graphe de compatibilité sur un monoprocesseur. Dans ce cadre, nous montrerons que ce problème est NP-complet. Nous développerons également un algorithme d'approximation en O(n^3) avec un ratio de (alpha+6)/6, où alpha est l'intervalle de temps entre les deux sous-tâches d'une tâche-couplée.