🔢 mathematics

Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approach

Cet article traite du problème d'ordonnancement de projets avec contraintes de ressources, incluant des tarifs énergétiques selon l'heure d'utilisation et des états de machines, en proposant une approche de décomposition de Benders à base de logique qui surpasse considérablement les méthodes monolithiques pour minimiser la durée d'exécution et les coûts énergétiques, tout en démontrant sa généralisabilité à d'autres problèmes d'ordonnancement complexes.

Auteurs originaux : Corentin Juvigny, Antonín Novák, Jan Mandík, Zdeněk Hanzálek

Publié 2026-07-07

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Corentin Juvigny, Antonín Novák, Jan Mandík, Zdeněk Hanzálek

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous soyez le directeur d'une usine très occupée. Vous avez une liste de tâches à accomplir, des machines qui ne peuvent effectuer qu'une seule chose à la fois, et un ensemble strict de règles sur l'ordre de priorité des tâches. C'est le problème classique de l'« Ordonnancement de Projets avec Contraintes de Ressources » (RCPSP). C'est comme essayer d'organiser un mariage massif où le traiteur, l'orchestre et le lieu de réception ont tous des disponibilités limitées, et où la découpe du gâteau ne peut pas avoir lieu avant la cérémonie.

Mais maintenant, ajoutez un rebondissement : les prix de l'électricité changent tout au long de la journée.

À certaines heures, l'énergie est bon marché (comme à 3 heures du matin) ; à d'autres, elle est coûteuse (comme à 17 heures). De plus, votre machine la plus gourmande en énergie (appelons-la le « Grand Four ») a trois humeurs :

Cuisson (Proc) : Il fonctionne et consomme de l'énergie.
Veille (Idle) : Il est chaud mais ne cuit rien. Il utilise un peu d'énergie pour rester prêt.
Éteint (Off) : Il est froid. Le rallumer prend du temps et nécessite une énorme pointe d'énergie.

Votre objectif est de planifier chaque tâche de manière à terminer le travail le plus vite possible et à dépenser le moins d'argent possible en électricité. C'est un équilibre délicat : faut-il faire fonctionner le four pendant les heures creuses, même si cela signifie que toute l'usine attend ? Ou faut-il se dépêcher de finir tôt, même si cela coûte une fortune en électricité pendant les heures de pointe ?

Le Problème : Un Puzzle Trop Grand pour un Seul Cerveau

Les auteurs de ce document ont tenté de résoudre ce puzzle en utilisant deux méthodes traditionnelles :

Le « Monolithique » ILP : Essayer d'écrire une seule équation mathématique géante qui tient compte de chaque tâche, de chaque seconde de temps et de chaque état de machine à la fois. C'est comme essayer de résoudre un puzzle de 1 000 pièces les yeux bandés, en tenant toutes les pièces dans une seule main.
Le « Monolithique » CP : Un autre type de solveur logique qui est très bon pour l'ordonnancement, mais qui peine lorsqu'on ajoute les règles complexes de « prix de l'électricité ».

Les deux méthodes fonctionnaient assez bien pour de petits puzzles, mais quand l'usine devenait plus grande (plus de tâches), elles restaient bloquées. Elles ne parvenaient pas à trouver la meilleure solution dans un délai raisonnable.

La Solution : Le « Chef de Cuisine » et le « Commis »

Les auteurs ont proposé une nouvelle méthode plus intelligente appelée Décomposition de Benders à Base de Logique (LBBD). Voyez cela comme la division du travail entre deux personnes ayant des compétences différentes :

Le Chef de Cuisine (Le Problème Maître) : Cette personne est un expert en argent. Elle regarde le graphique des prix de l'électricité et décide : « D'accord, le Grand Four doit être en mode cuisson pendant ces heures peu coûteuses et en mode repos pendant les heures coûteuses. » Elle ne se soucie pas de savoir quel gâteau spécifique va dans le four ; elle définit simplement le planning de l'« humeur » du four (Allumé, Veille, Éteint) pour économiser de l'argent. Elle utilise un solveur mathématique rapide (ILP) pour cela.
Le Commis (Le Sous-problème) : Cette personne est un expert en logistique. Elle prend le planning du four du Chef de Cuisine et demande : « Pouvons-nous réellement faire tenir toutes les autres tâches (les gâteaux, les décorations, les invités) autour de ce planning du four sans briser aucune règle ? » Elle utilise un moteur logique puissant (Programmation par Contraintes) pour vérifier si le plan fonctionne.

Comment ils communiquent :

Le Chef de Cuisine propose un plan.
Le Commis essaie de l'exécuter.
Si cela fonctionne : Parfait ! Ils vérifient s'ils peuvent faire encore mieux.
Si cela échoue : Le Commis dit : « Hé, vous ne pouvez pas mettre le four en mode "Éteint" à 14h parce que la pâte à gâteau doit être prête à ce moment-là ! »
Le Chef de Cuisine prend ce retour, apprend de cette erreur et propose un nouveau plan qui évite cette erreur spécifique.

