Complexity of Master-slave Tasking on Heterogeneous Trees

Overview & Synopsis

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.