A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minimax Criterion

Chien Chung Shen, Wen-Hsiang Tsai 

Research output: Contribution to journalArticlepeer-review

229 Scopus citations

Abstract

A graph matching approach is proposed in this pa-per for solving the task assignment problem encountered in dis-tributed computing systems. A cost function defined in terms of a single unit, time, is proposed for evaluating the effectiveness of task assignment. This cost function represents the maximum time for a task to complete module execution and communication in all the processors. A new optimization criterion, called the minimax criterion, is also proposed, based on which both minimization of interprocessor communication and balance of processor loading can be achieved. The proposed approach allows various system constraints to be included for consideration. With the proposed cost function and the minimax criterion, optimal task assignment is defined. Graphs are then used to represent the module relationship of a given task and the processor structure of a distrib-uted computing system. Module assignment to system processors is transformed into a type of graph matching, called weak homo-morphism. The search of optimal weak homomorphism cor-responding to optimal task assignment is next formulated as a state-space search problem. It is then solved by the well-known A* algorithm in artificial intelligence After proper heuristic infor-mation for speeding up the search is suggested. An illustrative example and some experimental results are also included to show the effectiveness of the heuristic search.

Original languageEnglish
Pages (from-to)197-203
Number of pages7
JournalIEEE Transactions on Computers
VolumeC-34
Issue number3
DOIs
StatePublished - 1 Jan 1985

Keywords

  • A* algorithm distributed computing systems
  • graph matching
  • interprocessor communication
  • load balancing minimax criterion
  • state-space search
  • weak homomorphism

Fingerprint Dive into the research topics of 'A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minimax Criterion'. Together they form a unique fingerprint.

Cite this