Task Assignment in Distributed Computing Systems
Journal
Interntional Journal of Systems Science
Journal Volume
21
Journal Issue
12
Pages
2425-2440
Date Issued
1991-01
Date
1991-01
Author(s)
Kuo, Te-Son
Abstract
The problem is addressed of assigning a task with a precedence constraint to a distributed computing system. Task turnaround time with regard to communication overhead and idle time is adopted to measure the performance of task assignment. The assignment of the module is determined as is the sequence of message transmission to balance the processor load and reduce communication overhead. The search for the optimal task assignment with a precedence constraint is known to be NP-complete (Garey et al. 1979) in the strong sense. A heuristic algorithm with polynomial time complexity is then proposed in order to solve the task-assignment problem effectively. Experimental results show that the proposed approach produces a near-optimal or even optimal task assignment. © 1990 Taylor & Francis Group, LLC.
Other Subjects
Combinatorial optimization; Heuristic algorithms; Optimization; Polynomial approximation; Communication overheads; Distributed computing systems; Message transmissions; Near-optimal; Polynomial time complexity; Precedence constraints; Processor loads; Task assignment; Distributed computer systems
Type
journal article