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.