Minimizing the volume in scheduling an outtree with communication delays and duplication

C. Hanen, A. Munier

LIP6 2001/015: Rapport de Recherche LIP6 / LIP6 research reports
13 pages - Juin/June 2001 - Document en anglais.

Get it : 160 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Systèmes d'Aide à la Décision et à la Formation

Titre français : Minimisation du volume d'un ordonnancement pour une arborescence avec delais de communications et duplication
Titre anglais : Minimizing the volume in scheduling an outtree with communication delays and duplication

Résumé : Nous considèrons dans ce papier un problème d'ordonnancement définie par n tâches de même durée d, une arborescence, des délais de communication égaux à c<= d et un entier t. Le problème est de construire un ordonnancement de durée inférieure à t et de volume minimum. En étudiant les propriétés de dominance de ces ordonnancements, nous montrons que ce problème est polynomial en utilisant un algorithme de programmation dynamique.

Abstract : 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.

Mots-clés : Ordonnancement, délais de communication, duplication

Key-words : Scheduling, communication delays, duplication

Publications internes LIP6 2001 / LIP6 research reports 2001

Responsable Éditorial / Editor :Valerie.Mangin@lip6.fr