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.