A branch-and-bound-with-underestimates algorithm for the task assignment problem with precedence constraint
Resource
Distributed Computing Systems, 1990. Proceedings., 10th International Conference on
Journal
10th International Conference on Distributed Computing Systems
Pages
-
Date Issued
1990-06
Date
1990-06
Author(s)
DOI
N/A
Abstract
The problem of finding an optimal assignment of task modules with a precedence relationship in a distributed computing system is considered. The objective of task assignment is to minimize the task turnaround time. The problem is known to be NP-complete for more than three processors. To solve the problem, a well-known state-space reduction technique, branch-and-bound-with-underestimates, is applied, and two underestimate functions are defined. Through experiments, their effectiveness is shown by comparing the proposed algorithm with both Wang and Tsai's (1988) algorithm and the A* algorithm with h(x)=0.>
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
00089319.pdf
Size
744.59 KB
Format
Adobe PDF
Checksum
(MD5):8ad558abfa420851a589ee00db0b9179