Optimal Task Assignment in Distributed Systems through Greedy algorithm

Authors

  • Kapil Govil  Department of Computer Science & Applications, ITM University, Gwalior, Madhya Pradesh, India
  • Arun Kumar Yadav  Department of Computer Science & Applications, ITM University, Gwalior, Madhya Pradesh, India
  • Harihar Nath Verma  Department of Computer Science & Applications, ITM University, Gwalior, Madhya Pradesh, India

DOI:

https://doi.org/10.32628/CSEIT2063106

Keywords:

Distributed Processing Environment, Performance Enhancement, Greedy algorithm, Allocation

Abstract

A distributed processing environment consists of one or more applications spread over several computers. These computers may be geographically separated from one another. The applications may be executed on different platforms using different operating systems and telecommunication protocols. In short, a distributed operating environment offers a variety of information system solutions regardless of the location of the user, user’s operating system or the equipment using by user. Performance enhancement of the distributed networks is a major and challenging problem for the researchers. In this paper, algorithm designed, have to allocate m tasks to n processors (m>n) in the environment of distributed processing. These m tasks are to be assigned on the n processors of system through Greedy algorithm of task scheduling. The starting time and finishing time of the processing of a task is considered and denoted by Si and Fi where i= 1, 2, 3, 4, 5…… m. In order to evaluate the optimal time, present algorithm obtains the set of assigned and on assigned tasks. Based on these sets allocation has been made. The method is presented into algorithmic form and several sets of input data have been implemented to test the effectiveness of the algorithm.

