Optimal assignment of task modules with precedence in distributed computing systems.
Journal
Inf. Sci.
Journal Volume
75
Journal Issue
1-2
Pages
1-34
Date Issued
1993
Author(s)
Yur, Jyh-Shiarn
Abstract
We consider the problem of finding an optimal assignment of task modules with a precedence relationship in a distributed computing system. The objective of task assignment is to minimize the task turnaround time, i.e., the total time required to finish the execution of a task. This 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 experiment, their effectiveness is shown by comparison with both Wang and Tsai's algorithm and the A* algorithm. Parameters considered in the experiment include the number of modules, the number of processors, the ratio of average intermodule communication time to average module execution time, and the shapes of task graphs. Statistical data about the number of search nodes, maximal queue length, and execution time are collected for performance evaluation. © 1993.
Other Subjects
Algorithms; Computer science; Information science; Execution time; Intermodule communication time; Maximal queue length; Optimal assignment; Task graphs; Task modules; Task turnaround time; Distributed computer systems
Type
journal article