Abstract

Due to the development of information and network technologies, idle computers all over the world can be organized and utilized to enhance the overall computation performance. Grid computing refers to the combination of computer resources from multiple administrative domains used to reach a common goal. Grids offer a way of using the information technology resources optimally inside an organization. As the grid environments facilitate distributed computation, the scheduling of grid jobs has become an important issue. This study introduces a novel approach based on Biogeography Based Optimization algorithm (BBO) for scheduling jobs on computational grid. The proposed approach generates an optimal schedule so as to complete the jobs within a minimum period of time. The performance of the proposed algorithm has been evaluated with Genetic Algorithm (GA), Differential Evolution algorithm (DE), Ant Colony Optimization algorithm (ACO) and Particle Swarm Optimization algorithm (PSO).

Keywords:

Biogeography based optimization , grid computing , job scheduling , makespan,

References

1. Berman, F., 1998. The Grid: Blueprint for a Future Computing Infrastructure. Morgan Kaufmann Publishers, Springer-Verlag, San Mateo, CA.
   
2. Berman, F., R. Wolski, S. Figueria, J. Schopf and G. Shao, 1996. Application-level scheduling on distributed heterogeneous networks. Proceeding of the 1996 ACM/IEEE Conference on Supercomputing, Article No: 39.
   CrossRef    
3. Berman, F., R. Wolski, H. Casanova, W. Cirne, H. Dail, M. Faerman, S. Figueira, J. Hayes, G. Obertelli, J. Schopf, G. Shao, S. Smallen, N. Spring, A. Su and D. Zagorodnov, 2003. Adaptive computing on the grid using apples. IEEE T. Parall. Distr., 14(4): 369-382.
   CrossRef    
4. Bhattacharya, A. and P.K. Chattopadhyay, 2010. Biogeography-based optimization for different economic load dispatch problems. IEEE T. Power Syst., 25(2): 1064-1077.
   CrossRef    
5. Braun, T.D., H.J. Siegel, N. Beck, D.A. Hensgen and R.F. Freund, 2001. A comparison of eleven static heuristics for mapping a class of independent tasks on heterogeneous distributed system. J. Parallel Distr. Com., 61(6): 810-837.
   CrossRef    
6. Dong, F. and S.G. Akl, 2006. Scheduling algorithms for grid computing: State of the art and open problems. Technical Report No. 2006-504. School of Computing, Queen's University Kingston, Ontario.
   
7. Du, D., D. Simon and M. Ergezer, 2009. Biogeography-based optimization combined with evolutionary strategy and immigration refusal. Proceeding of the IEEE Conference on Systems, Man and Cybernetics. San Antonio, Texas, pp: 997-1002.
   CrossRef    
8. Foster, I. and A. Iamnitchi, 2003. On death, taxes and the convergence of peer-to-peer and grid computing. Proceeding of 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03), Berkeley, CA, USA.
   CrossRef    
9. Foster, I. and C. Kesselmann, 2004. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann Publishers, USA.
   
10. Foster, I., C. Kesselman and S. Tuecke, 2001. The anatomy of the grid: Enabling scalable virtual organizations. Int. J. Supercomput. Ap., 15(3): 200-220.
    CrossRef    
11. Garg, S.K., R. Buyya and H.J. Siegel., 2010. Time and cost trade-off management for scheduling parallel applications on utility grids. Future Gener. Comp. Sy., 26(8): 1344-1355.
    CrossRef    
