Adaptation d'un algorithme optimal d'ordonnancement en régime permanent pour des lots bornés

International audienceLe contexte de cet article est l ordonnancement de lots bornes de travaux identiques sur une plate-forme d execution heterogene comme la grille. Les travaux executes sont des graphes de t?ches orientes et sans cycle (DAG), en forme d anti-arbre. Les t?ches sont de plusieurs types et les n{oe}uds de la plate-forme ne sont pas toujours en mesure d executer tous les types de t?ches. Le probleme de minimisation du temps d execution d un lot est un probleme NP-Complet. Sous l angle du regime permanent, il est possible de decrire le probleme sous la forme d un programme lineaire donnant une solution optimale pour l ordonnancement cyclique de lots infinis. Lorsque les lots sont bornes, les resultats restent bons bien que sous optimaux. Nous montrons ici que les phases d initialisation et de terminaison ajoutent un sur-co?t qui penalise le temps global d execution. Nous montrons ensuite le lien entre la taille de ces phases et la taille de la periode de l ordonnancement cyclique et donnons un algorithme permettant le calcul de la periode minimale. Des experimentations, obtenues par simulations avec SimGrid, illustrent en fin d article le gain apporte par le choix d une periode minimal