# On the Complexity of Multi-Round Divisible Load Scheduling

6 MESCAL - Middleware efficiently scalable
ID-IMAG - Informatique et Distribution, Inria Grenoble - Rhône-Alpes
Abstract : In this paper we study master-worker scheduling of divisible loads in heterogeneous distributed systems. Divisible loads are computations that can be arbitrarily divided into independent chunks'', which can then be processed in parallel. In multi-round scheduling load is sent to each worker as several chunks rather than as a single one. Solving the divisible load scheduling (DLS) problem entails determining the subset of workers that should be used, the sequence of communication to these workers, and the sizes of each load chunk. We first state and establish an optimality principle in the general case. Then we establish a new complexity result by showing that a DLS problem, whose complexity has been open for a long time, is in fact NP-hard, even in the one-round case. We also show that this problem is pseudopolynomially solvable under certain special conditions. Finally, we present a deep survey on algorithms and heuristics for solving the multi-round DLS problem.
Keywords :
Type de document :
Rapport
[Research Report] RR-6096, INRIA. 2007, pp.23
Domaine :

https://hal.inria.fr/inria-00123711
Contributeur : Rapport de Recherche Inria <>
Soumis le : jeudi 11 janvier 2007 - 13:31:10
Dernière modification le : jeudi 11 janvier 2018 - 06:20:05
Document(s) archivé(s) le : mardi 21 septembre 2010 - 11:56:21

### Fichiers

RR-6096.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00123711, version 2

### Citation

Yang Yang, Henri Casanova, Maciej Drozdowski, Marcin Lawenda, Arnaud Legrand. On the Complexity of Multi-Round Divisible Load Scheduling. [Research Report] RR-6096, INRIA. 2007, pp.23. 〈inria-00123711v2〉

### Métriques

Consultations de la notice

## 546

Téléchargements de fichiers