References

  1. M. M. Kovalev and D. M.Vasilkov. 1995. The canonical order and greedy algorithms. European Journal of Operational Research. (1995), Vol. 80. No. 2. pp. 446 – 450.
  2. A. Kumar, M. P. Singh and P. K. Yadav. 1995. A Fast Algorithm for Allocating Tasks in Distributed Processing System. In proceedings of the 30th Annual Convention of CSI, Hyderabad. (1995). pp. 347 – 358.
  3. Nitin Upadhyay, “The Design & Analysis of Algorithms”, Katson Books, India, 2004.
  4. R. Y. Richard, E. Y. S. Lee and M. Tsuchiya. 1982. A Task Allocation Model for Distributed Computer System. IEEE Transactions on Computer. (1982), Vol. 31. pp. 41 – 47.
  5. T. F. Abelzaher and K. G. Shin. 1995. Optimal combined task and message scheduling in distributed real – time systems. IEEE Real – Time Systems Symposium. (1995), Vol. 16. pp. 162.
  6. Andrew S. Tanenbaum, “Computer Networks”, Prentice Hall of India, India, 2001.
  7. D. F. Baca. 1989. Allocation modules to Processor in a distributed system. IEEE Transactions on Software Engineering. (1989), Vol. 15. pp. 1427 – 1436.
  8. T. L. Casavent and J. G. Kuhl. 1988. A. Taxonomy of Scheduling in General Purpose Distributed Computing System. IEEE Transactions on Software Engineering. (1988), Vol. 14. pp. 141 – 154.
  9. A. Farinelli, L. Iocchi, D. Nardi and V. A. Ziparo. 2005. Task Assignment with dynamic perception and constrained tasks in a Multi-Robot System. Proc. of International Conference on Robotics and Automation (ICRA'05). (2005).
  10. A. Y. Hamed. 2012. Task Allocation for Maximizing Reliability of Distributed Computing Systems Using Genetic Algorithms. International Journal of Computer Networks and Wireless Communications. (2012), Vol. 2. No. 5. pp. 560 – 569.
  11. Bassel Arafeh, Khalid Day and Abderezak Touzene. 2008. A multilevel partitioning approach for efficient tasks allocation in heterogeneous distributed systems. Journal of Systems Architecture: The EUROMICRO Journal. (2008), Vol. 54. No. 5. pp. 530 – 548.
  12. Faizul Navi Khan and Kapil Govil. 2014. A tricky task scheduling technique to optimize time cost and reliability in mobile computing environment. International Journal of Research in Engineering and Technology. (2014), Vol. 3. No. 5. pp. 823 – 829.
  13. Faizul Navi Khan and Kapil Govil. 2014. A Static approach to optimize time cost and reliability in Distributed Processing Environment. International Journal of Scientific & Engineering Research. (2014), Vol. 5. No. 5. pp. 1016 – 1021.
  14. Faizul Navi Khan and Kapil Govil. 2013. Cost Optimization Technique of Task Allocation in Heterogeneous Distributed Computing System. International Journal Advanced Networking and Applications. (2013), Vol. 5, No.3. pp. 1913 – 1916.
  15. Faizul Navi Khan, Kapil Govil. 2013. Static Approach for Efficient Task Allocation in Distributed Environment. International Journal of Computer Applications. (2013), Vol. 81. No. 15. pp. 19 – 22.
  16. Geir Horn, B. John Oommen. 2010. Solving multi constraint assignment problems using learning automata. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics. (2010), Vol. 40. No.1. pp. 6 – 18.
  17. Harendra Kumar, M. P. Singh, P. K. Yadav. 2013. Optimal Tasks Assignment for Multiple Heterogeneous Processors with Dynamic Re – assignment. International Journal of Computers & Technology. (2013), Vol. 4. No. 2. pp. 528 – 535.
  18. Kapil Govil. 2011. A Smart Algorithm for Dynamic Task Allocation for Distributed Processing Environment. International Journal of Computer Applications. (2011), Vol. 28. No. 2. pp. 13 – 19.
  19. M. P. Singh, P. K. Yadav, H. Kumar and B. Agarwal. 2012. Dynamic Tasks Scheduling Model for Performance Evaluation of a Distributed Computing System through Artificial Neural Network. Proceedings of the International Conference on Soft Computing for Problem Solving (SocProS 2011) (Advances in Intelligent and Soft Computing: Published by Springer). (2012), Vol. 130. pp. 321 – 331.
  20. Manisha Sharma, Harendra Kumar and Deepak Garg. 2012. An Optimal Task Allocation Model through Clustering with Inter –Processor Distances in Heterogeneous Distributed Computing Systems. International Journal of Soft Computing and Engineering. (2012), Vol. 2. No. 1. pp. 50 – 55.
  21. Monika Choudhary and Sateesh Kumar Peddoju. 2012. A Dynamic Optimization Algorithm for Task Scheduling in Cloud Environment. International Journal of Engineering Research and Applications (IJERA). (2012), Vol. 2. No. 3. pp. 2564 – 2568.
  22. N. Beaumont. 2009. Using dynamic programming to determine an optimal strategy in a contract bridge tournament. Journal of the Operational Research Society. (2009), Vol. 61. No. 5. pp. 732 – 739.
  23. Palmer, J. and Mitrani I. 2005. Optimal and heuristic policies for dynamic server allocation. Journal of Parallel and Distributed Computing. (2005), Vol. 65. No. 10. pp. 1204 – 1211.
  24. Pradeep Kumar Yadav, M. P. Singh and Harendra Kumar. 2008. Scheduling Algorithm: Tasks Scheduling Algorithm for Multiple Processors with Dynamic Reassignment. Journal of Computer Systems, Networks, and Communications. (2008), pp. 1 – 9.
  25. Sagar Dhakal, Majeed M. Hayat, Jorge E. Pezoa, Cundong Yang and David A. Bader. 2007. Dynamic Load Balancing in Distributed Systems in the Presence of Delays: A Regeneration-Theory Approach. IEEE Transactions on Parallel and Distributed Systems. (2007), Vol. 18. No. 4. pp. 485 – 497.
  26. Shen Chenglin and Zhang Xinxin. 2009. Dynamic Mechanisms of Task – assignment for Virtual Enterprises Based on Multi-agent Theory. Proceedings of the 2009 International Symposium on Web Information Systems and Applications (WISA’09). (2009), pp. 525 – 528.
  27. Sunita Bansal, Bhavik Kothari and Chittaranjan Hota. 2011. Dynamic Task-Scheduling in Grid Computing using Prioritized Round Robin Algorithm. IJCSI International Journal of Computer Science Issues. (2011), Vol. 8. No. 2. pp. 472 – 477.
  28. V. Pilloni, P. Navaratnam, S. Vural, L. Atzori and R. Tafazolli. 2014. TAN: A Distributed Algorithm for Dynamic Task Assignment in WSNs. Sensors Journal, IEEE. (2014), Vol. 14. No. 4. pp. 1266 – 1279.
  29. Xiangzhen Konga, Chuang Lina, Yixin Jianga, Wei Yana and Xiaowen Chub. 2011. Efficient dynamic task scheduling in virtualized data centers with fuzzy prediction. Journal of Network and Computer Applications. (2011), Vol. 34. No. 4. pp. 1068 – 1077.
  30. Yishuang Hu, Yi Ding, Fan Wen and Lei Liu. 2019. Reliability Assessment in Distributed Multi-State Series-Parallel Systems. Energy Procedia. (Feb 2019), Vol. 159. pp. 104 – 110.
  31. Amit Kumar Srivastava and Shishir Kumar. 2018. Dynamic Reconfiguration of robot software component in real time distributed system using clustering techniques. Procedia Computer Science. (2018), Vol. 125. pp. 754 – 761.
  32. Mohammed I. Alghamdi, Xunfei Jiang, Ji Zhang, Jifu Zhang and Xiao Qin. 2017. Towards two – phase scheduling of real-time applications in distributed systems, Journal of Network and Computer Applications. (Apr 2017), Vol. 84. pp. 109 – 117.
  33. Vikash Mishra and Vikram Singh. 2015. Generating Optimal Query Plans for Distributed Query Processing using Teacher – Learner Based Optimization. Procedia Computer Science. (2015), Vol. 54. pp. 281 – 290.
  34. Qingchao Jiang and Biao Huang. 2016. Distributed monitoring for large – scale processes based on multivariate statistical analysis and Bayesian method. Journal of Process Control. (Oct 2016), Vol. 46. pp. 75 – 83.

IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology

Downloads

Published

2020-06-30

Issue

Volume 6, Issue 3, May-June-2020

Section

Research Articles

License

Copyright (c) IJSRCSEIT

Creative Commons License

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

How to Cite

[1]
Kapil Govil, Arun Kumar Yadav, Harihar Nath Verma, " Optimal Task Assignment in Distributed Systems through Greedy algorithm" International Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), ISSN : 2456-3307, Volume 6, Issue 3, pp.416-427, May-June-2020. Available at doi : https://doi.org/10.32628/CSEIT2063106