Le 14/10/2016 par plopez :

DOCTORAT DE L'UNIVERSITE DE TOULOUSE


Délivré par l'Université Paul Sabatier






Titre :


Ordonnancement sous contraintes énergétiques





de


Margaux NATTAF (Equipe--- ROC)


E-mail : mnattaf@laas.fr





Date : 18 Octobre 2016 à 14h00


Lieu : LAAS-CNRS - Salle de Conférences


7 avenue du Colonel Roche


31077 TOULOUSE Cedex 4





Composition du jury :


DIRECTEURS DE THÈSE


Christian ARTIGUES, Directeur de Recherche, LAAS-CNRS


Pierre LOPEZ, Directeur de Recherche, LAAS-CNRS





RAPPORTEURS


Philippe BAPTISTE, Directeur Scientifique, TOTAL, Paris


Claude-Guy QUIMPER, Professeur associé, Université Laval, Québec





EXAMINATEURS


Cyril BRIAND, Professeur des Universités, Université Paul Sabatier


Tamas KIS, Research Fellow, MTA SZTAKI, Budapest


Philippe LABORIE, Principal Scientist, IBM, Paris


Alain QUILLIOT, Professeur des Universités, Université Blaise Pascal, Clermont Ferrand







Résumé :




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.



Mots-clés : complexité - Energie - ordonnancement - programmation mathématique - propagation de contraintes - recherche arborescente et locale