Exact and approximation algorithms for scheduling and placement problems

Dans cette thèse, nous nous intéressons à la résolution de quelques problèmes d'optimisation combinatoires que nous avons choisi de traiter en deux volets. Dans un premier temps, nous étudions des problèmes d'optimisation issus de l'ordonnancement d'un ensemble de tâches sur des machines de calcul et où on cherche à minimiser l'énergie totale consommée par ces machines tout en préservant une qualité de service acceptable. Dans un deuxième temps, nous traitons deux problèmes d'optimisation classiques à savoir un problème d'ordonnancement dans une architecture de machines parallèles avec des temps de communication, et un problème de placement de données dans des graphes modélisant des réseaux pair-à-pair et visant à minimiser le coût total d'accès aux données.In this thesis, we focus on solving some combinatorial optimization problems that we have chosen to study in two parts. Firstly, we study optimization problems issued from scheduling a set of tasks on computing machines where we seek to minimize the total energy consumed by these machines while maintaining acceptable quality of service. In a second step, we discuss two optimization problems, namely a classical scheduling problem in architecture of parallel machines with communication delays, and a problem of placing data in graphs that represent peer-to-peer networks and the goal is to minimize the total cost of data access