<figure><img src="image_1.png" /></figure>

HAL
open science

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

Arthur Mazeyrat, Ammar Oulamara, Tifenn Rault, Ameur Soukhal

<figure><img src="image_2.png" /></figure>

## To cite this version:

Arthur Mazeyrat, Ammar Oulamara, Tifenn Rault, Ameur Soukhal. Programme dynamique générique pour l'ordonnancement d'intervalles avec contrainte de clique. ROADEF 2026, LIFAT, Feb 2026, Tours, France. hal-05396585v1

HAL Id: hal-05396585

https://hal.science/hal-05396585v1

Submitted on 3 Dec 2025 (v1), last revised 19 Dec 2025 (v2)

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Programme dynamique générique pour l'ordonnancement
d'intervalles avec contrainte de clique

Arthur Mazeyrat¹, Ammar Oulamara², Tifenn Rault¹, Ameur Soukhal¹

¹ Université de Tours, LIFAT EA 6300, 64 avenue Jean Portalis, 37200 Tours, France
[arthur.mazeyrat@etu.univ-tours.fr](mailto:arthur.mazeyrat@etu.univ-tours.fr)
[tifenn.rault,ameur.soukhal]@univ-tours.fr

² Université de Lorraine, LORIA - UMR 7503, Campus Scientifique - BP 239, 54506 Vandoeuvre-les-Nancy, France
[ameur.oulamara@loria.fr](mailto:ameur.oulamara@loria.fr)

**Mots-clés** : recherche opérationnelle, ordonnnancement, graphes d'intervalles, cliques, complexité, programmation dynamique

# 1 Introduction

Les problèmes d'optimisation combinatoires définis sur des graphes d'intervalles apparaissent dans de nombreux domaines tels que la planification de machines, les réseaux de communication, le transport, la gestion des effectifs ou les systèmes énergétiques. Dans ces problèmes, chaque tâche ou activité $T_j$ est associée à un intervalle $[r_j, d_j]$ défini par sa date de début au plus tôt et sa date de fin impérative, ainsi qu'à une durée de traitement $p_j \le (d_j - r_j)$, et éventuellement à un poids ou profit. Les problèmes classiques incluent la sélection de tâches correspondant à des intervalles compatibles (*interval scheduling*) [3], [4], la sélection pondérée de tâches (*weighted interval selection*), la planification de tâches à intervalles fixes (*fixed-interval scheduling*) [1], la gestion de projet avec contraintes de ressources (*RCPSP*) ou encore la planification préemptive tel que le problème de recharge de véhicules électriques (*EVCSP*) [5].

Pour un grand nombre de ces problèmes, des algorithmes de programmation dynamique (DP) existent dans le cas de capacité illimitée, où aucune limite n'est imposée sur le nombre de tâches traitées simultanément. Ces algorithmes exploitent la structure des intervalles : les tâches sont d'abord triées, en général par date de fin croissante, puis des sous-problèmes sont définis sur des sous-ensembles d'intervalles, souvent structurés autour d'ensembles de cliques maximales du graphe d'intervalles. Cette décomposition permet d'obtenir des algorithmes polynomiaux, mais le cas d'une capacité limitée est en général nettement plus difficile à résoudre.

Cependant, dans la plupart des problèmes réels, les ressources sont limitées et cette limitation peut varier dans le temps. À chaque instant, un nombre maximal de tâches simultanées est autorisé, ce que nous formalisons par une fonction de capacité temporelle $\omega(t)$, fixant pour chaque instant $t$ le nombre maximal de tâches pouvant être exécutées en parallèle. Ce cadre peut-être modélisé par une coloration de graphes d'intervalles sous contrainte de capacité, où chaque tâche est associée à une demande de ressource et où, à chaque instant, la capacité totale disponible limite la somme des demandes des tâches qui se chevauchent. On parle alors aussi de multi-coloration de graphes d'intervalles.

