Optimisation du placement de tâches dans les systèmes distribués et de l'allocation de ressources pour les communications multipoints
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
Combinatorial optimization problems consist in finding an optimal solution among a great number of feasible solutions. This kind of problems arise in many fields. In this thesis, we have studied optimization problems occuring in distributed systems and telecommunication networks. The problems we have considered are NP-complete, so there might not exist polynomial time algorithms to solve them optimally. We have, on the one hand, explored theoritical aspects of the problems: we studied some variants that can be solved either optimally or approximately with polynomial time algorithms. On the other hand, we looked at the practical side and proposed efficient heuristics. We first looked at a task assignment problem. For a given application, we seek to assign its tasks among different processors of a parallel architecture so as to minimize its overall completion time. We have proposed polynomial time approximation schemes to solve variants of the problem. Moreover, we have described many new heuristics to solve the general problem and we have provided methods to calculate lower bounds. The second problem we looked at arises in the field of telecommunications. It is a resources allocation problem in a multipoint communications setting. This problem, relatively recent, arised from the necessity of managing new applications for instance video-conference, group communication or network games. We have studied two problems. The first deals with network design (synthesis) under least cost and multipoint communications demand satisfaction. In the second, we seek to maximize the number of simultaneous multipoint communications in a network with fixed link capacities.
Abstract FR:
Les problèmes d'optimisation combinatoire consistent à déterminer une solution optimale parmi un ensemble généralement très grand de solutions possibles. Ce type de problèmes se pose de manière cruciale dans de très nombreux domaines. Dans notre thèse, nous avons étudié des problèmes d'optimisation issus des systèmes distribués et des réseaux de télécommunications. Comme les problèmes considérés sont NP-difficiles, il est très peu probable qu'ils puissent être résolus de manière optimale à l'aide d'un algorithme polynomial. Nous avons exploré d'un côté les aspects théoriques, en déterminant les variantes admettant des algorithmes polynomiaux pour les résoudre soit de manière exacte soit de manière approchée, et les aspects pratiques en développant des heuristiques efficaces. Nous avons d'abord étudié un problème de placement de tâches - de type min/max -dont l'objectif est de placer les tâches composant une application sur les différents processeurs d'une architecture parallèle de façon à minimiser le temps total d'exécution de l'application. Nous avons proposé des schémas d'approximation polynomiaux pour résoudre certaines variantes. Nous avons aussi présenté plusieurs heuristiques nouvelles pour résoudre le problème général ainsi que des méthodes de calcul de bornes inférieures. Le deuxième problème considéré est issu du domaine des télécommunications. Il s'agit d'un problème d'allocation de ressources pour des communications multipoints. Cette problématique, relativement récente, est née de la nécessité d'exploiter au mieux les nouvelles applications telles la visioconférence, le travail de groupe, ou les jeux en réseau par exemple. Nous avons étudié deux problèmes.