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. / 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 designed 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.

Nous nous intéressons dans cette thèse à des problèmes d'optimisation liés au domaine des réseaux. Ces problèmes sont d'une part des problèmes d'optimisation ``classiques'' dans lesquels nous cherchons à pallier la NP-difficulté d'un problème en proposant des algorithmes approchés, le plus souvent avec garantie de performance. D'autre part, nous avons considéré des problèmes dans lesquels les utisateurs du réseau sont indépendants et individualistes. Chaque utilisateur souhaite alors optimiser sa propre fonction objectif, qui peut être très différente de la fonction objectif globale que, en tant que concepteurs d'un protocole, nous souhaitons optimiser. Nous nous plaçons alors dans le cadre de la théorie des jeux algorithmique et cherchons à optimiser cette fonction objectif globale en prenant en compte des contraintes supplémentaires dues au fait que les utilisateurs se comportent de façon individualiste. Les problémes que nous avons considérés sont des problémes d'ordonnancement et de routage.