Dans cette étude, nous proposons une approche de résolution originale fondée sur un programme dynamique qui exploite la structure des solutions réalisables optimales. Cette structure représente, à chaque instant $t$, l'affectation des tâches aux ressources pour une capacité maximale $\omega(t)$. Notre méthode repose sur l'introduction de vecteurs de forme et d'une fonction de score généralisée associée, qui encodent à la fois la structure d'une solution optimale et les contraintes de chevauchement. Pour tout problème dont la solution optimale peut être obtenue
par un programme dynamique en considérant un nombre fixe de sous-intervalles, nous établissons l'existence de vecteurs de forme adaptés, garantissant à la fois l'optimalité et la faisabilité de la solution sous une contrainte de clique de taille variable $\omega(t)$. Cette construction conduit à un algorithme de complexité :

$$O(n^{2m\ell} \cdot \text{poly}(n))$$

où $\ell$ désigne le nombre maximal de sous-ensembles d'intervalles considérés à chaque étape, $\text{poly}(n)$ la complexité du DP initial, $m$ le maximum de la fonction $\omega(t)$ et $n$ le nombre d'intervalles. Lorsque $m$ est fixé, l'algorithme est donc polynomial.

Ce cadre théorique s'applique à plusieurs problèmes d'ordonnancement de tâches à intervalles admettant un algorithme de programmation dynamique (DP-initial). On peut notamment citer : la planification du rechargement de véhicules électriques (EVCSP), où un seul véhicule peut être chargé à un instant donné et où le nombre de places de stationnement est limité à $m$ [5]; la planification à intervalles fixes avec contraintes multi-ressources sur une machine [1]; la gestion de la production industrielle soumise à des contraintes d'énergie ou de maintenance; ainsi que la planification d'affectations d'agents aux ressources ou aux tâches, où la capacité totale disponible à l'instant $t$, correspondant au cumul des disponibilités des agents, est modélisée par la fonction $\omega(t)$.

## 2 Vecteurs de forme

Pour décrire précisément la structure des solutions réalisables exploitée par notre programme dynamique, nous introduisons la notion de vecteur de forme, qui représente la configuration temporelle d'un sous-ensemble d'intervalles.

Nous notons $I$ l'ensemble des intervalles d'une instance d'un problème $P$. Notons $O$ un sous-ensemble d'intervalles, tel que $O \subseteq I$. Une contrainte de clique maximale impose que, pour qu'un sous-ensemble $O$ constitue une solution réalisable, pas plus de $m$ intervalles puissent se chevaucher à n'importe quel instant. Pour un sous-ensemble $O$ réalisable, la fonction $h_O(t)$ donne ainsi la taille de la clique au temps $t$ :

$$h_O : \mathbb{R} \to \mathbb{N}, \quad t \mapsto h_O(t) \quad \text{avec} \quad h_O(t) = |\{j \in O \mid t \in I_j\}|$$

L'ensemble de toutes les fonctions $h_O$ possibles croît exponentiellement avec $n = |I|$ (i.e. $2^n$ combinaisons), ce qui rend une approche basée directement sur $h_O$ intractable.

Pour réduire cette complexité tout en conservant l'information pertinente pour l'optimalité, nous introduisons le vecteur de forme. Il s'agit d'une représentation compacte de $h_O$, suffisante pour construire la solution optimale via un programme dynamique.

Formellement, un vecteur de forme $t \in \mathbb{R}^{2m}$ associé à un ensemble d'intervalles $O$ encode, pour chaque niveau $i = 1, \dots, m$, la première et la dernière fois où ce niveau est atteint dans $h_O$. Autrement dit, $t$ contient les instants

$$t_i^{\text{first}} = \min\{t \mid h_O(t) \ge i\}, \quad t_{2m-i+1} = t_i^{\text{last}} = \max\{t \mid h_O(t) \ge i\}.$$

La Figure 3 représente le vecteur de forme $t$ ainsi que ses coordonnées. Cette représentation saisie l'information minimale nécessaire sur l'évolution des cliques dans le temps, et sert de base au programme dynamique.

En exploitant les propriétés structurelles des vecteurs de forme ainsi que certains outils combinatoires appropriés, on peut montrer que, pour toute instance $I$, un vecteur de forme $t$ n'a besoin de prendre des valeurs que dans $\mathbb{R}^{2m}$, où $\mathbb{R}$ représente l'ensemble des dates de début des intervalles.

