La gestion de la consommation d’énergie et de la température est devenue un enjeu crucial dans les systèmes informatiques. En effet, un grand centre de données consomme autant d’électricité qu’une ville et les processeurs modernes atteignent des températures importantes dégradant ainsi leurs performances et leur fiabilité. Dans cette thèse, nous étudions différents problèmes d’ordonnancement prenant en compte la consommation d’énergie et la température des processeurs en se focalisant sur leur complexité et leur approximabilité. Pour cela, nous utilisons le modèle de Yao et al. (1995) (modèle de variation de vitesse) pour la gestion d’énergie et le modèle de Chrobak et al. (2008) pour la gestion de la température. / Nowadays, the enegy consumption and the heat dissipation of computing environments have emerged as crucial issues. Indeed, large data centers consume as muse electricity as a city while modern processors attain high temperatures degrading their performance and decreasing their reliability.. In this thesis, we study various energy and temperature aware scheduling problems and we focus on their complexity and approximability. A dominant technique for saving energy is by prosper scheduling of the jobs through the operating system combined with appropriate scaling of the processor's speed. This technique is referred to as speed scaling in the literature and its theoretical study was initiated by Yao, Demers and Shenker (FOCS'1995). In order to manage the thermal behavior of a computing device, we adaopt the approach of Chrobak, Dürr, Hurand and Robert (AAIM'2008). The main assumption is that some jobs are more CPU intensive than others and more heat is generated during their execution. Moreover, the cooling of a computing device occurs by introducing appropriate idle periods.

Cette thèse se focalise sur des algorithmes efficaces en énergie pour des problèmes d'ordonnancement de tâches sur des processeurs pouvant varier la vitesse d'exécution ainsi que sur des processeurs fonctionnant sous un mécanisme de réchauffement-refroidissement, où pour un budget d'énergie donné ou un seuil thermique, l'objectif consiste à optimiser un critère de Qualité de Service. Une partie de notre recherche concerne des problèmes d'ordonnancement de tâches apparaissant dans des environnements de traitement de grandes données. Dans ce contexte, nous nous focalisons sur le paradigme MapReduce en considérant des problèmes d'ordonnancement efficaces en énergie sur un ensemble de processeurs, ainsi que pour la version classique.Premièrement, nous proposons des résultats de complexité, des algorithmes optimaux et approchés pour différentes variantes du problème de la minimisation du retard maximal d'un ensemble de tâches sur un processeur pouvant varier la vitesse d'exécution. Ensuite, nous considérons le problème d'ordonnancement MapReduce dans les versions énergétique et classique sur des processeurs non-reliés où le but est de minimiser le temps d'achèvement pondéré. Nous étudions deux cas spéciaux et les généralisations de ces deux problèmes en proposant des algorithmes d'approximation constante. Enfin, nous étudions le problème d'ordonnancement dans lequel la température du processeur est en-dessous un seuil donné où chaque tâche contribue au réchauffement et le but est de maximiser le nombre de tâches exécutées. Nous considérons le cas où les tâches ont des durées unitaires et ayant la même date d'échéance et nous étudions le rapport d'approximation de ce problème. / This thesis is focused on energy-efficient algorithms for job scheduling problems on speed-scalable processors, as well as on processors operating under a thermal and cooling mechanism, where, for a given budget of energy or a thermal threshold, the goal is to optimize a Quality of Service criterion. A part of our research concerns scheduling problems arising in large-data processing environments. In this context, we focus on the MapReduce paradigm and we consider problems of energy-efficient scheduling on multiple speed-scalable processors as well as classical scheduling on a set of unrelated processors.First, we propose complexity results, optimal and constant competitive algorithms for different energy-aware variants of the problem of minimizing the maximum lateness of a set of jobs on a single speed-scalable processor. Then, we consider energy-aware MapReduce scheduling as well as classical MapReduce scheduling (where energy is not our concern) on unrelated processors, where the goal is to minimize the total weighted completion time of a set of MapReduce jobs. We study special cases and generalizations of both problems and propose constant approximation algorithms. Finally, we study temperature-aware scheduling on a single processor that operates under a strict thermal threshold, where each job has its own heat contribution and the goal is to maximize the schedule's throughput. We consider the case of unit-length jobs with a common deadline and we study the approximability of the problem.

L'éruption de 2010 du Merapi est la première grande éruption explosive du volcan qui a été observée instrumentalement. Dans ce travail, nous étudions les précurseurs de l'éruption et le comportement du volcan avant l'éruption en reliant les caractéristiques sismiques avec d'autres observations disponibles. Nous présentons les principaux aspects de l'activité sismique au cours de la crise de 2010, tels que la chronologie de la sismicité, l'évolution spatio-temporelle des positions de source de séisme et les changements de vitesse sismique. En effectuant des localisations absolues et relatives, nous obtenons des preuves de l'existence de zones asismiques, concordant avec des études antérieures, que nous interprétons comme des zones plus ductiles. La migration du magma de la partie profonde à la partie superficielle du conduit à travers la zone asismique supérieure est mise en évidence par un déplacement vers le haut des hypocentres. Nous analysons l'énergie sismique quantifiée par le RSAM calculé pour plusieurs bandes de fréquences. Ces fonctions affichent des accélérations claires dans les dernières semaines avant l'éruption. Ce comportement est utilisé pour effectuer des prévisions d'éruption volcanique rétrospective avec la méthode « Material Failure Forecast » ou FFM. Le début de la première éruption est estimé avec une bonne précision. Nous proposons une méthode originale de détection d'événement basée sur un rapport d'énergie. En utilisant cette méthode et la corrélation de la forme d'onde, nous identifions 10 familles de séismes similaires. Ces multiplets sismiques sont situés en dessous ou au -dessus de la zone asismique supérieure et sont composés soit d'événements volcano-tectoniques soit d'événements basse fréquence. Certains de ces groupes ont été actifs pendant plusieurs mois avant la crise éruptive alors qu'une famille qui comprend 119 événements répétitifs est apparue 20 heures avant le début de l'éruption. Nous estimons des variations de vitesse sismique, liées principalement à l'activité magmatique, en utilisant la coda des multiplets et les fonctions d'intercorrélation du bruit sismique. Ces variations montrent une forte variabilité spatiale et temporelle de leur amplitude et de leur signe. Bien qu'elles ne puissent pas être décrites par une simple tendance unique, ces variations de vitesse peuvent être considérées comme un précurseur de l'éruption. En utilisant les résultats précédents ainsi que d'autres observations, nous déterminons les particularités associées à la grande éruption explosive de 2010. En outre, nous proposons un scénario chronologique de l'activité pré- éruptive du Merapi. / The 2010 eruption of Merapi is the first large explosive eruption of the volcano that has been instrumentally observed. In this work, we study the eruption precursors and the pre-eruptive volcano behaviour by linking seismic features with other available observations. The main characteristics of the seismic activity during the 2010 crisis, including the chronology of seismicity, the spatio-temporal evolution of earthquake source positions and the seismic velocity changes, are presented. By performing absolute and relative locations, we obtain evidences of aseismic zones which are consistent with earlier studies and are interpreted as more ductile zones. Magma migration from the deep to the shallow part of the conduit through the upper aseismic zone is revealed by an upward shift of the hypocenters. We analyse the seismic energy quantified by RSAM calculated for several frequency bands. These functions display clear accelerations in the last few weeks before the eruption. This behaviour is used to perform hindsight eruption forecasting with the Material Failure Forecast method (FFM). The onset of the first eruption is estimated with a good precision. We propose an original method of event detection based on energy ratio. Using this method and waveform correlation, we identify 10 families of similar earthquakes. The seismic multiplets are located either below or above the upper aseismic zone and are composed of either volcano-tectonic or low-frequency events. Some of the clusters were active during several months before the eruptive crisis while a family that includes 119 repeating events appeared 20 hours before the eruption onset. Seismic velocity variations associated mainly with magmatic activity are estimated using the coda of both multiplets and noise cross correlation functions. These variations display strong temporal and spatial variability of their amplitude and sign. Although they cannot be described by a unique simple trend, these velocity variations can be considered as an eruption precursor. Using the preceding results together with other observations, we determine the specific features associated with the large explosive eruption of 2010. Furthermore, we propose a chronological scenario of the pre-eruptive activity of Merapi 2010 unrest.