New Hybrid Algorithm for Task Scheduling in Grid Computing to Decrease missed Task
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.
[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
[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
@article{"International Journal of Information, Control and Computer Sciences:53488", author = "Z. Pooranian and A. Harounabadi and M. Shojafar and N. Hedayat", title = "New Hybrid Algorithm for Task Scheduling in Grid Computing to Decrease missed Task", 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", volume = "5", number = "7", pages = "743-5", }
