Skip to main content
SpringerLink
Log in

Efficient Batch Job Scheduling in Grids Using Cellular Memetic Algorithms

  • Published:
Journal of Mathematical Modelling and Algorithms

Abstract

Computational grids are an important emerging paradigm for large-scale distributed computing. As grid systems become more wide-spread, techniques for efficiently exploiting the large amount of grid computing resources become increasingly indispensable. A key aspect in order to benefit from these resources is the scheduling of jobs to grid resources. Due to the complex nature of grid systems, the design of efficient grid schedulers becomes challenging since such schedulers have to be able to optimize many conflicting criteria in very short periods of time. This problem has been tackled in the literature by several different metaheuristics, and our main focus in this work is to develop a new highly competitive technique with respect to the existing ones. For that, we exploit the capabilities of cellular memetic algorithms (cMAs), a kind of memetic algorithm with structured population, for obtaining efficient batch schedulers for grid systems, and the obtained results will be compared versus the state of the art. A careful design of the cMA methods and operators for the problem yielded to an efficient and robust implementation. Our experimental study, based on a known static benchmark for the problem, shows that this heuristic approach is able to deliver very high quality planning of jobs to grid nodes and thus it can be used to design efficient dynamic schedulers for real grid systems. Such dynamic schedulers can be obtained by running the cMA-based scheduler in batch mode for a very short time to schedule jobs arriving in the system since the last activation of the cMA scheduler.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Abraham, A., Buyya, R., Nath, B.: Nature’s heuristics for scheduling jobs on computational grids. In: The 8th IEEE International Conference on Advanced Computing and Communications (ADCOM), pp. 45–52. India (2000)

  2. Alba, E., Dorronsoro, B.: The exploration/exploitation tradeoff in dynamic cellular evolutionary algorithms. IEEE Trans. Evol. Comput. 9(2), 126–142 (2005)

    Article  Google Scholar 

  3. Alba, E., Dorronsoro, B.: Cellular Genetic Algorithms. Operations Research/Computer Science Interfaces Series, vol. 42. Springer-Verlag Heidelberg (2008) ISBN: 978-0-387-77609-5

  4. Alba, E., Dorronsoro, B., Alfonso, H.: Cellular memetic algorithms. J. Comput. Sci. Technol. 5(4), 257–263 (2005)

    Google Scholar 

  5. Alba, E., Dorronsoro, B., Alfonso, H.: Cellular memetic algorithms evaluated on SAT. In: XI Congreso Argentino de Ciencias de la Computacixxn (CACIC). DVD Edition (2005)

  6. Alba, E., Dorronsoro, B., Giacobini, M., Tomassini, M.: Handbook of Bioinspired Algorithms and Applications, Chapt. 7, Decentralized Cellular Evolutionary Algorithms, pp. 103–120. CRC Press (2006)

  7. Alba, E., Tomassini, M.: Parallelism and evolutionary algorithms. IEEE Trans. Evol. Comput. 6(5), 443–462 (2002)

    Article  Google Scholar 

  8. Alba, E., Troya, J.: Cellular evolutionary algorithms: evaluating the influence of ratio. In: Proc. of the 6th International Conference on Parallel Problem Solving from Nature (PPSN). LNCS, vol. 1917, pp. 29–38 (2000)

  9. Braun, H., Siegel, T., Beck, N., Bölöni, L., Maheswaran, M., Reuther, A., Robertson, J., Theys, M., Yao, B.: 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–837 (2001)

    Article  Google Scholar 

  10. Buyya, R., Abramson, D., Giddy, J.: Nimrod/G: an architecture for a resource management and scheduling system in a global computational grid. In: The 4th Int. Conf. on High Performance Computing, pp. 283–289. China (2000)

  11. Carretero, J., Xhafa, F.: Using genetic algorithms for scheduling jobs in large scale grid applications. Journal of Technological and Economic Development—A Research Journal of Vilnius Gediminas Technical University 12(1), 11–17 (2006)

    Google Scholar 

  12. Casanova, H., Dongarra, J.: Netsolve: network enabled solvers. IEEE Comput. Sci. Eng. 5(3), 57–67 (1998)

    Article  Google Scholar 

  13. Casanova, H., Legrand, A., Zagorodnov, D., Berman, F.: Heuristics for scheduling parameter sweep applications in grid environments. In: Heterogeneous Computing Workshop, pp. 349–363 (2000)

  14. Coello, C., Van Veldhuizen, D., Lamont, G.: Evolutionary Algorithms for Solving Multi-Objective Problems, Genetic Algorithms and Evolutionary Computation. Kluwer Academic Pubishers (2002)

  15. Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. Wiley (2001)

  16. Foster, I., Kesselman, C.: The Grid—Blueprint for a New Computing Infrastructure. Morgan Kaufmann Publishers (1998)

  17. Foster, I., Kesselman, C., Tuecke, S.: The anatomy of the grid: enabling scalable virtual organizations. Int. J. Supercomput. Appl. 15(3), 200–222 (2001)

    Article  Google Scholar 

  18. Frey, J., Tannenbaum, T., Foster, I., Livny, M., Tuecke, S.: Condor-G: a computation management agent for multi-institutional grids. Cluster Comput. 5(3), 237–246 (2002)

    Article  Google Scholar 

  19. Ghafoor, A., Yang, J.: Distributed heterogeneous supercomputing management system. IEEE Comput. 26(6), 78–86 (1993)

    Google Scholar 

  20. Giacobini, M., Tomassini, M., Tettamanzi, A., Alba, E.: Selection intensity in cellular evolutionary algorithms for regular lattices. IEEE Trans. Evol. Comput. 9(5), 489–505 (2005)

    Article  Google Scholar 

  21. Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Publishers, Boston (1997)

    MATH  Google Scholar 

  22. Kafil, M., Ahmad, I.: Optimal task assignment in heterogeneous distributed computing systems. IEEE Concurr. 6(3), 42–51 (1998)

    Article  Google Scholar 

  23. Linderoth, L., Wright, S.: Decomposition algorithms for stochastic programming on a computational grid. Comput. Optim. Appl. (Special issue on Stochastic Programming) 24, 207–250 (2003)

    MATH  MathSciNet  Google Scholar 

  24. Luna, F., A. Nebro, Alba, E.: Observations in using grid-enabled technologies for solving Multi-objective optimization problems. Parallel Comput. 32, 377–393 (2006)

    Article  MathSciNet  Google Scholar 

  25. Martino, V., Mililotti, M.: Sub optimal scheduling in a grid using genetic algorithms. Parallel Comput. 30, 553–565 (2004)

    Article  Google Scholar 

  26. Talbi, E.-G.: Parallel Combinatorial Optimization. John Wiley & Sons, USA (2006)

    Google Scholar 

  27. Talbi, E.-G., Zomaya, A.: Grids for Bioinformatics and Computational Biology. John Wiley & Sons, USA (2007)

    Google Scholar 

  28. Wright, S.: Solving optimization problems on computational grids. Optima 65, 8–13 (2001)

    Google Scholar 

  29. Xhafa, F.: An experimental study on GA replacement operators for scheduling on grids. In: The 2nd International Conference on Bioinspired Optimization Methods and their Applications (BIOMA), pp. 212–130. Ljubljana, Slovenia (2006)

  30. Xhafa, F., Carretero, J., Alba, E., Dorronsoro, B.: Design and evaluation of a tabu search method for job scheduling in distributed environments. In: The 11th International Workshop on Nature Inspired Distributed Computing (NIDISC’08), Miami, Florida, USA, 14–18 April (to appear)

Download references

Author information

Authors and Affiliations

  1. Dept. de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, C/Jordi Girona 1-3, 08034, Barcelona, Spain

    Fatos Xhafa & Bernat Duran

  2. Dpto. de Lenguajes y Ciencias de la Computación, E.T.S.I. Informática, Campus de Teatinos, 29071, Málaga, Spain

    Enrique Alba & Bernabé Dorronsoro

Authors
  1. Fatos Xhafa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Enrique Alba
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bernabé Dorronsoro
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Bernat Duran
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fatos Xhafa.

Additional information

Research partially supported by ASCE Project TIN2005-09198-C02-02, Project FP6-2004-IST-FETPI (AEOLUS) and MEC TIN2005-25859-E.

This work has been partially funded by the Spanish MEC and FEDER under contract TIN2005-08818-C04-01 (the OPLINK project: http://oplink.lcc.uma.es).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Xhafa, F., Alba, E., Dorronsoro, B. et al. Efficient Batch Job Scheduling in Grids Using Cellular Memetic Algorithms. J Math Model Algor 7, 217–236 (2008). https://doi.org/10.1007/s10852-008-9076-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10852-008-9076-y

Keywords

Mathematics Subject Classifications (2000)

Search

Navigation