New Hybrid Algorithm for Task Scheduling in Grid Computing to Decrease missed Task

Authors: Z. Pooranian, A. Harounabadi, M. Shojafar, N. Hedayat

Abstract:

The purpose of Grid computing is to utilize computational power of idle resources which are distributed in different areas. Given the grid dynamism and its decentralize resources, there is a need for an efficient scheduler for scheduling applications. Since task scheduling includes in the NP-hard problems various researches have focused on invented algorithms especially the genetic ones. But since genetic is an inherent algorithm which searches the problem space globally and does not have the efficiency required for local searching, therefore, its combination with local searching algorithms can compensate for this shortcomings. The aim of this paper is to combine the genetic algorithm and GELS (GAGELS) as a method to solve scheduling problem by which simultaneously pay attention to two factors of time and number of missed tasks. Results show that the proposed algorithm can decrease makespan while minimizing the number of missed tasks compared with the traditional methods.

Keywords: Grid Computing, Genetic Algorithm, Gravitational Emulation Local Search (GELS), missed task

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332154

References:

[1] Kołodzie. J, Xhafa. F, "Meeting security and user behavior requirements in Grid scheduling ", Simulation Modeling Practice and Theory Vol.19,Iss. 1, pp. 213-226, 2011.DOI: http://dx.doi.org/10.1016/j.simpat.2010.06.007
[2] Tseng. L. Y, Chin. Y. H, Wang. S. C, "The anatomy study of high performance task scheduling algorithm for Grid computing system", Computer Standards & Interfaces Vol. 31, Iss. 4, pp. 713-722, 2009. DOI: http://dx.doi.org/10.1016/j.csi.2008.09.017
[3] M. Shojafar, S. Barzegar, M. R. Meybodi, "A new Method on Resource Scheduling in grid systems based on Hierarchical Stochastic Petri net", First International Conference on Information, Networking and Automation (ICINA 2010), Vol. 9, No 2,pp. V9-175-180, China, 2010. DOI: http://www.irexpert.ir/UploadedFiles/Records/16732_201008142030093 424zmd4dhsos.changeto(pdf)
[4] Shenassa. M. H, Mahmoodi. M, "A novel intelligent method for task scheduling in multiprocessor systems using genetic algorithm", journal of Franklin Institute, Elsevier, Vol.343, Iss. 4-5, pp. 361-371, 2006. DOI: http://dx.doi.org/10.1016/j.jfranklin.2006.02.022
[5] Pourhaji Kazem A. A, Rahmani A. M. and Habibi Aghdam. H, "A Modified Simulated Annealing Algorithm for Static Scheduling in Grid Computing", International Conference on Computer Science and Information Technology 2008 (ICCSIT 2008), Singapore August 29 - September, pp. 623-627, 2008. DOI: http://dx.doi.org/10.1109/ICCSIT.2008.163
[6] Benedict. SH, Vasudevan. V, "Improving scheduling of scientific workflows using tabu search for computational grids", Information Technology Journal Vol.7, No. 1, pp. 91- 97, 2008. DOI: http://scialert.net/abstract/?doi=itj.2008.91.97
[7] Rahmani. A. M, Rezvani. M, "A Novel Genetic Algorithm for Static Task Scheduling in Distributed Systems", International Journal of Computer Theory and Engineering, Vol. 1, No. 1, pp. 1793- 8201, April 2009. DOI: http://www.etlibrary.org/?m=fbook&a=down&aid=10
[8] Abdulal. W, Jadaan. O. A, Jabas. A, Ramachandram. S, "An Improved Rank-based Genetic Algorithm with Limited Iterations for Grid Scheduling", IEEE Symposium on Industrial Electronics and Applications, pp. 215-220, October 2009. DOI: http://10.1109/ISIEA.2009.5356468
[9] Tamilarasi. A, Anantha kumar. T, "An enhanced genetic algorithm with simulated annealing for job-shop scheduling", International Journal of Engineering, Science and Technology, Vol. 2, No. 1, pp. 144- 151, 2010. DOI: http://www.doaj.org/doaj?func=openurl&genre=article&issn=21412820 &date=2010&volume=2&issue=1&spage=144
[10] Omaraa. F. A, Arafa. M. M," Genetic algorithms for task scheduling problem", Journal Parallel Distributed Computing, Vol. 70, Iss. 1, pp. 13-22, 2010.DOI: http://dx.doi.org/10.1016/j.jpdc.2009.09.009
[11] Khanli. L. M, Etminan Far, Ghaffari. A, "Reliable Job Scheduler using RFOH in Grid Computing", Journal of Emerging Trends in Computing and Information Sciences, Vol. 1, No. 1, pp. 43- 47, July 2010. DOI: DOI: http://www.doaj.org/doaj?func=openurl&genre=article&issn=20798407 &date=2010&volume=1&issue=1&spage=43
[12] Tao. Q, Chang. H, Yi. Y, Gu. CH,"A Grid Workflow Scheduling Optimization Approach for e-Business Application", International Conference on E-Business and E-Government, pp. 168- 171, 2010. DOI: http://dx.doi.org/10.1109/ICEE.2010.50
[13] Gharooni fard. G, Moein darbari. F, Deldari. H, Morvaridi. A, "Scheduling of scientific workflows using a chaos- genetic algorithm", International Conference on Computational Science ICCS, pp. 1439- 1448, 2010. DOI: http://dx.doi.org/10.1016/j.procs.2010.04.160
[14] Lifeng Ai and Maolin Tang, "QoS-Based Web Service Composition Accommodating Inter-Service Dependencies Using Minimal-Conflict Hill-Climbing Repair Genetic Algorithm", Fourth IEEE International Conference on Science, pp. 119- 126, 2008.DOI: http://dx.doi.org/10.1109/eScience.2008.110
[15] Barzegar. B, Rahmani. A. M, Zamani far. K, "Gravitational Emulation Local Search Algorithm for Advanced Reservation and Scheduling in Grid Systems", First Asian Himalayas International Conference on (2009), pp. 1-5, 2009. DOI: http://dx.doi.org/10.1109/AHICI.2009.5340301
[16] Braun. T. D, Siegel. H. J,Beck. N, Boloni. L. L, Maheswaran. M, Reuther. A. L, Robertson. J. P, Theys. M. D, Yao. B, Hensgen. D, Freund. R. F,"A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems", Journal of Parallel and distributed Computing Vol. 61, No. 6, pp. 680- 1983, 2001.DOI: http://dx.doi.org/10.1006/jpdc.2000.1714
[17] Holland. J, "Adaptation in Natural and Artificial Systems", University of Michigan Press, Ann Arbor, ISBN: 0-262-58111-6, pp. 228, 1975.DOI: http://www.amazon.com/Adaptation-Natural-Artificial-Systems- Introductory/dp/0262581116
[18] Goldberg. D.E, "Genetic Algorithms in Search, Optimization and Machine Learning", Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, ISBN: 0201157675, pp. 432, 1989. DOI: http://www.amazon.com/Genetic-Algorithms-Optimization-Machine- Learning/dp/0201157675
[19] Voudouris, chris, Edward Tsang, Guided Local Search. Technical Report CSM-247, Department of Computer Science, University of Essex, UK, August 1995.
[20] Barry Lynn Webster, "Solving Combinatorial Optimization Problems Using a New Algorithm Based on Gravitational Attraction", Ph.D. Thesis, Florida Institute of Technology Melbourne, FL, USA, May 2004.DOI: http://dx.doi.org/10.1109/T-C.1973.223690
[21] Raja Balachandar. S, Kannan. K, "Randomized gravitational emulation search algorithm for symmetric traveling salesman problem", Applied Mathematics and Computation, Vol. 192, Iss. 2, pp. 413-421, 2007.DOI: http://dx.doi.org/10.1016/j.amc.2007.03.019