Heuristic task assignment for distributed computing systems
Journal
Information Sciences
Journal Volume
62
Journal Issue
44563
Pages
65-86
Date Issued
1992
Date
1992
Author(s)
Hsu, Chiun-Chieh
Abstract
This paper addresses the problem of assigning a task with precedence constraint to a distributed computing system. The task turnaround time including communication overhead and idle time is adopted to measure the performance of task assignment. The task assignment in this paper requires one to determine not only the assignment of modules, but also the sequence of message transmission to balance processor loads and diminish communication overhead. The search for the optimal task assignment with precedence constraint is known to be NP-complete in the strong sense. A heuristic algorithm with polynomial time complexity is then proposed in order to effectively solve the task assignment problem. The experimental results reveal that the proposed approach is able to obtain a near-optimal or even the optimal task assignment. © 1992.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
05.pdf
Size
1.22 MB
Format
Adobe PDF
Checksum
(MD5):61ebc9ac3e92ec9687df50fe122cb608