VÁSQUEZ PÉREZ Óscar Carlos

Docteur
Équipe : RO
Date de départ : 31/03/2014
https://sites.google.com/a/usach.cl/oscar-cvasquez/
Direction de recherche : Christoph DÜRR

Minimisation de l'énergie et conception d'algorithmes avec une approche théorie des jeux

Cette thèse est consacrée au problème d'ordonnancement de tâches qui consiste à minimiser la somme de l'énergie consommée et le temps d'attente pondéré total, et l'aborde de deux différents points de vue~: centralisé et décentralisé. Pour l'approche décentralisée, nous avons défini deux types de jeux qui diffèrent dans les actions proposées aux joueurs et avons cherché des moyens de facturer l'énergie consommée aux utilisateurs pour les inciter à adopter un bon comportement. Concrètement nous nous intéressons à l'existence d'équilibres de Nash purs, au temps de convergence vers ces équilibres, et au rapport entre l'énergie consommée et le montant des factures. Pour l'approche centralisée, nous avons réduit le problème de minimisation à un problème d'ordonnancement plus classique avec une fonction de pénalité de retard polynomiale concave, pour lequel peu résultats ont été connus. Après avoir établi un état de l'art sur la famille de problèmes d'ordonnancement pour plusieurs fonctions de pénalité élémentaires et montré qu'une technique de preuve de NP-complétude classique échoue ici, nous nous sommes intéressés à sa résolution exacte. Pour améliorer les performances de l'algorithme A* dans ce contexte, nous avons montré des résultats de règles de dominance. Concrètement, nous avons cherché à déterminer les conditions sous lesquelles une solution optimale devrait ordonnancer une paire de tâches dans un certain ordre. Ces résultats sont appuyés par une étude expérimentale qui évalue l'impact pratique de ces nouvelles règles, par rapport aux règles existantes.
Soutenance : 23/01/2014 - 10h - Site Jussieu - Salle Jean-Louis Laurière - 25-26/101
Membres du jury :
LARAKI Rida (Universite Paris Dauphine, LAMSADE) [rapporteur]
MASTROLILLI Monaldo (Istituto Dalle Molle di Studi sull'Intelligenza Artificiale, Lugano) [rapporteur]
DÜRR Christoph (CNRS, LIP6, UPMC)
GOURVÈS Laurent (Universite Paris Dauphine, LAMSADE)
KEDAD-SIDHOUM Safia (LIP6, UPMC)
SOUKHAL Ameur (École Polytecnique de l'Université de Tours)
 Mentions légales
Carte du site |