Ils répètent cette conversation jusqu'à ce qu'ils trouvent le planning parfait.

Ce Qu'Ils Ont Découvert

Les auteurs ont testé cette « Approche d'Équipe » contre l'« Approche Solo » sur des centaines de scénarios d'usine différents :

Lorsque l'objectif est purement l'économie d'argent (en ignorant la durée du travail) : L'Approche d'Équipe (LBBD) a été la grande gagnante. Elle a résolu des problèmes allant jusqu'à 480 tâches parfaitement, tandis que les méthodes solo abandonnaient ou mettaient un temps infini. C'était comme avoir un GPS qui sait exactement quand conduire pour éviter les embouteillages, alors que le conducteur solo ne faisait que deviner.
Lorsque l'objectif est un mélange de vitesse et d'argent : L'Approche d'Équipe était toujours la meilleure, surtout pour les grandes usines encombrées.
L'Exception : Si l'usine était très vide (peu de tâches) et que la vitesse était le seul critère important, l'ancienne « Logique Solo » (Programmation par Contraintes) était parfois plus rapide.

Le « Tour de Magie » (Généralisation)

La partie la plus excitante de l'article est que ce travail d'équipe « Chef de Cuisine / Commis » n'est pas réservé à cette usine spécifique. Les auteurs ont montré que vous pouvez utiliser cette même stratégie de travail d'équipe pour d'autres types de problèmes d'ordonnancement, comme :

Les Ateliers à Travaux Flexibles (Flexible Job Shops) : Où une tâche peut être effectuée sur n'importe laquelle de plusieurs machines.
Les Projets avec « Blocage » : Où une machine est coincée en attendant qu'une pièce arrive.

Dans tous ces cas, séparer la décision « Énergie/Argent » de la décision « Tâche/Temps » a permis à l'ordinateur de résoudre le problème beaucoup plus rapidement et de trouver de meilleures solutions.

Résumé

En termes simples, cet article affirme que : N'essayez pas de résoudre tout le puzzle de l'ordonnancement énergétique avec un seul cerveau géant. Au lieu de cela, divisez le travail. Faites en sorte qu'un expert s'occupe des factures d'électricité et qu'un autre s'occupe de la logistique des tâches. Laissez-les communiquer jusqu'à ce qu'ils s'entendent sur le meilleur plan. Cette méthode est plus rapide, plus intelligente et peut gérer des usines réelles beaucoup plus grandes et complexes que les anciennes méthodes.

Résumé Technique : Ordonnancement de Projets avec Contraintes de Ressources, Tarifs Énergétiques de Type « Heures de Pointe » et États de Machines

1. Définition du Problème

L'article traite d'une variante du Problème d'Ordonnancement de Projets avec Contraintes de Ressources (RCPSP) qui intègre des tarifs énergétiques de type « Heures de Pointe » (Time-of-Use - TOU) et des transitions d'états de machines. Le problème implique l'ordonnancement d'un ensemble de tâches non préemptives soumises à des contraintes de précédence et à des capacités de ressources limitées.

Les caractéristiques clés incluent :

