LIP6 2004/008

• Rapports de recherche
  Un algorithme de programmation dynamique pour la minimisation du coût total de duplication dans un ordonnancement d’une arborescence avec délais de communication
• C. Hanen, D. Tayachi
• 12 pages - 13/07/2004- document en - http://www.lip6.fr/lip6/reports/2004/lip6.2004.008.pdf - 177 Ko
• Contact : Claire.Hanen (at) nulllip6.fr, Dalila.Tayachi (at) nulllip6.fr
• Ancien Thème : SYSDEF
Nous présentons dans cet article un algorithme basé sur la programmation dynamique qui minimise le coût total de duplication des tâches d’un ordonnancement dans le cas de délais de communication et d’un nombre infini de processeurs. La duplication permet de diminuer la durée de l’ordonnancement mais elle crée un coût de duplication qui peut être important selon le nombre et le coût de tâches dupliquées. On définit le coût de duplication dans un ordonnancement comme étant la somme des coûts des tâches (originales et dupliquées). Nous considérons que les tâches ont la même durée d et que nous sommes dans le cas de petits délais de communication (c <= d), et que le graphe de précédence est une arborescence. Nous étudions le problème de détermination du coût minimal de duplication des tâches d’un ordonnancement réalisable de makespan t
• Mots clés : Ordonnancement, Délais de communication, Arborescence, Duplication
• Directeur de la publication : Nicole.Nardy (at) nulllip6.fr