Programme dynamique générique pour l'ordonnancement d'intervalles avec contraintes de clique

Nous présentons un théorème général d'extension de programmes dynamiques pour des problèmes d'ordonnancement de tâches définis sur des graphes d'intervalles, en y ajoutant la contrainte selon laquelle au plus $m$ tâches peuvent être actives à tout instant $t$. Nous parlerons alors de généralisation d'un problème initial $P$ vers sa variante intégrant des contraintes de cliques maximales locales. Pour un $m$ fixé, nous développons une méthode générale permettant d'adapter la résolution de $P$ à cette variante en temps polynomial.Notre approche suppose l'existence d'un programme dynamique résolvant le problème initial $P$. Ce résultat s'applique à une large famille de problèmes d'ordonnancement et a notamment permis d'établir une résolution en temps polynomial pour un problème dont la complexité était jusqu'alors ouverte.