Abstract

In this study, we have proposed a novel perspective for grid scheduling which aims at decreasing the makespan of the submitted jobs and increasing the utilization of resources involved. Grid scheduling is mapping jobs to grid resources at specific time intervals. Efficient scheduling is crucial to achieve excellent performance through grid computation. Meta-heuristics techniques are used, as grid scheduling is an NP-complete problem. Literature proposes genetic algorithm based heuristics and swarm based optimizations for grid scheduling. This study aims at using meta-heuristics techniques for the scheduling problem to reduce the Make span of task submitted to grid. Artificial Bee Colony (ABC) is selected for optimizing the scheduling due to its simplicity, flexibility and robustness. We have proposed Cluster Heterogeneous Min-Min Artificial Bee Colony (CHMM-ABC) and also a Hybrid ABC algorithm with reactive tabu search for efficient grid scheduling. Also the relationships between initial population and ABCs final outcome have been investigated in this study. Simulation confirms the efficiency of the suggested new approach. The proposed method reaches low makespan in the first run as initial swarm is created by the new CHEFT and Min-Min algorithm with RTS. Simulation reveals a make span decrease of 9.87 % to 13.32 % achieved by the new RTS- ABC compared to classic ABC.

Keywords:

Artificial Bee Colony (ABC), grid scheduling , meta-heuristics , makespan,

References

1. Abraham, A., H. Liu, W. Zhang and T.G. Chang, 2006. Scheduling Jobs on Computational Grids Using Fuzzy Particle Swarm Algorithm. In: Gabrys, B., R.J. Howlett and L.C. Jain (Eds.), Knowledge-Based Intelligent Information and Engineering Systems. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 4252: 500-507.
   CrossRef    
2. Abraham, A., H. Liu, C. Grosan and F. Xhafa, 2008. Nature Inspired Meta-Heuristics for Grid Scheduling: Single and Multi-Objective Optimization Approaches. In: Xhafa, F. and A. Abraham (Eds.), Metaheuristics for Scheduling in Distributed Computing Environments. Studies in Computational Intelligence, Springer, Berlin, Heidelberg, 146: 247-272.
   CrossRef    
3. Alyaseri, S. and K.R. Ku-Mahamud, 2013. Bee foraging behaviour techniques for grid scheduling problem. Int. Refereed J. Eng. Sci., 2(4): 39-45.
   
4. Arsuaga-Ríos, M., M.A. Vega-Rodríguez and F. Prieto-Castrillo, 2011. Multi-objective artificial bee colony for scheduling in grid environments. Proceeding of the IEEE Symposium on Swarm Intelligence (SIS, 2011). Paris, pp: 1-7.
   CrossRef    
