# Ordonnancement avec acceptation sous contraintes énergétiques glissantes

Imane Boukerrouis¹, H. Murat Afsar¹, Alice Yalaoui¹

Université de technologie de Troyes

{imane.boukerrouis, murat.afsar, alicelyalaoui}@utt.fr

**Mots-clés** : ordonnancement, acceptation de tâches, disponibilité énergétique, fenêtres temporelles glissantes.

## 1 Introduction

La croissance de la demande énergétique, particulièrement dans les secteurs industriels à forte intensité, accentue les enjeux économiques et environnementaux liés à la production. Dans ce contexte, l'intégration explicite de contraintes énergétiques dans la planification et l'ordonnancement de la production constitue un levier essentiel pour améliorer l'efficacité énergétique tout en maintenant la performance opérationnelle [1].

L'ordonnancement sous contraintes énergétiques vise à séquencer les tâches de production en respectant des limites de consommation définies sur un horizon donné, qu'elles soient périodiques, glissantes ou globales. De plus, toutes les tâches ne peuvent pas toujours être réalisées, ce qui introduit la notion d'acceptation ou de rejet des tâches : seules les tâches sélectionnées contribuent au profit total de la production, conformément au cadre de l'Order Acceptance Scheduling présenté dans [2].

Ce travail s'inscrit dans cette perspective et propose d'étudier différentes formulations et méthodes d'optimisation permettant de concilier performance industrielle et usage rationnel de l'énergie, tout en tenant compte des contraintes de disponibilité énergétique et de sélection des tâches. Plusieurs travaux ont récemment intégré ces deux dimensions dans des environnements de production, notamment sous forme de limites énergétiques globales ou périodiques [3, 4].

## 2 Description et formulation du problème

Le problème est modélisé dans un environnement à machine unique, où l'énergie disponible varie au cours du temps selon une contrainte de type fenêtre glissante. On considère un ensemble de tâches $N = 1, ..., n$, où chacune définie par une durée $p_j$, une date limite $d_j$, un profit $w_j$ et une consommation d'énergie $e_j$. L'horizon de planification est découpé en un ensemble de périodes de temps discrètes $\{1, ..., T\}$, avec $T = \max_j\{d_j + 1\}$. La machine peut exécuter au plus une tâche à la fois, sans préemption, et chaque tâche doit être terminée avant sa date limite. L'objectif est de déterminer l'ensemble des tâches à accepter et leur ordonnancement de manière à maximiser le profit total, tout en respectant simultanément les contraintes énergétiques et temporelles.

La contrainte énergétique repose sur un mécanisme de contrôle glissant de la consommation : pour chaque période $t \in \{R, ..., T\}$, la somme de l'énergie consommée par les tâches exécutées au cours des $R$ dernières unités de temps ne doit pas excéder une capacité maximale $E$. Elle s'écrit formellement :

$$ \sum_{j \in N} \sum_{t'=t-R+1}^{t} e_j x_{j,t'} \leq E, \quad \forall t = R, ..., T, $$

