Institut de la Francophonie pour l’Informatique de Hanoi Ordonnancement sous contraintes de consommation énergétique Mémoire de fin d’études MANGOUA SOFACK William (mswilliam@ifi.vn) Encadrement : Christian ARTIGUES et Pierre LOPEZ Laboratoire d’Analyse et d’Architecture des Systèmes 19 octobre 2009 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Dédicaces A Mon matelas, Ma couverture, Mon oreiller. i LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Remerciements Mes premiers remerciements vont à mes encadreurs Christian ARTIGUES et Pierre LOPEZ pour le temps qu’il m’ont consacré durant ce stage, leur soutien, leurs conseils scientifiques, leur disponibilité et leurs aides précieuses qui ont été nécessaires pour aller jusqu’au bout de ce travail de stage. Je tiens à remercier tous les membre de l’équipe MOGISA, particulièrement : Oumar (Le Mogor), Wafa, Touria et Christèle pour leur amitié, leur soutien et leur accueil dans le groupe. Je remercie Monsieur Ngo Hong Son pour avoir accepté d’être le rappor- teur de ce travail et pour son précieux temps qu’il y a accordé.
Je tiens à remercier le directeur et les Professeurs de l’IFI, qui m’ont donné des connaissances et m’ont aidé, par leurs encouragements à bien suivre la formation de master. Je remercie aussi tout le staff administratif de l’IFI pour leurs encouragement. Il s’agit de M. Son, Mme Hien, Mme Loan et M.
Je remercie sincèrement mes camarades de classes qui m’ont accueilli et couvert de beaucoup de chaleur durant mon séjour au Vietnam. Je fais un clin d’œil particulier à Kim Dung, Giap, Hiep et Luyen. Mes remerciements vont aussi aux membres de ma grande famille pour leur encouragement, leurs prières et leur présence malgré la distance. Je ne saurais terminer sans remercier mes amis, les Bikunda.
ii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Résumé Le raisonnement énergétique est une technique particulière de propaga- tion de contraintes. Celui-ci s’appuie sur les concepts d’intervalle temps- ressource et d’énergie pour raisonner simultanément sur les contraintes de temps et de ressources. Il est basé sur l’évaluation de l’énergie réellement dis- ponible pour l’exécution d’une tâche sur un intervalle de temps, compte tenu de la consommation des autres tâches. Grâce à cette évaluation, des bilans énergétiques peuvent mettre en évidence un manque d’énergie sur cet inter- valle, ce qui amène à produire des conditions de séquencement entre tâches ou interdire la localisation d’une tâche sur certains intervalles de temps.
La littérature nous propose un ensemble d’intervalles à utiliser pour détecter une infaisabilité d’un problème de type cumulatif (CuSP : Cumulative Sche- duling Problem). Dans ce rapport, nous proposons un ensemble d’intervalles semblables, approprié à un contexte plus général de problème énergétique (EnSP : Energetic Scheduling Problem). Mots-clés : recherche opérationnelle, programmation par contraintes, propagation de contraintes, raisonnement énergétique, analyse énergétique, intervalle temps-ressource, consommation obligatoire, problème EnSP, pro- blème CuSP. iii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Abstract The energetic reasoning is a special technique of constraint propagation.
It builds on the concepts of time-resource interval and energy simultaneously to reason about the time constraints and resources constraints. It is based on the evaluation of the energy actually available for the execution of a task on a time interval, given the consumption of other tasks. Through this quantification, energy audits can highlight a lack of energy on this interval, which leads to produce conditions of sequencing between tasks or prohibit the location of a certain task on time intervals. The literature offers a set of intervals to be used to detect infeasibility of a cumulative problem (CuSP : Cumulative Scheduling Problem).
In this report we propose a set of similar intervals, suitable for a more general problem of energy (EnSP : Energetic Scheduling Problem). Keywords : operational research, constraint programming, constraint propagation, energetic reasoning, energetic analysis, time-ressource interval, required consumption, EnSP problem, CuSP problem. iv LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des matières Dédicaces i Remerciements ii Résumé iii Abstract iv Table des matières vi 1 Introduction générale 1 1.2 Problématique, contexte et positionnement .4 Plan du mémoire. 3 2 Etat de l’art 4 2.1 Problème d’ordonnancement sous contraintes énergétiques .4 Le problème EnSP .2 Propagation de contraintes .2 Techniques de propagation de contraintes pour les res- sources cumulatives.
12 v LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com TABLE DES MATIÈRES vi 2.3 Le raisonnement énergétique .1 L’intervalle temps-ressource .2 Consommation obligatoire d’une tâche sur un inter- valle fournisseur .4 Principe de l’approche énergétique .1 Propriétés du raisonnement énergétique .2 Problème du raisonnement énergétique .5 Autres approches du raisonnement énergétique .1 Raisonnement énergétique amélioré .2 Raisonnement énergétique / enveloppe énergétique .3 Raisonnement énergétique pour des activités trapézoï- dales .6 Résumé et analyse de l’existant. 20 3 Le raisonnement énergétique pour le problème EnSP 23 3.2 Les instants remarquables .1 Analyse énergétique au plus tôt .2 Analyse énergétique au plus tard .3 Les combinaisons possibles des instants remarquables .4 Cas particulier du problème CuSP .3 Propriétés des instants remarquables .4 Les intervalles remarquables .1 Les bornes des intervalles remarquables .2 Réduction de l’ensemble d’intervalles. 48 Ordonnancement sous contraintes de consommation énergétique LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des figures 2.1 Situation de notre travail.2 Solution d’un problème EnSP.3 Cas possibles pour 𝑤𝐿 (𝑖, 𝑡1 , 𝑡2 ).1 Analogie EnSP/Principe des vases communicants .3 Progression de 𝑓 (𝑥) en grande pente .5 Progression de 𝑓 (𝑥) en petite pente .7 Progression de 𝑓 (𝑥) en grande pente .8 Tâche calée à gauche à l’instant remarquable 𝑥4 .9 Tâche calée à droite à l’instant remarquable 𝑥4 .10 Tâche calée à gauche à l’instant remarquable 𝑥5 .11 Tâche calée à droite à l’instant remarquable 𝑥5 .13 Allure de 𝑓 (𝑥) avec la configuration 1 .15 Allure de 𝑓 (𝑥) avec la configuration 2 .17 Allure de 𝑓 (𝑥) avec la configuration 3 .19 Allure de 𝑓 (𝑥) avec la configuration 4. 41 vii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Liste des tableaux 2.1 Les contraintes de l’exemple 2 .2 Les résultats des calculs de l’exemple 2 .3 Mise en évidence de l’infaisabilité de l’exemple 2 .4 Contraintes de l’exemple 3 .1 Instants remarquables issus de l’analyse énergétique au plus tôt 34 3.2 Instants remarquables issus de l’analyse énergétique au plus tard .3 Ensembles d’instants remarquables issus de l’analyse énergé- tique au plus tôt .4 Ensembles d’instants remarquables issus de l’analyse énergé- tique au plus tard .5 Similitudes entre les résultats des problèmes CusP et EnSP .6 Intersection des plans.
43 viii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapitre 1 Introduction générale 1.1 Introduction L’objectif général du stage concerne l’organisation de l’exécution d’activi- tés (ordonnancement) et la maîtrise des consommations d’énergie électrique dans les ateliers de production. La méthodologie proposée est l’application de techniques de propagation de contraintes particulières (faisant référence au «raisonnement énergétique») pour limiter les décisions en termes d’allocation de machines aux activités et de positionnement temporel de ces activités. Si le raisonnement énergétique existe et a été exploité pour la résolution de problèmes d’ordonnancement depuis une quinzaine d’années, il n’a jamais été étendu pour la prise en compte de contraintes particulières issues des consommations électriques dans la fabrication de biens (on a notamment un intervalle de puissances à respecter sur des fours qui constituent nos machines ainsi qu’un lien entre la puissance utilisée par les machines et les durées des activités). Des premiers résultats ont été obtenus et montrent le bien-fondé de l’emploi d’un tel raisonnement dans ce contexte.
Il reste toutefois à valider les formules analytiques proposées, à identifier les intervalles temporels per- tinents pour l’application du raisonnement énergétique, à intégrer l’approche dans une méthode de résolution générale («Branch-and-Bound»), enfin à va- lider expérimentalement la démarche par une série de tests réalistes. 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Problématique, contexte et positionnement 2 1.2 Problématique, contexte et positionnement L’ordonnancement sous contraintes peut être défini comme un thème qui étudie la manière de résoudre les problèmes d’ordonnancement en utilisant la programmation par contraintes [Bap98]. Une des idées-clé de la programma- tion par contraintes (CP : Constraint Programming) est que les contraintes peuvent être utilisées «activement» pour réduire le domaine de solutions, dé- duire de nouvelles contraintes et détecter d’éventuelles inconsistances. Le fait d’utiliser des contraintes de la sorte pour obtenir certaines déductions est ap- pelé propagation de contraintes [Bap98].
Le raisonnement énergétique est une technique particulière de propagation de contraintes [Lop91]. Celui-ci s’ap- puie sur les concepts d’intervalle temps-ressource et d’énergie pour raisonner simultanément sur les contraintes de temps et de ressources. Le schéma général de résolution est de type Branch-and-Bound auquel le raisonnement énergétique à été intégré. Plu- sieurs questions non résolues restent posées dans ces travaux.
L’analyse faite dans le raisonnement énergétique s’appuie sur des intervalles de temps bien précis et clairement identifiés dans [Bap98], pour une sous-classe de problèmes d’ordonnancement dits problèmes cumulatifs (CuSP : Cumulative Scheduling Problem). Le problème est de savoir si ce même ensemble d’intervalles est suf- fisant dans un cadre plus général du problème d’ordonnancement énergétique (EnSP : Energetic Scheduling Problem). Dans le cadre de notre stage, réalisé au sein du groupe Modélisation, Optimisation et Gestion Intégrée de Systèmes d’Activités (MOGISA) du La- boratoire d’Analyse et d’Architecture des Systèmes (LAAS), nous avons es- sayé de répondre à cette question. Ces travaux se situent dans le domaine de la recherche opérationnelle, précisément celui de la programmation par contraintes, et s’inscrivent dans le cadre de la recherche fondamentale.
Plu- sieurs travaux à l’instar de [Bap98], [Lop91] et [ALH09] se sont penchés sur ces problèmes et les résultats obtenus jusqu’à présent montrent que le do- maine est encore ouvert. Ordonnancement sous contraintes de consommation énergétique LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3 Contribution Le but de ce travail de stage est de proposer un ensemble suffisant d’inter- valles à utiliser pour établir l’infaisabilité d’un problème EnSP avec l’analyse énergétique. En plus d’un état de l’art sur le sujet, nous avons d’abord pro- posé les instants remarquables associé à un problème EnSP. Avec ces instants, nous avons construit les intervalles cherchés.
Nous avons aussi proposé un si- mulateur permettant de simuler l’analyse énergétique au plus tôt d’une tâche et d’obtenir sa courbe de consommation obligatoire.4 Plan du mémoire Après cette introduction générale, nous présentons, dans le chapitre 2, un état de l’art relatif aux références pertinentes permettant d’appuyer le propos de ce stage. Le premier paragraphe traite des problèmes d’ordon- nancement énergétique. Nous en présentons une introduction générale, une définition et une classification suivie d’une présentation du problème EnSP. Le deuxième paragraphe traite de la propagation de contraintes.
Nous y fai- sons une introduction suivie d’un tour d’horizon de quelques techniques de propagation de contraintes appliquées aux ressources cumulatives. Les trois paragraphes suivants sont réservés au raisonnement énergétique. Nous abor- derons les notions d’intervalle temps-ressource et de consommation obliga- toire d’une tâche. Il sera ensuite question des propriétés relatives au principe du raisonnement énergétique.
Nous évoquerons aussi d’autres façons d’ap- préhender le raisonnement énergétique. Nous terminons ce chapitre par une synthèse de l’existant qui contient un résumé et une analyse de l’existant. Le troisième chapitre de ce mémoire présente la contribution qu’apporte ce travail. Il y sera essentiellement question d’instants et d’intervalles remar- quables.
Le premier paragraphe donne le détail de l’obtention des instants remarquables. Le second présente les propriétés de ces instants remarquables. Le dernier paragraphe nous dévoile les intervalles cherchés. Ordonnancement sous contraintes de consommation énergétique LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapitre 2 Etat de l’art Résumé L’objectif de cette partie est de dresser un état de l’art sur le raisonnement énergétique.
Ceci n’est pas une recherche bibliographique exhaustive sur le sujet. C’est surtout une présentation d’un ensemble de références pertinentes nous permettant de mieux l’aborder. Dans un premier temps, nous présen- tons le problème à résoudre. Après cette formulation, nous exposons dans un second temps le principe général de la propagation de contraintes, puis celui du raisonnement énergétique.
Enfin, nous abordons quelques solutions existantes dans la littérature.1 Problème d’ordonnancement sous contraintes énergétiques 2.