標題: DISTRIBUTED TASK ASSIGNMENT USING CRITICAL PATH ESTIMATE
作者: HSU, CC
LEE, PJ
資訊科學與工程研究所
Institute of Computer Science and Engineering
公開日期: 1-Nov-1993
摘要: A very general task assignment scheme for a distributed computing system is presented in this paper. It takes execution time, communication time, and idle time into consideration. All possible task assignments are formed as a state space tree where a path from the root node of the tree to a node represents a partial or total task assignment. We propose an approach called the critical path overestimate for achieving a suboptimal task assignment and pruning most of the nodes of the tree. Combining the above approach with a divide-and-conquer method, we can further reduce the complexity of the problem, and therefore attain a satisfactory solution. Results from a wide range of experiments reveal that the proposed approaches perform well because of their giving close approximation to the actual cost and saving a high percentage of node generations.
URI: http://hdl.handle.net/11536/2803
ISSN: 0020-0255
期刊: INFORMATION SCIENCES
Volume: 74
Issue: 3
起始頁: 191
結束頁: 212
Appears in Collections:Articles