A Modified Parallel Heuristic Graph Matching Approach for Solving Task Assignment Problem in Distributed Processor System
Автор: R Mohan, N P Gopalan
Журнал: International Journal of Information Technology and Computer Science(IJITCS) @ijitcs
Статья в выпуске: 10 Vol. 5, 2013 года.
Бесплатный доступ
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.
Task Assignment Problem, Heuristic Algorithm, Graph Matching Algorithm, Distributed Systems
Короткий адрес: https://sciup.org/15011980
IDR: 15011980
Список литературы A Modified Parallel Heuristic Graph Matching Approach for Solving Task Assignment Problem in Distributed Processor System
- W.-H. Chen, C.-S. Lin, A hybrid heuristic to solve a task allocation problem, Comput. Oper. Res. 27 (3) (2000) 287–303.
- K.Efe, Heuristic models of task assignment scheduling in distributed systems, IEEE Comput. 15 (6) (1982) 50–56.
- H. El-Rewini, T.G. Lewis, H.H. Ali, Task Scheduling in Parallel and Distributed Systems, Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1994.
- 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.
- Y.Hamam, K.S. Hindi, Assignment of programmodules to Processors: A simulated annealing approach, European J. Oper. Res.122 (2) (2000)
- 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.
- 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.
- Cormen, Leiserson, Rivest, Stein, “A star Algorithm, Introduction To Algorithms” edition 2001.
- 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.
- P.Sadayappan, F.Ercal and J.Ramanujam, Cluster Partitioningapproach to mapping parallel program onto a hypercube, Parallel Computing, 13(1990), pp. 1-16.
- 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.
