Optimal Grid Scheduling Using Improved Artificial Bee Colony Algorithm

Authors: T. Vigneswari, M. A. Maluk Mohamed

Abstract:

Job Scheduling plays an important role for efficient utilization of grid resources available across different domains and geographical zones. Scheduling of jobs is challenging and NPcomplete. Evolutionary / Swarm Intelligence algorithms have been extensively used to address the NP problem in grid scheduling. Artificial Bee Colony (ABC) has been proposed for optimization problems based on foraging behaviour of bees. This work proposes a modified ABC algorithm, Cluster Heterogeneous Earliest First Min- Min Artificial Bee Colony (CHMM-ABC), to optimally schedule jobs for the available resources. The proposed model utilizes a novel Heterogeneous Earliest Finish Time (HEFT) Heuristic Algorithm along with Min-Min algorithm to identify the initial food source. Simulation results show the performance improvement of the proposed algorithm over other swarm intelligence techniques.

Keywords: Grid Computing, Grid Scheduling, Heterogeneous Earliest Finish Time (HEFT), Artificial Bee colony (ABC) Algorithm, Resource Management.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1099196

References:

[1] Baker, M., Buyya, R., & Laforenza, D. (2002). Grids and Grid technologies for wide‐area distributed computing. Software: Practice and Experience, 32(15), 1437-1466.
[2] Foster, I. (2005). Globus toolkit version 4: Software for service-oriented systems. In Network and parallel computing (pp. 2-13). Springer Berlin Heidelberg.
[3] Garg, S. K., Buyya, R., & Siegel, H. J. (2010). Time and cost trade-off management for scheduling parallel applications on utility grids. Future Generation Computer Systems, 26(8), 1344-1355.
[4] Casavant, T. L., & Kuhl, J. G. (1988). A taxonomy of scheduling in general-purpose distributed computing systems. Software Engineering, IEEE Transactions on, 14(2), 141-154.
[5] Dong, F., & Akl, S. G. (2006). Scheduling algorithms for grid computing: State of the art and open problems. School of Computing, Queen’s University, Kingston, Ontario. 1-55.
[6] Lorpunmanee, S., Sap, M. N., Abdullah, A. H., & Chompoo-inwai, C. (2007). An ant colony optimization for dynamic job scheduling in grid environment.International Journal of Computer and Information Science and Engineering, 1(4), 207-214.
[7] Sarath Chandar A P, Priyesh V, & Doreen Hephzibah Miriam D. (2012). Grid Scheduling using Improved Particle Swarm Optimization with Digital Pheromones. International Journal of Scientific & Engineering Research, 3(6).
[8] Kennedy, J., & Eberhart, R. C. (1997, October). A discrete binary version of the particle swarm algorithm. In Systems, Man, and Cybernetics, 1997. Computational Cybernetics and Simulation., 1997 IEEE International Conference on (Vol. 5, pp. 4104-4108). IEEE.
[9] Dorigo, M., & Di Caro, G. (1999). Ant colony optimization: a new meta-heuristic. In Evolutionary Computation, 1999. CEC 99. Proceedings of the 1999 Congress on (Vol. 2). IEEE.
[10] Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms and machine learning. Machine learning, 3(2), 95-99.
[11] Cao, J., & Zimmermann, F. (2004, April). Queue scheduling and advance reservations with COSY. In Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International (p. 63). IEEE.
[12] Liu, H., Abraham, A., & Hassanien, A. E. (2010). Scheduling jobs on computational grids using a fuzzy particle swarm optimization algorithm. Future Generation Computer Systems, 26(8), 1336-1343.
[13] Somasundaram, K., & Radhakrishnan, S. (2009). Task Resource Allocation in Grid using Swift Scheduler. International Journal of Computers, Communications & Control, 4(2).
[14] Carretero, J., & Xhafa, F. (2006). Use of genetic algorithms for scheduling jobs in large scale grid applications. Technological and Economic Development of Economy, 12(1), 11-17.
[15] Grosan, C., Abraham, A., & Helvik, B. (2007). Multiobjective evolutionary algorithms for scheduling jobs on computational grids. In International Conference on Applied Computing (pp. 459-463).
[16] Coello Coello, C. A. (2006). Evolutionary multi-objective optimization: a historical view of the field. Computational Intelligence Magazine, IEEE, 1(1), 28-36.
[17] Karaboga, D., & Basturk, B. (2008). On the performance of artificial bee colony (ABC) algorithm. Applied soft computing, 8(1), 687-697.
[18] Bolaji, A. L. A., Khader, A. T., Al-Betar, M. A., & Awadallah, M. A. (2013). Artificial Bee Colony Algorithm, Its Variants and Applications: A Survey. Journal of Theoretical & Applied Information Technology, 47(2).
[19] Casanova, H., Legrand, A., Zagorodnov, D., & Berman, F. (2000). Heuristics for scheduling parameter sweep applications in grid environments. In Heterogeneous Computing Workshop, 2000.(HCW 2000) Proceedings. 9th (pp. 349-363). IEEE.
[20] Baraglia, R., Ferrini, R., & Ritrovato, P. (2005). A static mapping heuristics to map parallel applications to heterogeneous computing systems. Concurrency and Computation: Practice and Experience, 17(13), 1579-1605.
[21] Fidanova, S., & Durchova, M. (2006). Ant algorithm for grid scheduling problem. In Large-Scale Scientific Computing (pp. 405-412). Springer Berlin Heidelberg.
[22] Chen, W. N., & Zhang, J. (2009). An ant colony optimization approach to a grid workflow scheduling problem with various QoS requirements. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 39(1), 29-43.
[23] Ma, Y., & Wang, Y. (2012, December). Grid task scheduling based on Chaotic Ant Colony Optimization Algorithm. In Computer Science and Network Technology (ICCSNT), 2012 2nd International Conference on (pp. 469-472). IEEE.
[24] Garg, R., & Singh, A. K. (2013). Enhancing the Discrete Particle Swarm Optimization based Workflow Grid Scheduling using Hierarchical Structure. International Journal of Computer Network and Information Security (IJCNIS), 5(6), 18.
[25] Karimi, M., & Motameni, H. (2013). Tasks Scheduling in Computational Grid using a Hybrid Discrete Particle Swarm Optimization. International Journal of Grid & Distributed Computing, 6(2).
[26] Zhi-yun, Z., Tian, Z., Yong-tao, Z., & Li-ping, L. (2010, July). Optimization of grid resource allocation using improved particle swarm optimization algorithm. In Information Technology and Applications (IFITA), 2010 International Forum on (Vol. 3, pp. 99-103). IEEE.
[27] Tao, Q., Chang, H., Yi, Y., Gu, C., & Yu, Y. (2009, August). QoS constrained grid workflow scheduling optimization based on a novel PSO algorithm. In Grid and Cooperative Computing, 2009. GCC'09. Eighth International Conference on (pp. 153-159). IEEE.
[28] Gao, Y., Rong, H., & Huang, J. Z. (2005). Adaptive grid job scheduling with genetic algorithms. Future Generation Computer Systems, 21(1), 151-161.
[29] Khanli, L. M., Far, M. E., & Ghaffari, A. (2010). Reliable job scheduler using RFOH in grid computing. Journal of Emerging Trends in Computing and Information Sciences, 1(1), 43-47.
[30] Kashyap, R., & Vidyarthi, D. P. (2011). Security-driven scheduling model for computational Grid using genetic algorithm. In Proceedings of the World Congress on Engineering and Computer Science (Vol. 1).
[31] Kim, S. S., Byeon, J. H., Liu, H., Abraham, A., & McLoone, S. (2012). Optimal job scheduling in grid computing using efficient binary artificial bee colony optimization. Soft Computing, 1-16.
[32] elvi, V., & Umarani, R.. (2013) “Comparative Study of GA and ABC for Job Scheduling “, International Journal of Soft Computing and Engineering (IJSCE), ISSN: 2231-2307, Volume-2, Issue-6.
[33] Mandloi, S., & Gupta, H. (2013). Adaptive job Scheduling for Computational Grid based on Ant Colony Optimization with Genetic Parameter Selection. International Journal. of Advanced Computer Research (ISSN (print): 2249-7277 ISSN (online): 2277-7970) Volume- 3 Number-1 Issue-9.
[34] Xue, X., & Gu, Y. (2010). Global optimization based on hybrid clonal selection genetic algorithm for task scheduling. J Comput Inf Syst, 6(1), 253-261.
[35] Hu, C., Wu, M., Liu, G., & Xie, W. (2007, August). QoS scheduling algorithm based on hybrid particle swarm optimization strategy for grid workflow. In Grid and Cooperative Computing, 2007. GCC 2007. Sixth International Conference on (pp. 330-337). IEEE.
[36] Fidanova, S. (2006, October). Simulated annealing for grid scheduling problem. In Modern Computing, 2006. JVA'06. IEEE John Vincent Atanasoff 2006 International Symposium on (pp. 41-45). IEEE.
[37] Di Martino, V., & Mililotti, M. (2004). Sub optimal scheduling in a grid using genetic algorithms. Parallel computing, 30(5), 553-565.
[38] Pooranian, Z., Shojafar, M., Abawajy, J. H., & Singhal, M. (2013). GLOA: a new job scheduling algorithm for grid computing. International journal of interactive multimedia and artificial intelligence, 2(1), 59-64.
[39] Garg, S. K., Konugurthi, P., & Buyya, R. (2011). A linear programmingdriven genetic algorithm for meta-scheduling on utility grids. International Journal of Parallel, Emergent and Distributed Systems, 26(6), 493-517.
[40] Rao, C. S., & Babu, B. R. (2013). DE Based Job Scheduling in Grid Environments. Journal of Computer Networks, 1(2), 28-31.
[41] Zhao, H., & Sakellariou, R. (2003). An experimental investigation into the rank function of the heterogeneous earliest finish time scheduling algorithm. In Euro-Par 2003 Parallel Processing (pp. 189-194). Springer Berlin Heidelberg.
[42] Abdelkader, D. M., & Omara, F. (2012). Dynamic task scheduling algorithm with load balancing for heterogeneous computing system. Egyptian Informatics Journal, 13(2), 135-145.
[43] Tang, X., Li, K., Liao, G., Fang, K., & Wu, F. (2011). A stochastic scheduling algorithm for precedence constrained tasks on Grid. Future Generation Computer Systems, 27(8), 1083-1091.
[44] Suter, F., Desprez, F., & Casanova, H. (2004, January). From heterogeneous task scheduling to heterogeneous mixed parallel scheduling. In Euro-Par 2004 Parallel Processing (pp. 230-237). Springer Berlin Heidelberg.
[45] Braun, T.D., H. Jay Siegel, N. Beck, L.L. Boloni, M. Maheswaran, A.I. Reuther, J.P. Robertson, M.D. Theys and B. Yao, (2001). A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems. Journal of Parallel and Distributed Computing, 61: 810-837.
[46] Kıran, M. S., & Gündüz, M. (2012). A novel artificial bee colony-based algorithm for solving the numerical optimization problems. International Journal of Innovative Computing, Information & Control, 8(9), 6107- 6121.
[47] Saab, S. M., El-Omari, N. K. T., & Hussein, H. O. (2009). Developing optimization algorithm using artificial bee colony system. Ubiquitous Computing and Communication Journal, 4(3), 391-396.
[48] Mezura-Montes, E., Damián-Araoz, M., & Cetina-Domingez, O. (2010, July). Smart flight and dynamic tolerances in the artificial bee colony for constrained optimization. In Evolutionary Computation (CEC), 2010 IEEE Congress on (pp. 1-8). IEEE.
[49] Yan, G., & Li, C. (2011). An effective refinement artificial bee colony optimization algorithm based on chaotic search and application for pid control tuning. J Comput Inf Syst, 7(9), 3309-3316.
[50] Karaboga, D., & Akay, B. (2009). Artificial bee colony (ABC), harmony search and bees algorithms on numerical optimization. In Innovative Production Machines and Systems Virtual Conference.