Research Article | OPEN ACCESS
Scheduling Independent Jobs on Computational Grid using Biogeography Based Optimization Algorithm for Makespan Reduction
1S. Selvi and 2D. Manimegalai
1Department of Electronics and Communication Engineering, Dr. Sivanthi Aditanar College of Engineering, Tiruchendur-628215
2Department of Information Technology, National Engineering College, Kovilpatti-628503,
Tamilnadu, India
Research Journal of Applied Sciences, Engineering and Technology 2014 8:964-975
Received: March 29, 2014 | Accepted: April 28, 2014 | Published: August 25, 2014
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
-
Berman, F., 1998. The Grid: Blueprint for a Future Computing Infrastructure. Morgan Kaufmann Publishers, Springer-Verlag, San Mateo, CA.
-
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 -
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 -
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 -
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 -
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.
-
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 -
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 -
Foster, I. and C. Kesselmann, 2004. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann Publishers, USA.
-
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 -
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 -
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 -
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.
-
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 -
Ibarra, O.H. and C.E. Ki, 1977. Heuristic algorithms for scheduling independent tasks on nonidentical processors. JACM, 24(2): 280-289.
CrossRef -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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.
-
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.
-
Siegel, H.J., H.G. Dietz and J.K. Antonio, 1996. Software support for heterogeneous computing. ACM Comput. Surv., 28(1): 237-239.
CrossRef -
Simon, D., 2008. Biogeography-based optimization. IEEE T. Evolut. Comput., 12(6): 702-713.
CrossRef -
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 -
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 -
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.
|
|
![](http://www.maxwellsci.com/images/RJASET-maxw.jpg) |
ISSN (Online): 2040-7467
ISSN (Print): 2040-7459 |
![Submit Manuscript](../images/sub.jpg) |
Information |
|
|
|
Sales & Services |
|
|
|