A Modified Binary PSO Algorithm for Scheduling Independent Jobs in Grid Computing System

##plugins.themes.academic_pro.article.sidebar##

Published Aug 4, 2021
https://doi.org/10.47164/ijngc.v7i2.211
Download
pdf
Statistic

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...
Volume 7, Issue 2, July 2016

##plugins.themes.academic_pro.article.main##

TARUN KUMAR GHOSH
Department of Computer Science and Engineering, Haldia Institute of Technology, West Bengal, India
Sanjoy Das
Department of Engineering and Technological Studies, Kalyani University, West Bengal

Abstract

Grid computing has been considered as an efficient high performance computing platform to solve large scale and complex computing problems. In computational Grids, the Grid scheduler schedules the submitted jobs and finds the appropriate available resource for each job. Job scheduling which is one of the NP-complete problems has been a focus of many researchers in Grid computing area. This paper presents a modified binary particle swarm optimization (MBPSO) algorithm for efficiently allocating jobs to resources in a Grid system so that makespan and flowtime are minimized. The extensive experimental study shows that our modified binary PSO based scheduler outperforms classical PSO based scheduler and also reveals its efficiency when makespan and flowtime are minimized in varied circumstances.

##plugins.themes.academic_pro.article.details##

How to Cite
GHOSH, T. K. ., & Das, S. . (2021). A Modified Binary PSO Algorithm for Scheduling Independent Jobs in Grid Computing System. International Journal of Next-Generation Computing, 7(2), 144–154. https://doi.org/10.47164/ijngc.v7i2.211
Crossref
Scopus
Google Scholar
Europe PMC

