A close look at task assignment in distributed systems

Author

Ramakrishnan, Sub ; Cho, Il-Hyung ; Dunning, Larry A.

Author_Institution

Dept. of Comput. Sci., Bowling Green State Univ., OH, USA

fYear

1991

fDate

7-11 Apr 1991

Firstpage

806

Abstract

C. C. Shen and W. H. Tsai (IEEE Trans. Comput., vol.C-34, no.3, p.197-203 1985) proposed a graph matching algorithm for solving the static task assignment problem. It combines two important ideas: (1) graph homomorphism and (2) application of the A* algorithm. Task-dependent information is used as a heuristic to reduce the search effort in finding an optimal path to the goal node. An examination is made of Shen and Tsai´s strategy and their complexity measure. The authors propose some simple alternatives to their algorithm that are effective in reducing the number of nodes generated (and expanded) without sacrificing the optimality criteria

Keywords

computational complexity; distributed processing; graph theory; parallel algorithms; A* algorithm; complexity measure; computer networks; distributed systems; graph homomorphism; graph matching algorithm; optimal path; task assignment; Adaptive algorithm; Application software; Communication networks; Computer science; Constraint optimization; Cost function; Delay; Interference; Mathematical programming; Queueing analysis;

fLanguage

English

Publisher

ieee

Conference_Titel

INFOCOM '91. Proceedings. Tenth Annual Joint Conference of the IEEE Computer and Communications Societies. Networking in the 90s., IEEE

Conference_Location

Bal Harbour, FL

Print_ISBN

0-87942-694-2

Type

conf

DOI

10.1109/INFCOM.1991.147588

Filename

147588