A dynamic programming algorithm for minimizing the total duplication cost in scheduling an outtree with communication delays
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
Résumé
This paper introduces an algorithm using the dynamic programming to solve the problem of finding the minimum cost of duplication in scheduling with communication delays and an unbounded number of processors. When duplication is allowed, makespan can be improved but it creates a cost wich can be huge depending on the number and the cost of duplicated tasks. The cost of a duplication in a schedule is the sum of the costs associated to each task (i.e original and duplicates). we assume in this work that the tasks have the same processing time d, that the communication delays are small (all equal to c <= d) and that the precedence graph is an out-tree. We study the problem of finding the minimum cost of a feasible schedule with makespan t.
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
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...