12. Hamscher, V., U. Schwiegelshohn, A. Streit and R. Yahyapour, 2000. Evaluation of job-scheduling strategies for grid computing. Proceeding of 1st IEEE/ACM International Workshop on Grid Computing (GRID'00). Bangalore, India, pp: 191-202.
    CrossRef    
13. Huang, V.L., A.K. Qin, K. Deb, E. Zitzler, P.N. Suganthan, J.J. Liang, M. Preuss and S. Huband, 2007. Problem definitions for performance assessment on multi-objective optimization algorithms. Technical Report, Nanyang Technological University, Singapore.
    
14. Huband, S., P. Hingston, L. Barone and L. While, 2006. A review of multiobjective test problems and a scalable test problem toolkit. IEEE T. Evolut. Comput., 10(5): 477-506.
    CrossRef    
15. Ibarra, O.H. and C.E. Ki, 1977. Heuristic algorithms for scheduling independent tasks on nonidentical processors. JACM, 24(2): 280-289.
    CrossRef    
16. Jarvis, S.A., D.P. Spooner, H.N. Lim Choi Keung, G.R. Nudd, J. Cao and S. Saini, 2003. Performance prediction and its use in parallel and distributed computing systems. Proceeding of the IEEE/ACM International Workshop on Performance Modelling, Evaluation and Optimization of Parallel and Distributed Systems. Nice, France.
    CrossRef    
17. Khokhar, A.A., V.K. Prasanna, M.E. Shaaban and C.L. Wang, 1993. Heterogeneous computing: Challenges and opportunities. IEEE Comput., 26(6): 18-27.
    CrossRef    
18. Krauter, K., R. Buyya and M. Maheswaran, 2002. A taxonomy and survey of grid resource management systems for distributed computing. Software Pract. Exper., 32: 135-164.
    CrossRef    
19. Liu, H., A. Abraham and A.E. Hassanien, 2010. Scheduling jobs on computational grids using a fuzzy particle swarm optimization algorithm. Future Gener. Comp. Sy., 26(8): 1336-1343.
    CrossRef    
20. Lohokare, M.R., S.S. Pattnaik, S. Devi, K.M. Bakwad and J.G. Joshi, 2009. Parameter calculation of rectangular microstrip antenna using biogeography-based optimization. Proceeding of Applied Electromagnetics Conference (AEMC). Kolkata, DOI: 10.1109/AEMC.2009.5430676.
    CrossRef    
21. Lozovyy, P., G. Thomas and D. Simon, 2011. Biogeography-based optimization for robot controller tuning. Computational Modeling and Simulation of Intellect: Current State and Future Perspectives. IGI Global Publication, Chapter 7, pp: 162-181.
    CrossRef    
22. Ma, H., S. Ni and M. Sun, 2009. Equilibrium species counts and migration model tradeoffs for biogeography-based optimization. Proceeding of the IEEE Conference on Decision and Control. Shanghai, P.R. China, pp: 3306-3310.
    CrossRef    
23. Mateescu, G., 2003. Quality of service on the grid via metascheduling with resource co-scheduling and co-reservation. Int. J. High Perform. C., 17(3): 209-218.
    CrossRef    
24. Panchal, V., P. Singh, N. Kaur and H. Kundra, 2009. Biogeography based satellite image classification. Int. J. Comput. Sci. Inform. Secur., 6(2): 269-274.
    
25. Schopf, J., 2001. Ten Actions When Super Scheduling, document of Scheduling Working Group, Global Grid Forum. Retrieved form: http://www.ggf.org/ documents/GFD.4.pdf, July 2001.
    
26. Siegel, H.J., H.G. Dietz and J.K. Antonio, 1996. Software support for heterogeneous computing. ACM Comput. Surv., 28(1): 237-239.
    CrossRef    
27. Simon, D., 2008. Biogeography-based optimization. IEEE T. Evolut. Comput., 12(6): 702-713.
    CrossRef    
28. Singh, U., H. Singla and T. Kamal, 2010. Design of Yagi-Uda antenna using biogeography based optimization. IEEE T. Antenn. Propag., 58(10): 3375-3379.
    CrossRef    
29. Song, Y., M. Liu and Z. Wang, 2010. Biogeography-based optimization for the traveling salesman problems. Proceeding of the 3rd International Joint Conference on Computational Science and Optimization (CSO, 2010). Huangshan, Anhui, China, pp: 295-299.
    CrossRef    
30. Sun, X.H. and W. Ming, 2003. Grid harvest service: A system for long-term, application-level task scheduling. Proceeding of 2003 International Parallel and Distributed Processing Symposium, ISSN: 1530-2075.
    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.