Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Off-line and on-line scheduling on heterogeneous master-slave platforms

Jean-François Pineau 1, 2 Yves Robert 1, 2 Frédéric Vivien 1, 2 
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this work, we deal with the problem of scheduling independent tasks on heterogeneous master-slave platforms. We target both off-line and on-line problems, with several objective functions (makespan, maximum response time, total completion time). On the theoretical side, our results are two-fold: (i) For off-line scheduling, we prove several optimality results for problems with release dates; (ii) For on-line scheduling, we establish lower bounds on the competitive ratio of any deterministic algorithm. On the practical side, we have implemented several heuristics, some classical and some new ones derived in this paper. We studied experimentally these heuristics on a small but fully heterogeneous MPI platform. Our results show the superiority of those heuristics which fully take into account the relative capacity of the communication links.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:18:36 PM
Last modification on : Wednesday, October 26, 2022 - 8:14:35 AM


  • HAL Id : inria-00070373, version 1


Jean-François Pineau, Yves Robert, Frédéric Vivien. Off-line and on-line scheduling on heterogeneous master-slave platforms. [Research Report] RR-5634, LIP RR-2005-31, INRIA, LIP. 2005, pp.23. ⟨inria-00070373⟩



Record views


Files downloads