Job scheduling in order to aggregate energy consumption and quality of service: optimization and game theory
This thesis focuses on a job scheduling problem with the goal of minimizing the sum of energy consumption and the weighted flow time from two different approaches: centralized and decentralized. In the decentralized setting, we defined two games which differ in the strategies players can choose from and design cost sharing mechanisms, charging the consumed energy to the users in order to incentive a socially desirable behavior. More precisely we were interested in the existence of pure Nash equilibria, in the convergence time, and the ratio between the consumed energy and the total charged amount. On the other side, for the centralized approach, we reduced the minimization problem to a classical scheduling problem with a polynomial concave penalty function, for which little results were known. We established a state of the art for a family of scheduling problems of this form with different penalty functions and showed that a classical NP-completeness proof technique fails here. Finally we addressed the exact resolution of the problem using the algorithm A*. In this context, we showed new order dominance rules. More precisely, we characterized the conditions under which any optimal solution must schedule a job pair in a certain order. In addition we carried out a computational experience to evaluate the practical impact of these new rules compared to the existing ones.
Defensa : 23/01/2014 - 10h - Site Jussieu - Salle Jean-Louis Laurière - 25-26/101 miembros del jurado : 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)