Scheduling trees with large communication delays on two identical processors

Scheduling trees with large communication delays on two identical processors

0.00 Avg rating0 Votes
Article ID: iaor2008719
Country: United Kingdom
Volume: 8
Issue: 2
Start Page Number: 179
End Page Number: 190
Publication Date: Mar 2005
Journal: Journal of Scheduling
Authors: , , ,
Abstract:

We consider the problem of scheduling trees on two identical processors in order to minimize the makespan. We assume that tasks have unit execution times, and arcs are associated with large identical integer communication delays. We prove that the problem is NP-hard in the strong sense even when restricted to the class of binary trees, and we provide a polynomia1-time algorithm for complete binary trees.

Reviews

Required fields are marked *. Your email address will not be published.