Optimal Grid Scheduling Using Improved Artificial Bee Colony Algorithm
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:69019", author = "T. Vigneswari and M. A. Maluk Mohamed", title = "Optimal Grid Scheduling Using Improved Artificial Bee Colony Algorithm", 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.", volume = "8", number = "11", pages = "2070-9", }
