Un algorithme d'ordonnancement asymptotiquement optimal pour le problème cyclique multidimensionnel

P. Le Gouëslier d'Argence

IBP-Litp 1994/52: Rapport de Recherche Litp / Litp research reports
21 pages - Décembre/December 1994 - French document.

PostScript : Ko /Kb

Titre / Title: Un algorithme d'ordonnancement asymptotiquement optimal pour le problème cyclique multidimensionnel

Résumé : Nous présentons le problème d'ordonnancement d'un ensemble de tâches, liées par des contraintes de précédences uniformes, et exécutées sur un domaine d'itération multidimensionnel et semi infini. Nous proposons un algorithme basé sur la programmation linéaire, qui fournit un ordonnancement affine par morceaux dont les performances sont asymptotiquement aussi bonnes que celles de l'ordonnancement au plus tôt.

Abstract : We present the problem of scheduling a tasks set, with uniform dependencies, on a multidimensionnal and semi infinite iteration domain. We propose an algorithm based on linear programming which provides a piecewise affine scheduling which is asymptotically as best as the earliest schedule.

Publications internes Litp 1994 / Litp research reports 1994