HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Complexity of Master-slave Tasking on Heterogeneous Trees

Pierre-François Dutot 1, 2
1 APACHE - Parallel algorithms and load sharing
ID-IMAG - Informatique et Distribution, Inria Grenoble - Rhône-Alpes, UJF - Université Joseph Fourier - Grenoble 1
Abstract : In this paper, we consider the problem of scheduling independent identical tasks on heterogeneous processors and network, where processing times and communications times are different. We assume that communication-computation overlap is possible for every processor, but only allow one send and one receive at a time. In this model, we prove that scheduling on a tree network is NP-hard in the strong sense, reducing the problem to the well-known 3-partition problem.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

Contributor : Pierre-François Dutot Connect in order to contact the contributor
Submitted on : Wednesday, February 1, 2006 - 1:29:10 PM
Last modification on : Friday, February 4, 2022 - 3:08:50 AM
Long-term archiving on: : Saturday, April 3, 2010 - 8:11:50 PM


  • HAL Id : inria-00001076, version 1



Pierre-François Dutot. Complexity of Master-slave Tasking on Heterogeneous Trees. European Journal of Operational Research, Elsevier, 2005, 164 (3), pp.690-695. ⟨inria-00001076⟩



Record views


Files downloads