Algorithmes approchés pour des problèmes d'ordonnancement à temps de communication

A. Munier

LIP6 1997/027: Habilitation à diriger des recherches LIP6 / LIP6 research reports
53 pages - Novembre/November 1997 - French document.

PostScript : 2532 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Systèmes d'Aide à la Décision et à la Formation

Titre français : Algorithmes approchés pour des problèmes d'ordonnancement à temps de communication
Titre anglais : Approximation algorithms for scheduling problems with communication delays

Résumé : L'ordonnancement des tâches sur une architecture distribuée est actuellement un problème critique en raison de l'importance croissante des machines parallèles. Pour mod'eliser correctement les contraintes liées à ces architectures modernes, les délais de communication entre processeurs doivent être pris en compte.
Dans le modèle que nous étudions ici, une contrainte de précédence entre deux tâches i et j exprime le fait que j a besoin du r'esultat de i pour être exécutée. Si ces deux tâches ne sont pas effectuées par le même processseur, il faut alors considérer un d'elai supplémentaire entre leurs date d'exécution pour prendre en compte le temps de transfert des données. Le but est de construire un ordonnancement de durée minimale.
Ces problèmes d'ordonnancement sont en général difficiles. Dans cette thèse, nous exposons quelques idées qui permettent d'obtenir des algorithmes approchés pour les résoudre.
Nous montrons que la programmation linéaire et les algorithmes de liste sont deux outils qui permettent d'obtenir de bonnes solutions approchées pour des instances générales de ce problème. Nous discutons également de l'impact de la duplication pour obtenir de meilleures solutions.

Abstract : With the increasing importance of parallel computing, the question of how to schedule a set of tasks on an architecture becomes critical, and has received much attention. For the results toreflect modern architectures, communication delays between processors must be included in the model.
Precedence relations between two tasks i and j expresses the fact that task j needs output of i to be executed. If these two tasks are not assigned to the same processor, a delay must be considered between the completion of i and the beginning of j to forward the data. The aim is to find a schedule that minimizes the makespan.
These scheduling problems are difficult. This thesis is dedicated to the presentation of some ideas developed to get approximation algorithms to solve them.
We show that linear programming and list scheduling are two efficient tools to get good approximation algorithms for general instances of these problems. We also point that duplication is a powerful way to get easier algorithms and good lower bounds.

Mots-clés : ordonnancement, temps de communication, algorithmes approchés

Key-words : scheduling, communication delays, approximation algorithms

Publications internes LIP6 1997 / LIP6 research reports 1997

Responsable Éditorial / Editor
webmaster@lip6.fr