Étant donné que $|\mathbb{R}| \le n$, le nombre total de combinaisons possibles pour un vecteur de forme est borné par $\frac{n^{2m}}{(2m)!}$.

Ainsi, pour un $m$ fixé, l'espace des vecteurs de forme est polynomial en $n$, ce qui rend tractable la construction du programme dynamique basé sur ces vecteurs.
<figure><img src="image_4.png" /><figcaption>FIG. 1 – Exemple d'un sous-ensemble O</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>FIG. 2 – Fonction h pour le sous-ensemble O</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>FIG. 3 – Vecteur de forme t pour le sous-ensemble O</figcaption></figure>

### 3 Algèbre des vecteurs de forme dans le DP

Soit $t^O \in \mathbb{R}^{2m}$ le vecteur de forme associé au sous-ensemble $O \subseteq I$. Le vecteur $t^O$ permet de vérifier si la contrainte de clique est respectée à chaque instant. Dans le cadre d'un programme dynamique (DP) général, il est nécessaire de combiner plusieurs solutions partielles. Pour garantir la faisabilité après combinaison, il faut s'assurer que le vecteur de forme résultant corresponde à une combinaison appropriée des vecteurs de forme des sous-solutions.

Formellement, soit $O_1, O_2 \subseteq I$ deux sous-ensembles réalisables avec vecteurs de forme $t^{O_1}$ et $t^{O_2}$. Nous définissons un opérateur de combinaison

$$ \oplus : \mathbb{R}^{2m} \times \mathbb{R}^{2m} \rightarrow \mathbb{R}^{2m}, \quad t^{O_1} \oplus t^{O_2} = t^{O_1 \cup O_2}, $$

tel que le vecteur de forme résultant encode correctement la taille maximale des cliques à chaque instant.

Deux cas se présentent :

1. **Composition connue** : On connaît les sous-ensembles $O_1$ et $O_2$ qui génèrent $t^{O_1}$ et $t^{O_2}$ (profil rouge de la Figure 4). La combinaison des vecteurs de forme peut alors être effectuée directement à partir des ensembles sous-jacents.

2. **Composition inconnue** : On ne dispose que des vecteurs de forme $t^1$ et $t^2$ sans connaître les ensembles sous-jacents (profil rouge de la Figure 5). Dans ce cas, il faut définir un opérateur de combinaison $\oplus$ qui, à partir de deux vecteurs de forme quelconques, fournit un vecteur de forme conservant la faisabilité et l'optimalité de n'importe quel sous-ensembles $O_1$ et $O_2$. Cet opérateur doit être compatible avec le DP, garantissant que l'optimisation locale pour $t$ ne compromet pas l'optimalité globale.

La preuve de l'existence d'un tel opérateur est essentielle, car elle permet d'étendre les résultats à des combinaisons composées de $\ell$ vecteurs de forme et à des fonctions de cliques variables $\omega(t)$.
<figure><img src="image_7.png" /><figcaption>FIG. 4 – Ajout d'un intervalle $J_k$ au sous-ensemble $O$</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>FIG. 5 – Ajout d'un intervalle $J_k$ à $t^O$</figcaption></figure>

Pour illustrer la complexité de ce problème, considérons l'ajout d'un intervalle $J_k$ à un sous-ensemble $O$. La Figure 4 montre l'ajout de $J_k$ dans le cas d'une "composition connue", tandis que la Figure 5 illustre l'ajout dans le cas d'une "composition inconnue". L'ensemble optimal $O \cup \{J_k\}$ dépend non seulement de la structure de $O$, mais aussi du vecteur de forme $t^O$ utilisé par le DP pour représenter cette solution. Il est possible que le vecteur de forme courant sur-estime certains profils, ce qui pourrait bloquer l'insertion future d'intervalle. Le théorème fondamental que nous démontrons assure qu'il existe toujours un vecteur de forme résultant permettant de retrouver la solution optimale, même lorsque la composition exacte de $O$ n'est pas connue.

Ainsi, en énumérant tous les vecteurs de forme possibles à chaque étape du DP, nous garantissons que la solution optimale courante est toujours représentée. Le programme dynamique peut alors construire la solution optimale globale par combinaison de solutions optimales locales, en manipulant uniquement leurs vecteurs de forme.