References

  1. Abraham, A., Buyya, R., and Nath, B. 2000. Nature’s heuristics for scheduling jobs on computational grids. In Proceedings of 8th IEEE International Conference on Advanced Computing and Communications, (ADCOM 2000), Tata McGraw-Hill Publishing Co. Ltd, New Delhi, 45-52.
  2. Aggarwal, M., and Kent, R. 2005. Genetic Algorithm Based Scheduler for Computational Grids. In Proceedings of the 19th International Symposium on High Performance Computing Systems and Applications (HPCS ’05).
  3. Ali, S., Siegel, H.J., Maheswaran, M., Hensgen, D., and Ali, S. 2000. Representing Task and Machine Heterogeneities for Heterogeneous Computing Systems. Tamkang Journal of Science and Engineering. 3(3), 195-207.
  4. Braun, T.D., Siegel, H.J., Beck, N., Boloni, L.L., Maheswaran, M., Reuther, A.I., Robertson, J.P., Theys, M.D., and Yao, B. 2001. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. International Journal of Parallel and Distributed Computing, 61(6), 810-837. DOI: https://doi.org/10.1006/jpdc.2000.1714
  5. Eberhart, R.C., Simpson, P.K., and Dobbins, R.W. 1996. Computational Intelligence PC Tools. Academic Press Professional, San Diego.
  6. Foster, C., Kesselman, C., and Tuecke, S. 2001. The anatomy of the Grid. International Journal of Supercomputer Applications, 15(3), 200-222. Gao, Y., Rong, H., and Huang, J.Z. 2005. Adaptive Grid job scheduling with genetic algorithms. Future Generation Computer Systems, Elsevier, 21(1), 151-161. DOI: https://doi.org/10.1016/j.future.2004.09.033
  7. Goswami, R., Ghosh, T. K., and Barman, S. 2011. Local search based approach in Grid scheduling using simulated annealing. In Proceedings of IEEE International Conference on Computer and Communication Technology (ICCCT-2011), Allahabad, India. DOI: https://doi.org/10.1109/ICCCT.2011.6075112
  8. Ibarra, O.H., and Kim, C.E. 1977. Heuristic algorithms for scheduling independent tasks on non-identical processors. Journal of ACM, 24(2), 280-289. DOI: https://doi.org/10.1145/322003.322011
  9. Kennedy, J., and Eberhart, R.C. 1995. Particle swarm optimization. In Proceedings of IEEE International Conference on Neural Networks, 1942-1948.
  10. Kennedy, J., and Eberhart, R.C. 1997. A discrete binary version of the particle swarm algorithm. In Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, Orlando, FL, 5, 4104 - 4108
  11. Liu, H., Abraham, A., and Hassanien, A.E. 2010. Scheduling jobs on computational Grids using a fuzzy particle swarm optimization algorithm. Future Generation Computer Systems, Elsevier, 26(8), 1336-1343. DOI: https://doi.org/10.1016/j.future.2009.05.022
  12. Lorpunmanee, S., Sap, M.N., Abdullah, A.H., and Inwai, C.C. 2007. An Ant Colony Optimization for Dynamic Job Scheduling in Grid Environment. International Journal of Computer Electrical, Automation, Control and Information Engineering, 1(5), 1343-1350.
  13. Macheswaran, M., Ali, S., Siegel, H.J., Hensgen, D., and Freund, R.F. 1999. Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. Journal of Parallel Distributed Computing, 59(2), 107-131. DOI: https://doi.org/10.1006/jpdc.1999.1581
  14. Martino, V.D., and Mililotti, M. 2004. Sub optimal scheduling in a grid using genetic algorithms. Journal of Parallel Computing, 30, 553-565. DOI: https://doi.org/10.1016/j.parco.2003.12.004
  15. McClatchey, R., Anjum A., Stockinger, H., Ali, A., Willers, I., and Thomas, M. 2007. Data intensive and network aware (DIANA) grid scheduling. Journal of Grid Computing, 5, 43-64. DOI: https://doi.org/10.1007/s10723-006-9059-z
  16. Moscato, P. 1989. On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. In CalTech Concurrent Computation Program, California Institute of Technology, USA, Technical Report No. 826.
  17. Page, J., and Naughton, J. 2005. Framework for task scheduling in heterogeneous distributed computing using genetic algorithms. AI Review, 24, 415-429. DOI: https://doi.org/10.1007/s10462-005-9002-x
  18. Prakash, M., Saranya, R., Jothi, K.R., andVigneshwaran, A.2012. An Optimal Job Scheduling in Grid Using Cuckoo Algorithm. International Journal of Computer Science and Telecommunications, 3(2), 65-69.
  19. Rabiee, M., and, Sajedi, H. 2013. Job Scheduling in Grid Computing with Cuckoo Optimization Algorithm. International Journal of Computer Applications, 62(16), 38-44. DOI: https://doi.org/10.5120/10168-5076
  20. Ritchie, G. 2003. Static multi-processor scheduling with ant colony optimization and local search. Master thesis, School of Informatics, Univ. of Edinburgh.
  21. Ritchie, G., and Levine, J. 2003. A fast effective local search for scheduling independent jobs in heterogeneous computing environments. Technical report, Centre for Intelligent Systems and their Applications, University of Edinburgh.
  22. Salman, A., Ahmad, I., and Al-Madani, S. 2002. Particle swarm optimization for task assignment problem. Microprocessors and Microsystems, 26(8), 363-371. DOI: https://doi.org/10.1016/S0141-9331(02)00053-4
  23. Schopf, J.M. 2004. Ten actions when grid scheduling. Grid Resource Management (Book), Springer, 64, Chapter 1. DOI: https://doi.org/10.1007/978-1-4615-0509-9_2
  24. Talbi, E. 2002. A taxonomy of hybrid meta-heuristics. Journal of Heuristics, 8(5), 541-564. DOI: https://doi.org/10.1023/A:1016540724870
  25. Xhafa, F. 2007. A Hybrid Evolutionary Heuristic for Job Scheduling in Computational Grids. Studies in Computational Intelligence, Springer, 75, Chapter 10. DOI: https://doi.org/10.1007/978-3-540-73297-6_11
  26. Xhafa, F., and, Abraham, A. 2010. Computational models and heuristic methods for Grid scheduling problems. Future Generation Computer Systems, Elsevier, 26, 608-621. DOI: https://doi.org/10.1016/j.future.2009.11.005
  27. Xhafa, F., Alba, E., Dorronsoro, B., and Duran, B. 2008. Efficient batch job scheduling in grids using cellular memetic algorithms. Journal of Mathematical Modelling and Algorithms, 7(2), 217-236. DOI: https://doi.org/10.1007/s10852-008-9076-y
  28. Xhafa, F., Duran, B., Abraham, A., and Dahal, K.P. 2008. Tuning struggle strategy in genetic algorithms for scheduling in computational grids. Neural Network World, 18(3), 209-225. DOI: https://doi.org/10.1109/CISIM.2008.54
  29. Yarkhan, A., and, Dongarra, J. 2002. Experiments with scheduling using simulated annealing in a Grid environment. In Proceedings of GRID-2002, 232-242. DOI: https://doi.org/10.1007/3-540-36133-2_21
  30. Zhang, L., Chen, H., Sun, R., Jing, S., and Yang, B. 2008. A Task Scheduling Algorithm Based on PSO for Grid Computing. International Journal of Computational Intelligence Research, 4(1), 37-43. DOI: https://doi.org/10.5019/j.ijcir.2008.123
  31. Zomaya, A.Y., and, Teh, Y.H. 2001. Observations on using genetic algorithms for dynamic load-balancing. IEEE Transactions on Parallel and Distributed Systems, 12(9), 899-911. DOI: https://doi.org/10.1109/71.954620