Algorithmes d'approximation pour l'ordonnancement multi-objectif (application aux systèmes parallèles et embarqués)

L'informatique moderne n'est plus uniquement composée de machines personnelles et de super calculateurs. De nombreux supports de calcul sont maintenant disponibles et chacun pose des contraintes particulières amenant à de nombreux objectifs. Ainsi, la notion de performance d'une application est devenue multi-dimensionnelle. Par exemple, ordonnancer optimalement (en temps) une application sur une grille de calcul est inutile si elle ne fournit pas de résultat parce qu'une machine tombe en panne. Fournir une solution à ces problèmes est un défi algorithmique actuel. Dans ce manuscrit, nous étudions l'ordonnancement multi-objectif à l'aide des outils de la théorie de l'approximation. Nous traitons ainsi quatre problèmes. Les deux premiers sont inspirés des systèmes embarqués, tandis que les deux derniers sont inspirés des problématiques que l'on retrouve sur les grilles et les clusters. Le premier problème étudié est l'optimisation des performances d'une application sur une machine disposant de peu de mémoire de stockage. Nous montrons que l'utilisation de l'optimisation multi-objectif permet de fournir une solution et des informations sur le problème que la théorie mono-objectif de l'approximation ne pouvait pas obtenir. Les deux problèmes suivants concernent l'optimisation des performances d'une application lorsque les machines ne sont pas entièrement fiables. Les différents modèles de défaillances amènent à des problèmes d'optimisation radicalement différents. C'est pourquoi le deuxième problème traite de la sûreté de fonctionnement des systèmes embarqués alors que le troisième considère la fiabilité des grilles et clusters. Le dernier problème concerne l'utilisation simultanée d'une plate-forme de calcul parallèle par de nombreux utilisateurs. Nous montrons comment l'utilisation de l'optimisation multi-objectif peut permettre de prendre en compte les besoins utilisateurs au sein du processus d'optimisation.Modern computing systems are no longer composed of personal computers and super computers. Many computing platforms are now available and each one has its own constraints, leading to many different objectives. Thus, the notion of performances becomes multi-dimensional. For instance, scheduling optimally (for time) and application on a computational grid is useless if no results are given when a computer crashes. Solving these problems is a present algorithmical challenge. In this manuscript, we study multi-objective scheduling through the approximation theory. We tackled four problems. The first two ones come from embedded systems while the last two ones are derived from cluster and grid computing. The first studied problem is the optimization of performances of an application running on a machine with low storage capacity. We show that using multi-objective optimization leads to solutions and informations for this problem that could not have been obtained by the classical approximation theory. The two following problems tackled the optimization of the performances of an application when computers are not entirely reliable. Different models can be studied leading to radically different optimization problems. That is why the second problem considers safety in embedded systems while the third one deals with the reliability in computational grids and clusters. The last problem is about scheduling tasks of several users on a parallel computing platform. We show how multi-objective optimization can be used to take the users' needs into account during the scheduling process.GRENOBLE1-BU Sciences (384212103) / SudocTOURS-Polytech'Informat.Product. (372612209) / SudocSudocFranceF