# 4 Fondements et théorème des DPs à cliques variables

Pour formaliser notre résultat, nous introduisons certaines conditions sur le DP initial et les vecteurs de forme, qui garantissent que la combinaison de sous-ensembles à chaque étape conserve l'optimalité sous la contrainte de clique variable $\omega(t)$.

Nous introduisons tout d'abord la notation suivante. Pour un intervalle $k$ et un instant $a$, notons

$$S_k(a) = \{I_j \in I \mid r_j \ge a, d_j \le d_k\}$$

l'ensemble des intervalles de $I$ commençant après $a$ et finissant avant $d_k$. Par définition, le fait que le DP du problème initial $P$ combine des solutions à l'étape $k$ pour déterminer la solution courante signifie que la solution optimale de $P$ sur $S_k(a)$ peut être construite à partir d'une famille de sous-ensembles $S_{k_i}(a_i)$ avec $a_i \ge a$ et $k_i \le k$.

Nous définissons ensuite deux opérateurs de combinaison de vecteurs de forme :

* $\oplus_E$ : somme des vecteurs de forme définis par des ensembles d'intervalle, de sorte que

$$t^{O_1} \oplus_E t^{O_2} = t^{O_1 \cup O_2},$$

représentant la combinaison exacte des ensembles (Figure 4).
• $\oplus_S$ : somme maximale des vecteurs de forme, qui fournit le plus grand vecteur de forme pouvant résulter de la combinaison de deux vecteurs de forme (Figure 5).

## 4.1 Prérequis pour l'extension du DP-initial

L'extension du DP-initial sous contraintes de cliques variables doit vérifier les conditions suivantes :

• Il existe une fonction $C(O_1, O_2, \dots, O_\ell)$ qui détermine un score pour une combinaison de sous-ensembles d'intervalleles,

• Il existe un entier $\ell$ tel que tout état $(k, a)$ du DP-initial soit issu d'une combinaison d'au plus $\ell$ sous-intervalleles

$$ (k_1, a_1), \dots, (k_\ell, a_\ell), $$

tel que $\forall i \in [1, \ell]$, $\forall O_i \subseteq S_{k_i}(a_i)$, on a :

$$ \bigoplus_{i=1}^{\ell} s t_i = \bigoplus_{i=1}^{\ell} E t_i $$

avec $t_i = t^{O_i}$, $k_i \le k$ et $a_i \ge a$.

La première condition est naturelle pour la majorité des DP, qu'il s'agisse de la somme des poids ou d'autres scores. La deuxième condition garantit que la combinaison de sous-intervalleles ne crée pas de conflits inattendus dans les vecteurs de forme. Elle est généralement satisfaite dans les DP classiques, où les intervalles combinés ne se chevauchent pas ou ne partagent aucun élément commun.

## 4.2 Théorème sur les DP avec contraintes de cliques variables

Sous les conditions précédentes, nous pouvons énoncer le théorème suivant :

**Théorème.** Soit P un problème d'ordonnancement d'intervalleles admettant un programme dynamique combinant au plus $\ell$ sous-ensembles d'intervalleles par étape et s'exécutant en temps poly(n) sur une instance de taille n. Alors, pour tout entier fixé $m \ge 1$, il existe un algorithme de programmation dynamique résolvant $P_{\omega(t)}$ en temps

$$ O(n^{\ell(2m)} \cdot \text{poly}(n)), $$

et est donc polynomial en n pour m fixé.

Ce théorème établit que *tout problème* admettant un DP basé sur la combinaison locale de $\ell$ sous-intervalleles reste efficacement solvable même lorsque l'on impose une contrainte de clique variable $\omega(t)$, à condition que le maximum m de cette fonction soit fixé.

Intuitivement, le résultat repose sur le fait que les vecteurs de forme représentent de manière compacte la structure des solutions partielles et permettent de contrôler la clique maximale à chaque instant. L'opérateur $\oplus_S$ garantit que la combinaison des vecteurs de forme préserve l'optimalité, même lorsque la composition exacte des intervalles sous-jacents n'est pas connue.

