LIP6 2001/015

• Rapports de recherche
  Minimisation du volume d'un ordonnancement pour une arborescence avec delais de communications et duplication
• C. Hanen, A. Munier
• 13 pages - 11/06/2001- document en - http://www.lip6.fr/lip6/reports/2001/lip6.2001.015.pdf - 164 Ko
• Contact : Claire.Hanen (at) nulllip6.fr, Alix.Munier (at) nulllip6.fr
• Ancien Thème : SYSDEF
Nous considèrons dans ce papier un problème d'ordonnancement définie par n tâches de même durée d, une arborescence, des délais de communication égaux à c<= d et un entier t. Le problème est de construire un ordonnancement de durée inférieure à t et de volume minimum. En étudiant les propriétés de dominance de ces ordonnancements, nous montrons que ce problème est polynomial en utilisant un algorithme de programmation dynamique.
• Mots clés : Ordonnancement, délais de communication, duplication
• Directeur de la publication : Valerie.Mangin (at) nulllip6.fr