Ordonnancement de tâches pour concilier la minimisation de la consommation d'énergie avec la qualité de service : optimisation et théorie des jeux.
- 31 March 2026
- thesis
- Published by Agence Bibliographique de l'Enseignement Supérieur
Abstract
Job scheduling in order to aggregate energy consumption and quality of service : optimization and game theory: 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.Keywords
This publication has 53 references indexed in Scilit:
- Dual Techniques for Scheduling on a Machine with Varying Speed2013
- On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost2012
- A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling ProblemsLecture Notes in Computer Science, 2011
- Universal Sequencing on a Single Machine2010
- Non-clairvoyant Speed Scaling for Weighted Flow Time2010
- Strategyproof sharing of submodular costs:budget balance versus efficiencyEconomic Theory, 2001
- Potential GamesGames and Economic Behavior, 1996
- Completion time variance minimization on a single machine is difficultOperations Research Letters, 1993
- Minimizing a generalized quadratic penalty function of job completion times: An improved branch-and-bound approachEngineering Costs and Production Economics, 1990
- Various optimizers for single‐stage productionNaval Research Logistics Quarterly, 1956