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.