Ressource énergivore : Une ressource spécifique ( $R_0$ ) possède une capacité unitaire et est énergivore. Elle peut exister sous trois états : proc (traitement), idle (repos/inactif), ou off (éteint).
Transitions d'états : Les transitions entre les états entraînent des durées et des coûts énergétiques spécifiques. Par exemple, allumer ou éteindre une machine consomme une énergie et un temps considérables. La machine doit commencer et finir dans l'état off.
Classification des tâches : Les tâches sont divisées en tâches énergivores (nécessitant $R_0$ en mode proc) et en tâches non énergivores (qui n'utilisent pas $R_0$ ).
Objectif : Le but est de minimiser une combinaison convexe du Coût Énergétique Total (TEC) et de la Durée de Réalisation (Makespan - $C_{max}$ ). Le TEC est calculé sur la base de tarifs TOU, qui peuvent varier dans le temps et même prendre des valeurs négatives. La fonction objectif est normalisée à l'aide de bornes inférieures dérivées d'optimisations indépendantes des composantes TEC et $C_{max}$ .

2. Méthodologie

Les auteurs proposent et comparent trois approches de modélisation distinctes :

A. Modèles Monolithiques
Deux modèles compacts sont formulés pour résoudre le problème dans son ensemble :

ILP Monolithique : Un modèle de programmation linéaire en nombres entiers utilisant des variables indexées par le temps. Il incorpore des coûts de transition optimaux précalculés (via l'algorithme SPACES) entre les intervalles de traitement pour gérer les états de la machine.
CP Monolithique : Un modèle de programmation par contraintes utilisant des variables d'intervalle optionnelles. Cette approche représente le traitement des tâches et les transitions d'états optimales comme des variables d'intervalle, permettant au solveur de déterminer dynamiquement le nombre et le placement des transitions.

B. Décomposition de Benders basée sur la Logique (LBBD)
La contribution principale est une approche LBBD hybride qui décompose le problème en deux sous-problèmes couplés :

Problème Maître (ILP) : Résout l'optimisation de l'état de la machine et du coût énergétique. Il détermine les temps de début des tâches énergivores et la séquence des transitions d'état. Il utilise un graphe SPACES modifié pour calculer les coûts de transition.
Sous-problème (CP) : Une vérification de faisabilité pour la composante RCPSP. Étant donné les temps de début fixes des tâches énergivores provenant du Problème Maître, il tente d'ordonnancer toutes les tâches non énergivores restantes tout en respectant les capacités de ressources et les contraintes de précédence.
Coupes (Cutting Planes) :
- Coupes de Faisabilité : Générées lorsque le sous-problème est infaisable, empêchant le Problème Maître de sélectionner le même ensemble conflictuel de temps de début de tâches énergivores.
- Coupes d'Optimalité : Générées lorsque le sous-problème est faisable mais produit un makespan différent de l'estimation du Problème Maître. Ces coupes utilisent le chemin critique du graphe de flux de ressources pour imposer une borne inférieure sur le makespan dans le Problème Maître.

3. Contributions Clés

Formulation du Problème : L'introduction d'une nouvelle variante du RCPSP qui couple la dynamique d'état des machines (proc, idle, off) avec les tarifs TOU, étendant les études précédentes sur une seule machine à un contexte d'ordonnancement de projet multi-ressources.
Cadre LBBD Novateur : Le développement d'une stratégie de décomposition qui sépare la gestion de l'énergie (Maître) de l'ordonnancement combinatoire (Sous-problème). Les auteurs dérivent des coupes de Benders spécifiques adaptées à l'interaction entre les états de la machine et les contraintes RCPSP.
Généralisation : Démonstration que l'architecture LBBD est applicable à d'autres problèmes d'ordonnancement, spécifiquement :
- Le RCPSP avec temps de blocage et un objectif de retard pondéré total.
- L'ordonnancement de type Flexible Job Shop (FJSP).

4. Résultats Expérimentaux

Des expériences ont été menées sur des instances issues du jeu de données PSPLIB, classées selon la densité des tâches énergivores (Sparse/Épars, Standard, Dense) et selon divers paramètres de pondération ( $\alpha$ ) entre le coût énergétique et le makespan.

Performance vs Modèles Monolithiques :
- Les approches monolithiques ILP et CP sont toutes deux surpassées par la LBBD dans la plupart des scénarios, particulièrement pour les instances de grande taille (jusqu'à 480 tâches) et lorsque le critère de makespan est moins dominant ( $\alpha \to 1$ ).
- L'approche LBBD résout les instances vers l'optimalité nettement plus rapidement que le CP monolithique, qui peine face à de grands espaces de recherche.
- L'ILP monolithique performe raisonnablement bien mais est généralement plus lent que la LBBD.
Impact des Paramètres :
- $\alpha = 1$ (Énergie uniquement) : La LBBD performe exceptionnellement bien, car le sous-problème se réduit à une simple vérification de faisabilité, que les solveurs CP gèrent efficacement.
- $\alpha < 1$ (Objectifs mixtes) : La LBBD reste supérieure dans les instances Standard et Dense. Cependant, dans les instances Éparses (Sparse) avec un faible $\alpha$ (poids élevé du makespan), le CP monolithique surpasse parfois la LBBD car les limites de temps du sous-problème dans la LBBD peuvent entraver l'exploration de l'espace de recherche.
Résultats de Généralisation :
- Pour le RCPSP avec temps de blocage, la LBBD a trouvé des solutions optimales pour près de 90 % des instances en moins de 30 minutes, contre moins de 5 % pour le CP monolithique.
- Dans le problème Flexible Job Shop, la LBBD a trouvé des solutions faisables plus fréquemment (107/120 fois) que l'ILP monolithique (83/120 fois) sous des contraintes de temps.

5. Signification et Revendications

L'article affirme que l'approche LBBD proposée représente une avancée significative pour les problèmes d'ordonnancement sensibles à l'énergie impliquant des états de machines complexes. Sa principale importance réside dans sa capacité à découpler l'optimisation continue du coût énergétique de la décomposition des contraintes d'ordonnancement combinatoires discrètes, permettant à chacune d'être résolue par le solveur le plus approprié (ILP pour l'énergie, CP pour l'ordonnancement).

Les auteurs soutiennent que cette décomposition n'est pas seulement efficace pour le problème spécifique RCPSP-TOU, mais constitue un cadre généralisable pour tout problème d'ordonnancement où les activités énergivores peuvent être séparées de la logique d'allocation des autres ressources. Le travail souligne que si les modèles monolithiques sont intuitifs, ils échouent souvent à passer à l'échelle avec la taille et la complexité des problèmes, tandis que l'approche LBBD maintient sa robustesse à travers diverses densités d'instances et pondérations d'objectifs.

L'article conclut en notant que des travaux futurs pourraient explorer des ressources énergivores multiples, des transitions d'états plus complexes, et l'intégration du stockage d'énergie ou de la production sur site, ainsi que l'impact de l'incertitude des tarifs énergétiques.