International Journal of Information Technology and Computer Science (IJITCS)
IJITCS Vol. 5, No. 10, 8 Sep. 2013
Cover page and Table of Contents: PDF (size: 348KB)
A Modified Parallel Heuristic Graph Matching Approach for Solving Task Assignment Problem in Distributed Processor System
Full Text (PDF, 348KB), PP.78-84
Views: 0 Downloads: 0
Author(s)
R Mohan
1,*
N P Gopalan
2
Index Terms
Task Assignment Problem, Heuristic Algorithm, Graph Matching Algorithm, Distributed Systems
Abstract
Task assignment is one of the most fundamental combinatorial optimization problems. Solving the Task Assignment Problem is very important for many real time and computational scenarios where a lot of small tasks need to be solved by multiple processors simultaneously. In this paper a Heuristic and Parallel Algorithm for Task Assignment Problem is proposed. Results obtained for certain cases are presented and compared with the optimal solutions obtained by already available algorithms. It is observed that the proposed algorithm works much faster and efficient than the existing algorithms .The paper also demonstrates how the proposed algorithm could be extended to multiple distributed processors.
Cite This Paper
R Mohan, N P Gopalan, "A Modified Parallel Heuristic Graph Matching Approach for Solving Task Assignment Problem in Distributed Processor System", International Journal of Information Technology and Computer Science(IJITCS), vol.5, no.10, pp.78-84, 2013. DOI:10.5815/ijitcs.2013.10.08
Reference
[1]W.-H. Chen, C.-S. Lin, A hybrid heuristic to solve a task allocation problem, Comput. Oper. Res. 27 (3) (2000) 287–303.
[2]K.Efe, Heuristic models of task assignment scheduling in distributed systems, IEEE Comput. 15 (6) (1982) 50–56.
[3]H. El-Rewini, T.G. Lewis, H.H. Ali, Task Scheduling in Parallel and Distributed Systems, Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1994.
[4]A. Giersch, Y. Robert, F. Vivien, Scheduling tasks sharing files on heterogeneous master-slave platforms, PDP’2004, 12th Euromicro Workshop on Parallel Distributed and Network-based Processing, IEEE Computer Society Press, Silver Spring, MD, 2004.
[5]Y.Hamam, K.S. Hindi, Assignment of programmodules to Processors: A simulated annealing approach, European J. Oper. Res.122 (2) (2000)
[6]Chien-chung shen and Wen-hsiang tsai, “A Graph Matching Approach to Optimal task assignment in Distributed computing systems using a Minimax Criterion”, IEEE Transactions on Computers, vol. C- 34,No.3, March 1985.
[7]R.Mohan, N P Gopalan, and et.al, “Parallel Heuristic graph Matching Algorithm for Task Assignment Problem in Distributed Computing Systems”, IEEE International Conference on Computer & Information Science (ICCIS 2012), 12-14 June 2012, pp 575-579.
[8]Cormen, Leiserson, Rivest, Stein, “A star Algorithm, Introduction To Algorithms” edition 2001.
[9]R.Mohan, Amitava Gupta, “A Parallel Task Assignment using Heuristic graph Matching”, First International Conference (PDTCTA 2011), Tirunelveli, Tamilnadu, india Sep2011, Springer LNCS CCIS Proceedings, pp. 334-343.
[10]P.Sadayappan, F.Ercal and J.Ramanujam, Cluster Partitioningapproach to mapping parallel program onto a hypercube, Parallel Computing, 13(1990), pp. 1-16.
[11]S. Salcedo-Sanz, Y. Xu, X. Yao, “Hybrid meta-heuristics algorithms for task assignment in heterogeneous computing systems”, An article from: Computers and Operations Research.