A Heuristic Approach for Optimal Task Allocation for The System Cost Analysis in Distributed Systems

Avanish Kumar, Tariq Ahmad Bhat


The problem of the task allocation in distributed computing system is to need to allocate a number of tasks to different processors for execution. In this paper we have developed a task allocation model and have proposed a heuristic algorithm for task allocation that will find an optimal solution to the problem. The proposed algorithm try to minimize the inter processor communication cost (IPCC) by assigning those task first, which has the heaviest communication link sum (CLS). Using this approach it has been seen that the system cost will minimize more than other heuristic.


Distributed computing systems, Heuristic Approach, Task Allocations, execution costs, Communication costs, communication link sum.


Ajith Tom P. and C. Siva Ram Murthy, An Improved Algorithm For Module Allocation in Distributed Computing Systems, Journal of Parallel and Distributed Computing Systems,” 42 (1997), pp. 82-90.

G. Sagar and A.K. Sarje, Task Allocation Model for Distributed System, Int. J. Systems Sci. Vol. 22, 9(1991). pp. 1671- 1678.

M. Kafil and I. Ahmad, Optimal Task Assignment in Heterogeneous Computing Systems, 0-8186- 7879- 8/97$ 10.00 ©1997 IEEE .

Cheol-Hoon Lee, Dongmyun Lee and Myunghwan Kim, “Optimal Task Assignment in Linear Array Networks, IEEE Transactions on Computers, Vol.41, 7(1997).

Imtiaz Ahmad Muhammad K. Dhodhi and Arif Ghafoor, Task Assignment in Distributed Computing Systems, IEEE Concurrency (1995), pp. 49- 53.

Elsadek A.A. Elsadek & B.E. Wells, A heuristic model for task allocation in heterogeneous distributed computing systems, International Journal of Computers and their Applications, Vol.6, No.1, 1999. Pp. 0-35.

Sol M. Shatz, Jia-Ping Wang and Masanori Goto, Task Allocation For Maximizing Reliability of Distributed Computer Systems, IEEE Transactions on Computers, Vol.41.9 (1992).

S. Kartik and C. Siva Ram Murthy, Task Allocation Algorithms for Maximizing Reliability of Distributed Computing System, IEEE Transactions on computers, Vol.46, 6 (1997).

D.J. Chen et al., A Heuristic Algorithm for the Reliability- Oriented File Assignment in a Distributed Computing System,” Computers Math. Applic. Vol. 29.10(1995), pp. 85- 104,

Peng-Yeng Yin, Shiuh-Sheng Yu, Pei-Pei Wang, Yi-Te Wang, Task Allocation for maximizing Reliability of a Distributed System using Hybrid Particle Swarm Optimization. The Journal of Systems and Software, 80(2007). Pp. 724-735.

Santhanam Srinivasan and Niraj K. Jha, Safety and Reliability Drivan Task Allocation in Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, Vol.10. 3(1999).

D.P. Vidayarthi and A.K. Tripathi, Maximizing reliability of Distributed Computing System with Task allocation using Simple Genetic Algorithm, Journal of System Architecture, 47(2001), pp.549-559.

Pradeep Kumar Yadav, M.P. Singh and Kuldeep Sharma, Task Allocation Model for Reliability and Cost optimization in Distributed Computing System, International Journal of modeling, simulation and scientific computations, vol-2, 2(2011), pp. 1-19.

Qin-Ma Kng, Hong He, Hui- Min Song, Rong Deng, Task allocation for maximizing Reliability of distributed Computing System using Honey bee mating Optimization, The Journal of Systems and software, Vol.83, 2010.

C.C. Shen and W.H. Tasi, A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minimax Criterion, IEEE Transactions on Computers, Vol. C- 34, 3(1985).

H. Kumar et al., A Task Allocation Model for Distributed Data Network, Journal of Mathematical Sciences, Vol.1, 4(2006),pp.379-392.

Lo V.M., Heuristic Algorithms for Task assignment in distributed systems, IEEE Transactions on computers, Vol.37. No. 11, pp. 1384- 1397, November 1988.

K. Kfe, “Heuristic Models of Task Assignment Scheduling in Distributed Systems,” Computer, Vol. 15, pp. 50- 56, June 1982.

W.W. Chu, Leslie J. Holloway, Min-Tsung Lan and Kemal Kfe, Task Allocation in Distributed Data Processing, IEEE Concurrency, November 1980.pp.57-69.

A.K. Sarje and G. Sagar, “Heuristic Model for Task Allocation in Distributed Computer Systems,” IEE Proceedings -E, Vol.138, 5(1991).

P-Y. Richard MA, Edward Y.S. Lee and Masahiro Tsuchiya, “A Task Allocation Model for Distributed Computing Systems,’’ IEEE Transactions on Computers, Vol.C-31, 1(1982), pp.41- 46.

Sung- Ho Woo, Sung- Bang Yang, Shen- Dug Kim and Tack- Don Han, “Task scheduling in distributed computing systems with a genetic algorithm,” 0- 8186- 7901- 8/97 $ 10.000© 1997 IEEE, pp. 301-305.

Hongjun Lu, “load Balanced Task Allocation in locally Distributed Computer Sciences,” Technical report # 633, feb- 1996.

H. Ellis, Sahni S and S. Rajsekaram, “Fundamentals of computers algorithm,” Galgotiya publication Pvt Ltd., (2005).

Peng, Dar- Tezen, Shin, K.G. and Abdel, Zoher, T.F., “Assignment Scheduling Communication periodic Tasks in Distributed Real Time System,” IEEE Transactions on Software Engineering, SE-13, (1997), pp. 745- 757.

DOI: http://dx.doi.org/10.29218/srmsmaths.v1i1.8

Copyright (c) 2017 SRMS Journal of Mathematical Sciences

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.