Enfin, ce théorème n'est pas seulement d'existence : il fournit un schéma constructif pour générer l'algorithme correspondant, en énumérant toutes les formes possibles et en combinant systématiquement les solutions partielles pour reconstruire la solution optimale finale.

# 5 Applications du théorème

Le théorème présenté a des implications directes pour un large ensemble de problèmes pratiques dont les solutions peuvent être décomposées en un nombre limité de sous-ensembles d'intervalleles. En particulier, en se basant sur le DP de Baptiste [2] développé pour résoudre le problème d'ordonnancement $1|pmtn, r_j| \sum U$, on peut affirmer l'existence d'un algorithme
polynomial pour ce problème avec contrainte de clique maximale de taille *m*. Le problème EVCSP avec contrainte de stationnement limité à *m* et mono-charge, dont la complexité était jusqu'alors inconnue [5], est donc polynomial pour un nombre de places de stationnement *m* fixé, répondant ainsi à la question ouverte (en $O(n^{4+6m})$). Nous avons par ailleurs montré que le cas *m* non fixé est NP-difficile.

Concernant le problème *Resource-Constrained Fixed Interval Scheduling*, le cadre proposé permet de gérer des tâches consommant différentes unités de ressources, avec des capacités disponibles variant dans le temps. Il s'étend naturellement aux configurations multi-ressources, garantissant que la contrainte de clique variable est respectée tout en préservant l'optimalité de la solution globale.

Pour le problème d'ordonnancement des tâches comportant des périodes d'indisponibilité des machines dues à la maintenance, ces contraintes peuvent être représentées comme une contrainte de clique variable sur le nombre de machines disponibles. Le cadre proposé fournit alors un outil systématique pour gérer ces contraintes tout en garantissant la préservation de l'optimalité de la solution malgré la variation temporelle des ressources.

Enfin, ce résultat offre également un intérêt théorique : pour un problème *P* soumis à une contrainte de clique, déterminer la complexité d'une extension $P \cup C$, où *C* représente des contraintes additionnelles quelconques, se réduit à l'analyse de la complexité de $P \cup C$ sans la contrainte de clique. En effet, si le problème $P \cup C$ est polynomial sans contrainte de clique, le théorème garantit que sa version avec contrainte de clique variable demeure polynomial pour tout *m* fixé.

# 6 Conclusion et perspectives

Ce travail fournit un cadre unifié permettant d'intégrer des contraintes de cliques variables dans les DP pour une classe de problèmes sur graphe d’intervalles, tout en garantissant une complexité polynomiale pour un *m* fixé.

Ce cadre constitue un outil algorithmique général pour résoudre des problèmes pratiques et complexes sous contraintes de clique variable, et ouvre la voie à de nouvelles extensions paramétrées applicables à d'autres classes de graphes.

De plus, il est probable que l'énumération exhaustive des vecteurs de forme ne soit pas nécessaire pour une large classe de problèmes. Il serait alors pertinent de déterminer une caractérisation précise, permettant la conception d'algorithmes FPT ou polynomiaux, ainsi que le développement d'une méthode systématique pour leur construction.

# References

[1] E. Angelelli, C. Archetti, and M. Vindigni. The clustered orienteering problem. *European Journal of Operational Research*, 238(2):404–414, 2014.

[2] Philippe Baptiste. An $o(n^4)$ algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. *Oper. Res. Lett.*, 24(4):175–180, May 1999.

[3] Antoon W.J. Kolen, Jan Karel Lenstra, Christos H. Papadimitriou, and Frits C.R. Spieksma. Interval scheduling: A survey. *Naval Research Logistics (NRL)*, 54(5):530–543, 2007.

[4] Mikhail Y Kovalyov, Chi To Ng, and TC Edwin Cheng. Fixed interval scheduling: Models, applications, computational complexity and algorithms. *European journal of operational research*, 178(2):331–342, 2007.

[5] I. Zaidi, A. Oulamara, L. Idoumghar, and M. Basset. Maximizing the number of satisfied charging demands of electric vehicles on identical chargers. *Omega*, 127:103106, 2024.