LIP6 1997/027

• Habilitation à Diriger des Recherches «Algorithmes approchés pour des problèmes d'ordonnancement à temps de communication»
• A. Munier
• 53 pages - 12/11/1997 - document en - http://www.lip6.fr/lip6/reports/1997/lip6.1997.027.ps.tar.gz 2,592 Ko
• Contact Alix.Munier (at) nulllip6.fr
• Ancien Thème : SYSDEF
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.