Task assignment with precedence relations in distributed computing systems
Journal
Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Journal Volume
13
Journal Issue
2
Pages
177-187
Date Issued
1990
Author(s)
Abstract
This paper addresses the problem of assigning a task with precedence constraints to a distributed computing system. A cost function considering communication overhead and idle time is adopted to measure the performance of the task assignment. The task assignment in this paper determines not only the assignment of modules but also the sequence of messages transmission to balance processor loading and diminish communication overhead. The search for the optimal task assignment with precedence constraints is known to be NP-complete [7] in the strong sense. A heuristic algorithm with polynomial time complexity is 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. © 1990 Taylor & Francis Group, LLC.
Subjects
Distributed computing system; Heuristic algorithm; Task assignment
Type
journal article