5. Barzegar, B., A.M. Rahmani, K. Zamanifar and A. Divsalar, 2009. Gravitational emulation local search algorithm for advanced reservation and scheduling in grid computing systems. Proceeding of the 4th International Conference on Computer Sciences and Convergence Information Technology (ICCIT'09). Seoul, pp: 1240-1245.
   CrossRef    
6. Battiti, R. and G. Tecchiolli, 1994. The reactive tabu search. ORSA J. Comput., 6(2): 126-140.
   CrossRef    
7. Benedict, S. and V. Vasudevan, 2008. Improving scheduling of scientific workflows using tabu search for computational grids. Inf. Technol. J., 7(1): 91-97.
   CrossRef    
8. Bolaji, A.L.A., A.T. Khader, M.A. Al-Betar and M.A. Awadallah, 2013. Artificial bee colony algorithm, its variants and applications: A survey. J. Theor. Appl. Inf. Technol., 47(2): 434-459.
   
9. Carretero, J. and F. Xhafa, 2006. Use of genetic algorithms for scheduling jobs in large scale grid applications. Technol. Econ. Dev. Econ., 12(1): 11-17.
   
10. Chang, R.S., J.S. Chang and P.S. Lin, 2009. An ant algorithm for balanced job scheduling in grids. Future Gener. Comp. Sy., 25(1): 20-27.
    CrossRef    
11. Chauhan, S.S. and R.C. Joshi, 2010. QoS guided heuristic algorithms for grid task scheduling. Int. J. Comput. Appl., 2(9): 24-31.
    CrossRef    
12. Chen, R.M. and C.M. Wang, 2011. Project scheduling heuristics-based standard PSO for task-resource assignment in heterogeneous grid. Abstr. Appl. Anal., 2011: 1-20.
    CrossRef    
13. Coello, C.A.C., 2006. Evolutionary multi-objective optimization: A historical view of the field. IEEE Comput. Intell. M., 1(1): 28-36.
    CrossRef    
14. El-Rewini, H., T.G. Lewis and H.H. Ali, 1994. Task Scheduling in Parallel and Distributed Systems. Prentice-Hall, Upper Saddle River, NJ, USA.
    
15. Fayad, C., J.M. Garibaldi and D. Ouelhadj, 2007. Fuzzy grid scheduling using tabu search. Proceeding of the IEEE International Fuzzy Systems Conference. London, pp: 1-6.
    CrossRef    
16. Gharooni-Fard, G., F. Moein-Darbari, H. Deldari and A. Morvaridi, 2010. Scheduling of scientific workflows using a chaos-genetic algorithm. Proc. Comput. Sci., 1(1): 1445-1454.
    CrossRef    
17. Grosan, C., A. Abraham and B. Helvik, 2007. Multiobjective evolutionary algorithms for scheduling jobs on computational grids. Proceeding of the International Conference on Applied Computing.
    
18. He, X., X. Sun and G. Von Laszewski, 2003. QoS guided min-min heuristic for grid task scheduling. J. Comput. Sci. Technol., 18(4): 442-451.
    CrossRef    
19. Izakian, H., B.T. Ladani, K. Zamanifar and A. Abraham, 2009. A Novel Particle Swarm Optimization Approach for Grid Job Scheduling. In: Prasad, S.K. et al. (Eds.), Information Systems, Technology and Management. Communications in Computer and Information Science, Springer, Berlin Heidelberg, 31: 100-109.
    CrossRef    
20. Kamalam, G.K. and V. Muralibhaskaran, 2010. A new heuristic approach: Min-mean algorithm for scheduling meta-tasks on heterogenous computing systems. Int. J. Comput. Sci. Netw. Secur., 10(1): 24-31.
    
21. Karaboga, D. and B. Basturk, 2008. On the performance of artificial bee colony (ABC) algorithm. Appl. Soft Comput., 8(1): 687-697.
    CrossRef    
22. Kiran, M.S. and M. Gündüz, 2012. A novel artificial bee colony-based algorithm for solving the numerical optimization problems. Int. J. Innov. Comput. I., 8(9): 6107-6121.
    
23. Kokilavani, T. and D.I.G. Amalarethinam, 2011. Load balanced min-min algorithm for static meta-task scheduling in grid computing. Int. J. Comput. Appl., 20(2): 43-49.
    
24. Ku-Mahamud, K.R. and H.J. Abdul Nasir, 2010. Ant colony algorithm for job scheduling in grid computing. Proceeding of the 4th Asia International Conference on Mathematical/Analytical Modelling and Computer Simulation (AMS). Kota Kinabalu, Malaysia, pp: 40-45.
    CrossRef    
25. Lorpunmanee, S., M.N. Sap, A.H. Abdullah and C. Chompoo-Inwai, 2007. An ant colony optimization for dynamic job scheduling in grid environment. Int. J. Comput. Electr. Autom. Control Inform. Eng., 1(5): 1343-1350.
    
26. Lu, E., Z. Xu and J. Sun, 2004. An Extendable Grid Simulation Environment Based on GridSim. In: Li, M. et al. (Eds.), Grid and Cooperative Computing. Lecture Notes in Computer Science, Springer, Berlin Heidelberg, 3032: 205-208.
    CrossRef    
27. Mathiyalagan, P., U.R. Dhepthie and S.N. Sivanandam, 2010. Grid scheduling using enhanced PSO algorithm. Int. J. Comput. Sci. Eng., 2(2): 140-145.
    
28. Miriam, D.D.H. and K.S. Easwarakumar, 2010. A double min min algorithm for task metascheduler on hypercubic p2p grid systems. Int. J. Comput. Sci. Issue, 7(4): 8-18.
    
29. Mousavinasab, Z., R. Entezari-Maleki and A. Movaghar, 2011. A Bee Colony Task Scheduling Algorithm in Computational Grids. In: Snasel, V., J. Platos and E. El-Qawasmeh (Eds.), Digital Information Processing and Communications. Communications in Computer and Information Science, Springer, Berlin Heidelberg, 188: 200-210.
    CrossRef    
30. Nallusamy, C., A. Sabari and K. Suganya, 2015. Appraisal on Link Lifetime Prediction Using Geographical Information. Int. J. Environ. Chem. Ecol. Geol. Geophys. Eng., 8(11): 735-738.
    
31. Omara, F.A. and M.M. Arafa, 2010. Genetic algorithms for task scheduling problem. J. Parallel Distr. Com., 70(1): 13-22.
    CrossRef    
32. Pooranian, Z., M. Shojafar, J.H. Abawajy and A. Abraham, 2013. An efficient meta-heuristic algorithm for grid computing. J. Comb. Optim., 30(3): 413-434.
    CrossRef    
33. Raj, R.J.S. and V. Vasudevan, 2011. Beyond simulated annealing in grid scheduling. Int. J. Comput. Sci. Eng., 3(3): 1312-1318.
    
34. Ruda, M. and H. Rudová, 2005. Grid scheduling and monitoring. Proceeding of the 4th Annual Workshop of the UK Planning and Scheduling Special Interest Group (PLANSIG'05), pp: 98-99.
    
35. SarathChandar, A.P., V. Priyesh and D. Doreen Hephzibah Miriam, 2012. Grid scheduling using improved particle swarm optimization with digital pheromones. Int. J. Sci. Eng. Res., 3(6): 1-6.
    
36. Singh, M. and P.K. Suri, 2008. QPSMax-MinMin-Min: A QoS based predictive max-min, min-min switcher algorithm for job scheduling in a grid. Inform. Technol. J., 7(8): 1176-1181.
    CrossRef    
37. Somasundaram, K. and S. Radhakrishnan, 2009. Task resource allocation in grid using swift scheduler. Int. J. Comput. Commun., 4(2): 158-166.
    CrossRef    
38. Suter, F., F. Desprez and H. Casanova, 2004. From heterogeneous task scheduling to heterogeneous mixed parallel scheduling. In: Danelutto, M., M. Vanneschi and D. Laforenza (Eds.), Euro-Par 2004 Parallel Processing. Lecture Notes in Computer Science, Springer, Berlin Heidelberg, 3149: 230-237.
    CrossRef    
39. Taheri, J., Y.C. Lee, A.Y. Zomaya and H.J. Siegel, 2013. A bee colony based optimization approach for simultaneous job scheduling and data replication in grid environments. Comput. Oper. Res., 40(6): 1564-1578.
    CrossRef    
40. Tao, Q., H. Chang, Y. Yi and C. Gu, 2010. A grid workflow scheduling optimization approach for e-Business application. Proceeding of the International Conference on E-Business and E-Government (ICEE, 2010). Guangzhou, pp: 168-171.
    CrossRef    
41. Vigneswari, T. and M.A. Maluk Mohamed, 2014a. Scheduling in sensor grid middleware for telemedicine using ABC algorithm. Int. J. Telemed. Appl., 2014: 7.
    CrossRef    PMid:25548557 PMCid:PMC4273462    
42. Vigneswari, T. and M.A. Maluk Mohamed, 2014b. Performance analysis of initialization methods for optimizing artificial bee colony grid scheduling. Proceeding of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA). The Steering Committee of the World Congress in Computer Science, Computer Engineering and Applied Computing (WorldComp), pp: 1-7.
    PMCid:PMC4273462    
43. Vigneswari, T. and M.A. Maluk Mohamed, 2014c. Optimal grid scheduling using improved artificial bee colony algorithm. Int. J. Comput. Electr. Autom. Control Inform. Eng., 8(11): 2065-2073.
    
44. Vivekanandan, K., D. Ramyachitra and B. Anbu, 2011. Artificial bee colony algorithm for grid scheduling. J. Converg. Inf. Technol., 6(7): 328-339.
    
45. Wieczorek, M., R. Prodan and T. Fahringer, 2005. Scheduling of scientific workflows in the ASKALON grid environment. SIGMOD Rec., 34(3): 56-62.
    CrossRef    
46. Xu, Z., X. Hou and J. Sun, 2003. Ant algorithm-based task scheduling in grid computing. Proceeding of the Canadian Conference on Electrical and Computer Engineering (IEEE CCECE, 2003), 2: 1107-1110.
    
47. Yan, H., X.Q. Shen, X. Li and M.H. Wu, 2005. An improved ant algorithm for job scheduling in grid computing. Proceeding of the International Conference on Machine Learning and Cybernetics. Guangzhou, China, 5: 2957-2961.
    
48. Yusof, M.K. and M.A. Stapa, 2010. Achieving of tabu search algorithm for scheduling technique in grid computing using GridSim simulation tool: Multiple jobs on limited resource. Int. J. Grid Distrib. Comput., 3(4): 19-32.
    
49. Zhang, L., Y. Chen, R. Sun, S. Jing and B. Yang, 2008. A task scheduling algorithm based on PSO for grid computing. Int. J. Comput. Intell. Res., 4(1): 37-43.
    CrossRef    
50. Zhu, Y. and Q. Wei, 2010. An improved ant colony algorithm for independent tasks scheduling of grid. Proceeding of the 2nd International Conference on Computer and Automation Engineering (ICCAE, 2010). Singapore, 2: 566-569.
    

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.