où $x_{j,t'}$ est une variable binaire valant 1 si la tâche $j$ est exécutée à la période $t'$, et 0 sinon.
Les paramètres énergétiques *R* (taille de la fenêtre) et *E* (capacité maximale) conditionnent directement la structure et la faisabilité du problème. Une valeur faible de *E* ou une fenêtre courte impose une contrainte locale stricte, limitant la possibilité d'enchaîner des tâches énergivores, tandis qu'une fenêtre plus longue ou un seuil élevé assouplit la contrainte et augmente la flexibilité de planification. L'interaction entre ces deux paramètres détermine la densité énergétique admissible et influence directement les décisions d'acceptation des tâches. Cette interaction illustre le compromis fondamental entre performance économique et contrainte énergétique, qui constitue le cœur du problème étudié.

Pour résoudre ce problème, un modèle de programmation linéaire en nombres entiers mixtes (MILP) a été formulé. Comme le problème est NP-difficile, la résolution exacte devient rapidement coûteuse lorsque le nombre de tâches augmente. Dans ce contexte, une heuristique constructive a été développée afin de générer rapidement des solutions de haute qualité. Celle-ci repose sur un critère de sélection combinant le profit, la durée et la consommation d'énergie, permettant de choisir à chaque itération la tâche la plus avantageuse tout en respectant la contrainte énergétique. Les résultats obtenus montrent que l'heuristique fournit des solutions proches de l'optimum avec des temps de calcul très réduits, confirmant son efficacité sur des instances de grande taille.

Les résultats numériques sont présentés dans le tableau 1, qui compare les performances du modèle MILP à celles de l'heuristique constructive (CH) sur différentes tailles d'instances.

D'autres méthodes de résolution sont actuellement à l'étude. Une perspective de ce travail consiste à étendre le problème à un environnement à machines parallèles, plus représentatif des systèmes industriels réels.

<table><caption>TAB. 1 – Comparaison des performances</caption><thead><tr><th rowspan="2">n</th><th rowspan="2">Instance</th><th colspan="3">MILP</th><th colspan="2">CH</th></tr><tr><th>cpu</th><th>gap</th><th>obj</th><th>cpu</th><th>obj</th></tr></thead><tbody><tr><td rowspan="5">n = 10</td><td>1</td><td>1.65s</td><td>0</td><td>54</td><td>&lt;1s</td><td>36</td></tr><tr><td>2</td><td>0.5s</td><td>0</td><td>72</td><td>&lt;1s</td><td><b>72</b></td></tr><tr><td>3</td><td>1.65s</td><td>0</td><td>64</td><td>&lt;1s</td><td><b>64</b></td></tr><tr><td>4</td><td>1.06s</td><td>0</td><td>61</td><td>&lt;1s</td><td><b>61</b></td></tr><tr><td>5</td><td>5.23s</td><td>0</td><td>49</td><td>&lt;1s</td><td><b>49</b></td></tr><tr><td rowspan="5">n = 25</td><td>1</td><td>523.76s</td><td>0</td><td>136</td><td>&lt;1s</td><td>117</td></tr><tr><td>2</td><td>462.34s</td><td>0</td><td>147</td><td>&lt;1s</td><td><b>147</b></td></tr><tr><td>3</td><td>499.20s</td><td>0</td><td>120</td><td>&lt;1s</td><td>108</td></tr><tr><td>4</td><td>875.62s</td><td>0</td><td>108</td><td>&lt;1s</td><td>104</td></tr><tr><td>5</td><td>93.73s</td><td>0</td><td>172</td><td>&lt;1s</td><td>168</td></tr><tr><td rowspan="5">n = 50</td><td>1</td><td>3600s</td><td>68.14</td><td>298</td><td>&lt;2s</td><td>244</td></tr><tr><td>2</td><td>3600s</td><td>160.10</td><td>195</td><td>&lt;2s</td><td><b>218</b></td></tr><tr><td>3</td><td>3600s</td><td>140.30</td><td>204</td><td>&lt;2s</td><td><b>220</b></td></tr><tr><td>4</td><td>3600s</td><td>137.01</td><td>179</td><td>&lt;2s</td><td><b>199</b></td></tr><tr><td>5</td><td>3600s</td><td>129.28</td><td>186</td><td>&lt;2s</td><td><b>242</b></td></tr></tbody></table>

Références

[1] Gao, K., Huang, Y., Sadollah, A., Wang, L. (2020). *A review of energy-efficient scheduling in intelligent production systems*. Complex & Intelligent Systems, 6(2), 237–249.

[2] Slotnick, S. A. (2011). *Order acceptance and scheduling: A taxonomy and review*. European Journal of Operational Research, 212(1), 1–11.

[3] Kong, M., Pei, J., Liu, X., Lai, P. C., Pardalos, P. M. (2020). *Order acceptance and scheduling under energy budgets*. Journal of Cleaner Production, 248, 119300.

[4] Bouzid, M., Masmoudi, O., Yalaoui, A. (2021). *Single machine order acceptance scheduling with periodic energy consumption limits*. IFIP APMS, Springer.