LIP6 2001/015

• Reports
  Minimisation du volume d'un ordonnancement pour une arborescence avec delais de communications et duplication
• C. Hanen, A. Munier
• 13 pages - 06/11/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
We consider in this paper a scheduling problem given by n tasks of same processing time d, an out-tree, communication delays all equal to c<=d and an integer t. The problem is to find the minimum volume of a feasible schedule with makespan t. Studying the dominance properties of such schedules, we prove that this problem is polynomial using a dynamic programming algorithm.
• Keywords : Scheduling, communication delays, duplication
• Publisher : Valerie.Mangin (at) nulllip6.fr