Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Soft Computing
Published in: Soft Computing 5/2013

01-05-2013 | Methodologies and Application

Optimal job scheduling in grid computing using efficient binary artificial bee colony optimization

Authors: Sung-Soo Kim, Ji-Hwan Byeon, Hongbo Liu, Ajith Abraham, Seán McLoone

Published in: Soft Computing | Issue 5/2013

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The artificial bee colony has the advantage of employing fewer control parameters compared with other population-based optimization algorithms. In this paper a binary artificial bee colony (BABC) algorithm is developed for binary integer job scheduling problems in grid computing. We further propose an efficient binary artificial bee colony extension of BABC that incorporates a flexible ranking strategy (FRS) to improve the balance between exploration and exploitation. The FRS is introduced to generate and use new solutions for diversified search in early generations and to speed up convergence in latter generations. Two variants are introduced to minimize the makepsan. In the first a fixed number of best solutions is employed with the FRS while in the second the number of the best solutions is reduced with each new generation. Simulation results for benchmark job scheduling problems show that the performance of our proposed methods is better than those alternatives such as genetic algorithms, simulated annealing and particle swarm optimization.
previous article Analysis and synthesis of laser forming process using neural networks and neuro-fuzzy inference system
next article A knowledge-based cooperative differential evolution for neural fuzzy inference systems

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Literature
Abraham A, Buyya R, Nath B (2000) Nature’s heuristics for scheduling jobs on computational grids. In: The 8th IEEE international conference on advanced computing and communications (ADCOM 2000), pp 45–52
Abraham A, Liu H, Zhao M (2008) Particle swarm scheduling for work-flow applications in distributed computing environments. Metaheuristics for scheduling in industrial and manufacturing applications. Stud Comput Intell 128:327–342CrossRef
Abraham A, Jatoth R, Rajasekhar A (2012) Hybrid differential artificial bee colony algorithm. J Comput Theor Nanosci 9(2):249–257CrossRef
Alzaqebah M, Abdullah S (2011) Comparison on the selection strategies in the artificial bee colony algorithm for examination timetabling problems. Int J Soft Comput Eng 1:158–163
Bao L, Zeng J (2009) Comparison and analysis of the selection mechanism in the artificial bee colony algorithm. In: Ninth international conference on hybrid intelligent systems, 2009, HIS’09, vol 1. IEEE, pp 411–416
Bonabeau E, Dorigo M, Theraulaz G (1999) Swarm intelligence: from natural to artificial systems. Oxford University Press, OxfordMATH
Braun T, Siegel H, Beck N, Boloni L, Maheswaran M, Reuther A, Robertson J, Theys M, Yao B (2001) A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J Parallel Distrib Comput 61(6):810–837CrossRef
Brucker P (2007) Scheduling algorithms. Springer, Berlin
Chandrasekaran K, Hemamalini S, Simon S, Padhy N (2012) Thermal unit commitment using binary/real coded artificial bee colony algorithm. Electric Power Syst Res 84(1):109–119CrossRef
Chung K, Erdös P (1952) On the application of the Borel-Cantelli lemma. Trans Am Math Soc 72:179–186CrossRefMATH
Chung W, Chang R (2009) A new mechanism for resource monitoring in grid computing. Future Gen Comput Syst 25(1):1–7CrossRef
Clerc M (2006) Particle swarm optimization. Wiley-ISTE
Cuevas E, Sención-Echauri F, Zaldivar D, Pérez-Cisneros M (2012) Multi-circle detection on images using artificial bee colony (abc) optimization. Soft Comput 16(2):1–16CrossRef
Davidovic T, Selmic M, Teodorovic D (2009) Scheduling independent tasks: bee colony optimization approach. In: 17th Mediterranean conference on control and automation, 2009, MED’09. IEEE, pp 1020–1025
Davis R, Burns A (2011) A survey of hard real-time scheduling for multiprocessor systems. ACM Comput Surveys 43(4):35CrossRef
Derrac J, García S, Molina D, Herrera F (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol Comput 1:3–18CrossRef
Di Martino V, Mililotti M (2004) Sub optimal scheduling in a grid using genetic algorithms. Parallel Comput 30(5-6):553–565CrossRef
Dong F Akl S (2006) Scheduling algorithms for grid computing: state of the art and open problems. Technical report, School of Computing, Queen’s University, Kingston, Ontario
Forestiero A, Mastroianni C, Spezzano G (2008) So-grid: a self-organizing grid featuring bio-inspired algorithms. ACM Trans Auton Adapt Syst 3(2):1–37CrossRef
Foster I, Kesselman C (2004) The grid: blueprint for a new computing infrastructure. Morgan Kaufmann
Foster I, Zhao Y, Raicu I, Lu S (2008) Cloud computing and grid computing 360-degree compared. In: Grid computing environments workshop, 2008, GCE’08. IEEE, pp 1–10
Fujita S, Yamashita M (2000) Approximation algorithms for multiprocessor scheduling problem. IEICE Trans Inf Syst 83(3):503–509
Gao Y, Rong H, Huang J (2005) Adaptive grid job scheduling with genetic algorithms. Future Gen Comput Syst 21(1):151–161CrossRef
García S, Molina D, Lozano M, Herrera F (2009) A study on the use of non-parametric tests for analyzing the evolutionary algorithms behaviour: a case study on the cecn2005 special session on real parameter optimization. J Heuristics 15(6):617–644CrossRefMATH
Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. WH Freeman & Co
Han L, Berry D (2008) Semantic-supported and agent-based decentralized grid resource discovery. Future Gen Comput Syst 24(8):806–812CrossRef
He R, Wang Y, Wang Q, Zhou J, Hu C (2005) Improved particle swarm optimization based on self-adaptive escape velocity. Chin J Softw 16(12):2036–2044CrossRefMATH
Hou E, Ansari N, Ren H (1994) A genetic algorithm for multiprocessor scheduling. IEEE Trans Parallel Distrib Syst 5(2):113–120
Izakian H, Ladani B, Abraham A, Snášel V (2010) A discrete particle swarm optimization approach for grid job scheduling. Int J Innov Comput Inf Control 6:1–15
Jansen K, Mastrolilli M, Solis-Oba R (2000) Approximation algorithms for flexible job shop problems. In: Lecture notes in computer science. LATIN 2000: theoretical informatics, vol 1776, pp 68–77
Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (abc) algorithm. J Global Optim 39(3):459–471MathSciNetCrossRefMATH
Karaboga D, Basturk B (2008) On the performance of artificial bee colony (abc) algorithm. Appl Soft Comput 8(1):687–697CrossRef
Kennedy J, Eberhart R, Shi Y (2001) Swarm intelligence. Springer, Germany
Kruskal W, Wallis W (1952) Use of ranks in one-criterion variance analysis. J Am Stat Assoc 47:583–621CrossRefMATH
Laalaoui Y, Drias H (2010) Aco approach with learning for preemptive scheduling of real-time tasks. Int J Bio-Inspired Comput 2(6):383–394CrossRef
Lahoz-Beltra R, Perales-Gravan C (2010) A survey of nonparametric tests for the statistical analysis of evolutionary computational experiments. Int J Inf Theor Appl 17(1):41–61
Lee W, Cai W (2011) A novel artificial bee colony algorithm with diversity strategy. In: 2011 Seventh international conference on natural computation (ICNC), vol 3. IEEE, pp 1441–1444
Li J, Pan Q, Xie S, Wang S (2011) A hybrid artificial bee colony algorithm for flexible job shop scheduling problems. Int J Comput Commun Control 6(2):286–296
Li G, Niu P, Xiao X (2012) Development and investigation of efficient artificial bee colony algorithm for numerical function optimization. Appl Soft Comput 12(1):320–332CrossRef
Liu H, Abraham A, Clerc M (2007) Chaotic dynamic characteristics in swarm intelligence. Appl Soft Comput 7(3):1019–1026CrossRef
Liu H, Abraham A, Wang Z (2009) A multi-swarm approach to multi-objective flexible job-shop scheduling problems. Fundam Inf 95(4):465–489MathSciNet
Liu H, Abraham A, Hassanien A (2010) Scheduling jobs on computational grids using a fuzzy particle swarm optimization algorithm. Future Gen Comput Syst 26(8):1336–1343CrossRef
Ma M, Liang J, Guo M, Fan Y, Yin Y (2011) Sar image segmentation based on artificial bee colony algorithm. Appl Soft Comput 11(8):5205–5214CrossRef
Mann H, Whitney D (1947) On a test of whether one of two random variables is stochastically larger than the other. Ann Math Stat 18(1):50–60MathSciNetCrossRefMATH
Mastrolilli M, Gambardella L (1999) Effective neighborhood functions for the flexible job shop problem. J Sched 3(1):3–20MathSciNetCrossRef
Mezura-Montes E, Velez-Koeppel R (2010) Elitist artificial bee colony for constrained real-parameter optimization. In: 2010 IEEE Congress on evolutionary computation (CEC). IEEE, pp 1–8
Nemeth Z, Sunderam V (2003) Characterizing grids: attributes, definitions, and formalisms. J Grid Comput 1(1):9–23CrossRef
Pampara G, Engelbrecht A (2011) Binary artificial bee colony optimization. In: Proceedings of 2011 IEEE symposium on swarm intelligence (SIS). IEEE, pp 1–8
Pan Q, Fatih Tasgetiren M, Suganthan P, Chua T (2011) A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Inf Sci 181(12):2455–2468CrossRef
Pinedo M (2012) Scheduling: theory, algorithms, and systems. Springer, Berlin
Ritchie G, 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
Ritchie G, Levine J (2004) A hybrid ant algorithm for scheduling independent jobs in heterogeneous computing environments. In: Proceedings of 23rd workshop of the UK Planning and Scheduling Special Interest Group, PLANSIG 2004
Sharma T, Pant M (2011) Enhancing the food locations in an artificial bee colony algorithm. In: 2011 IEEE symposium on swarm intelligence (SIS). IEEE, pp 1–5
Singh A, Sundar S (2011) An artificial bee colony algorithm for the minimum routing cost spanning tree problem. Soft Comput 15(12):1–11CrossRef
Thesen A (1998) Design and evaluation of tabu search algorithms for multiprocessor scheduling. J Heuristics 4(2):141–160CrossRefMATH
Vivekanandan K, Ramyachitra D, Anbu B (2011) Artificial bee colony algorithm for grid scheduling. J Converg Inf Technol 6:328–339
Walker R (2007) Purposive behavior of honeybees as the basis of an experimental search engine. Soft Comput 11(8):697–716CrossRef
Wei Y, Blake M (2010) Service-oriented computing and cloud computing: challenges and opportunities. IEEE Internet Comput 14(6):72–75CrossRef
Wong L, Puan C, Low M, Wong Y (2010) Bee colony optimisation algorithm with big valley landscape exploitation for job shop scheduling problems. Int J Bio-Inspired Comput 2(2):85–99CrossRef
Wu A, Yu H, Jin S, Lin K, Schiavone G (2004) An incremental genetic algorithm approach to multiprocessor scheduling. IEEE Trans Parallel Distrib Syst 15(9):824–834CrossRef
Xhafa F, Carretero J, Abraham A (2007) Genetic algorithm based schedulers for grid computing systems. Int J Innov Comput Inf Control 3(5):1–19
Xiao R, Chen W, Chen T (2012) Modeling of ant colony’s labor division for the multi-project scheduling problem and its solution by pso. J Comput Theor Nanosci 9(2):223–232
Yang X (2011) Nature-inspired metaheuristic algorithms. Luniver Press
Yue B, Liu H, Abraham A (2012) Dynamic trajectory and convergence analysis of swarm algorithm. Comput Inf 31(2):371–392MathSciNet
Ziarati K, Akbari R, Zeighami V (2011) On the performance of bee algorithms for resource-constrained project scheduling problem. Appl Soft Comput 11:3720–3733CrossRef
Metadata
Title
Optimal job scheduling in grid computing using efficient binary artificial bee colony optimization
Authors
Sung-Soo Kim
Ji-Hwan Byeon
Hongbo Liu
Ajith Abraham
Seán McLoone
Publication date
01-05-2013
Publisher
Springer-Verlag
Published in
Soft Computing / Issue 5/2013
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-012-0957-7

Other articles of this Issue 5/2013

Soft Computing 5/2013 Go to the issue

Methodologies and Application

An examination of different fitness and novelty based selection methods for the evolution of neural networks

Methodologies and Application

Neighborhood field for cooperative optimization

Methodologies and Application

An extended functional network model and its application for a gas sensing system

Methodologies and Application

An automatic approach to extract goal plans from soccer simulated matches

Methodologies and Application

Possibilistic classifiers for numerical data

Methodologies and Application

Financial time series forecasting using LPP and SVM optimized by PSO

Premium Partner

    Image Credits