nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.10.2015

An efficient meta-heuristic algorithm for grid computing

verfasst von: Zahra Pooranian, Mohammad Shojafar, Jemal H. Abawajy, Ajith Abraham

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A grid computing system consists of a group of programs and resources that are spread across machines in the grid. A grid system has a dynamic environment and decentralized distributed resources, so it is important to provide efficient scheduling for applications. Task scheduling is an NP-hard problem and deterministic algorithms are inadequate and heuristic algorithms such as particle swarm optimization (PSO) are needed to solve the problem. PSO is a simple parallel algorithm that can be applied in different ways to resolve optimization problems. PSO searches the problem space globally and needs to be combined with other methods to search locally as well. In this paper, we propose a hybrid-scheduling algorithm to solve the independent task-scheduling problem in grid computing. We have combined PSO with the gravitational emulation local search (GELS) algorithm to form a new method, PSO–GELS. Our experimental results demonstrate the effectiveness of PSO–GELS compared to other algorithms.

Vorheriger Artikel Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals

Nächster Artikel Some results on the reciprocal sum-degree distance of graphs

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Abdollahi Azgomi M, Eetezari-maleki R (2010) Task scheduling modeling and reliability evaluation of grid services using colored Petri nets. Future Gener Comput Syst 26(8):1141–1150CrossRef

Balachandar S, Kannan K (2007) Randomized gravitational emulation search algorithm for symmetric traveling salesman problem. Appl Math Comput 192(2):413–421MathSciNetCrossRefMATH

Barzegar B, Rahmani AM, Zamanifar K, Divsalar A (2009) Gravitational emulation local search algorithm for advanced reservation and scheduling in grid computing systems. In: Fourth international conference on computer sciences and convergence information technology ICCIT ’09, Seoul, pp 1240–1245

Benedict SH, Vasudevan V (2008) Improving scheduling of scientific workflows using tabu search for computational grids. Inf Technol J 7(1):91–97CrossRef

Chen R, Shiau D, Andlo SH (2009) Combined discrete particle swarm optimization and simulated annealing for grid computing scheduling problem. In: Lecture notes in computer science, vol, 57. Springer, Berlin, pp 242–251

Cruz JB Jr, Chen G, Li D, Wang X (2003) Particle swarm optimization for resource allocation in UAV cooperative control. In: AIAA guidance navigation and control conference and exhibit, Reno, pp 1–11

Cruz-Chavez M, Rodríguez-Leon A, Avila-Melgar E, Juarez-Perez F, Cruz-Rosales M, Rivera-Lopez R (2010) Genetic-annealing algorithm in grid environment for scheduling problems. In: Security-enriched urban computing and smart grid communications in computer and information science, vol 78. springer, New York, pp 1–9

Eberhat R, Kennedy J (1995) A new optimizer using particle swarm theory. In: Sixth international symposium on micro machine and human science, Piscataway, pp 39–43

Foster I, Kesselman C, Nick J, Tuecke S (2002) The physiology of the grid: an open grid services architecture for distributed systems integration. Computer 35(6):1–4CrossRef

Gao Y, Rong HQ, Huang JZ (2005) Adaptive grid job scheduling with genetic algorithms. Future Gener Comput Syst 21:151–161CrossRef

Garg SK, Buyya R, Siegel HJ (2010) Time and cost trade-off management for scheduling parallel applications on utility Grids. Future Gener Comput Syst 26:1344–1355CrossRef

Izakian H, Tork Ladani B, Zamanifar K, Abraham A (2009) A novel particle swarm optimization approach for grid job scheduling. Commun Comput Inf Sci 31:100–109CrossRef

Joshua Samuel Raj R, Vasudevan V (2011) Beyond simulated annealing in grid scheduling. Int J Comput Sci Eng 3(3):1312–1318

Liu H, Abraham A, Hassanien A (2010) Scheduling jobs on computational grids using a fuzzy particle swarm optimization algorithm. Future Gener Comput Syst 26:1336–1343CrossRef

Maheswaran M (1999) Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. J Parallel Distributed Comput 59(2):107–131CrossRef

Mathiyalagan P, Dhepthie UR, Sivanandam SN (2010) Grid scheduling using enhanced PSO algorithm. Int J Comput Sci Eng 2(2):140–145

Orosz ZE, Jacobson SH (2002) Analysis of static simulated annealing algorithm. J Optim Theory Appl 115:165–182MathSciNetCrossRefMATH

Padmavathi S, Mercy shalinie S (2010) Dag scheduling on cluster of workstations using hybrid particle swarm optimization. In: First international conference on emerging trends in engineering and technology ICETET ’08, vol 10, Mawson Lakes, no 6, pp 384–389

