LIP6 2004/008

• Reports
  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 - 07/13/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
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.
• Keywords : Scheduling, Communication delays, Out-tree, Duplication
• Publisher : Nicole.Nardy (at) nulllip6.fr