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

https://hal.inria.fr/inria-00001076
Contributor : Pierre-François Dutot <>
Submitted on : Wednesday, February 1, 2006 - 1:29:10 PM
Last modification on : Tuesday, February 9, 2021 - 3:22:08 PM
Long-term archiving on: : Saturday, April 3, 2010 - 8:11:50 PM

Identifiers

  • HAL Id : inria-00001076, version 1

Collections

INRIA | IMAG | CNRS | UGA

Citation

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⟩

Share

Metrics

Record views

310

Files downloads

481