Pooranian Z, Harounabadi A, Shojafar M, Hedayat N (2011) New hybrid algorithm for task scheduling in grid computing to decrease missed task. World Acad Sci Eng Technol 55:924–928

Pooranian Z, Shojafar M, Javadi B (2012) Independent task scheduling in grid computing based on queen bee algorithm. IAES Int J Artif Intell 1(4):171–181

Pooranian Z, Shojafar M, Abawajy JH, Singhal M (2013a) GLOA: a new job scheduling algorithm for grid computing. Int J Artif Intell Interact Multimed 2(1):59–64

Pooranian Z, Shojafar M, Tavoli R, Singhal M, Abraham A (2013b) A hybrid meta-heuristic algorithm for job scheduling on computational grids. Inform J 37(2):157–164

Shiau Der-Fang (2011) A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences. Expert Syst Appl 38:235–248CrossRef

Shiau D, Huang Y (2012) A hybrid two-phase encoding particle swarm optimization for total weighted completion time minimization in proportionate flexible flow shop scheduling. Int J Adv Manuf Technol 58(1):339–357CrossRef

Shi Y, Eberhat R (1998) Parameter selection in particle swarm optimization. In: Proceedings of the 7th annuals conference on evolutionary programming. Springer, Berlin, pp 591–600

Shi Y, Eberhat R (1999) Empirical study of particle swarm optimization. In: Proceedings of the IEEE congress on evolutionary computation, vol 3. IEEE Press, Los Alamitos, pp 1945–1950

Shojafar M, Barzegar S, Meybodi MR (2010) A new method on resource scheduling in grid systems based on hierarchical stochastic Petri net. In: Proceedings of third international conference on computer and electrical engineering (ICCEE 2010), Chengdu, pp 175–180

Shojafar M, Pooranian Z, Abawajy JH, Meybodi MR (2013) An efficient scheduling method for grid systems based on a hierarchical stochastic Petri net. J Comput Sci Eng 7(1):44–52CrossRef

Sivanandam SN, Visalakshi P (2007) Multiprocessor scheduling using hybrid particle swarm optimization with dynamically varying inertia. Int J Comput Sci Appl 4(3):95–106

Sullivan WT, Werthimer D, Bowyer S, Cobb J, Gedye D, Anderson D (1997) A new major SETI project based on Project Serendip data and 100000 personal computers. In: Proceedings of the fifth international conference on bioastronomy, Bologna, no 61, p 729

Tao Q, Chang H, Yi Y, Gu CH, Li W (2011) A rotary chaotic PSO algorithm for trustworthy scheduling of a grid workflow. Comput Oper Res 38:824–836MathSciNetCrossRefMATH

Voudouris CH, Tsang E (1995) Guided local search. Eur J Oper Res 16(3):46–50

Webster B (2004) Solving combinatorial optimization problems using a new algorithm based on gravitational attraction. PhD thesis, Florida Institute of Technology, Melbourne

Weijun X, Zhiming W, Wei ZH, Genke Y (2004) A new hybrid optimization algorithm for the job-shop scheduling problem. In: Proceeding of the 2004 American control conference, vol 6, Boston, pp 5552–5557

Xhafa F, Gonzalez J, Dahal K, Abraham A (2009) A GA(TS) hybrid algorithm for scheduling in computational grids. In: Hybrid artificial intelligence systems. Lecture notes in computer science, vol 5572. Springer, Berlin, pp 285–292

Yan-ping B, Wei ZH, Jin-shou Y (2008) An improved PSO algorithm and its application to grid scheduling problem. International symposium on computer science and computational technology ISCSCT ’08, Shanghai, pp 352–355

Yusof M, Badak K, Stapa M (2010) Achieving of tabu search algorithm for scheduling technique in grid computing using GridSim simulation tool: multiple jobs on limited resource. Int J Grid Distributed Comput 3(4):19–32

Zhang L, Chen Y, Sun R, Jing SH, Yang B (2008) A task scheduling algorithm based on PSO for grid computing. Int J Comput Intell Res 4(1):37–43CrossRef

Titel: An efficient meta-heuristic algorithm for grid computing
verfasst von: Zahra Pooranian
Mohammad Shojafar
Jemal H. Abawajy
Ajith Abraham
Publikationsdatum: 01.10.2015
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2015
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-013-9644-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2015

On improving convex quadratic programming relaxation for the quadratic assignment problem

Rank bounds for a hierarchy of Lovász and Schrijver

A unified linear-programming modeling of some topological indices

Approximating minimum power edge-multi-covers

On Lagrangians of r-uniform hypergraphs

-labelling of the direct product of a complete graph and a cycle