Ordonnancement sous contraintes d’énergie

Resource constraint scheduling problems have been extensively studied in the literature. However, in most cases it is assumed that the activities have a fixed duration and require a constant amount of the resource throughout their execution. In this thesis, we propose to deal with a scheduling problem in which the tasks have a duration and a variable consumption consumption profile. This profile, which can vary as a function of time, is a decision variable of the problem on which the duration of the associated task depends. On the other hand, the consideration of linear and non-linear output functions for representing the use of resources complicates the problem and makes it possible to realistically model transfers of energy resources. For this NP-complete problem, we present several properties allowing to derive models and methods of resolution. These methods of resolution are divided into two parts. The first part shows the problem from the perspective of Constraint Programming and several methods derived from this paradigm are detailed including the development of energy thinking about the problem studied. The second part of the thesis is dedicated to approaches to Linear Programming and Mixed several models, including a continuous-time model based on the events, as well as theoretical analyzes and models of these enhancement techniques are presented. Finally, experiments come support the results presented in this manuscript.Les problèmes d’ordonnancement à contraintes de ressource ont été largement étudiés dans la littérature. Cependant, dans la plupart des cas, il est supposé que les activités ont une durée fixe et nécessitent une quantité constante de la ressource durant toute leur exécution. Dans cette thèse, nous nous proposons de traiter un problème d’ordonnancement dans lequel les tâches ont une durée et un profil de consommation de ressource variables. Ce profil, qui peut varier en fonction du temps, est une variable de décision du problème dont dépend la durée de la tâche associée. Par ailleurs, la considération de fonctions de rendement linéaires et non linéaires pour la représentation de l’utilisation des ressources complexifie le problème et permet de modéliser de manière réaliste les transferts de ressources énergétiques. Pour ce problème NP-complet, nous présentons plusieurs propriétés permettant de dériver des modèles et méthodes de résolution. Ces méthodes de résolution sont divisées en deux parties. La première partie visualise ce problème du point de vue de la Programmation Par Contraintes et plusieurs méthodes dérivées de ce paradigme sont détaillées dont le développement du raisonnement énergétique sur le problème étudié. La seconde partie de la thèse est dédiée à des approches de Programmation Linéaire Mixte et plusieurs modèles, notamment un modèle à temps continu basé sur les événements, ainsi que des analyses théoriques et des techniques d’amélioration de ces modèles sont présentés. Enfin, des expérimentations viennent appuyer les résultats présentés dans ce manuscrit