A close look at task assignment in distributed systems

1 January 1991

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

Vol. se 7, 806-812 vol.2
https://doi.org/10.1109/infcom.1991.147588

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

This publication has 12 references indexed in Scilit:

Heuristic algorithms for task assignment in distributed systems
IEEE Transactions on Computers, 1988
A taxonomy of scheduling in general-purpose distributed computing systems
IEEE Transactions on Software Engineering, 1988
Adaptive load sharing in homogeneous distributed systems
IEEE Transactions on Software Engineering, 1986
Studies in Semi-Admissible Heuristics
IEEE Transactions on Pattern Analysis and Machine Intelligence, 1982
Load Balancing in Distributed Systems
IEEE Transactions on Software Engineering, 1982
Heuristic Models of Task Assignment Scheduling in Distributed Systems
Computer, 1982
A Task Allocation Model for Distributed Computing Systems
IEEE Transactions on Computers, 1982
A Shortest Tree Algorithm for Optimal Assignments Across Space and Time in a Distributed Processor System
IEEE Transactions on Software Engineering, 1981
Task Allocation in Distributed Data Processing
Computer, 1980
Dual Processor Scheduling with Dynamic Reassignment
IEEE Transactions on Software Engineering, 1979