Research Article | OPEN ACCESS
Improved Grid Scheduling Using Hybrid Heuristic Algorithms with Enhanced Initial Solutions
1, 2T. Vigneswari and 1M.A. Maluk Mohamed
1M.A.M. College of Engineering, Tiruchirappalli, 612005
2Kings College of Engineering, Punalkulam, 613303, India
Research Journal of Applied Sciences, Engineering and Technology 2016 1:30-41
Received: November 21, 2015 | Accepted: March 5, 2016 | Published: July 05, 2016
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
-
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 -
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 -
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.
-
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 -
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 -
Battiti, R. and G. Tecchiolli, 1994. The reactive tabu search. ORSA J. Comput., 6(2): 126-140.
CrossRef -
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 -
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.
-
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.
-
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 -
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 -
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 -
Coello, C.A.C., 2006. Evolutionary multi-objective optimization: A historical view of the field. IEEE Comput. Intell. M., 1(1): 28-36.
CrossRef -
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.
-
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 -
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 -
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.
-
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 -
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 -
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.
-
Karaboga, D. and B. Basturk, 2008. On the performance of artificial bee colony (ABC) algorithm. Appl. Soft Comput., 8(1): 687-697.
CrossRef -
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.
-
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.
-
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 -
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.
-
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 -
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.
-
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.
-
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 -
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.
-
Omara, F.A. and M.M. Arafa, 2010. Genetic algorithms for task scheduling problem. J. Parallel Distr. Com., 70(1): 13-22.
CrossRef -
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 -
Raj, R.J.S. and V. Vasudevan, 2011. Beyond simulated annealing in grid scheduling. Int. J. Comput. Sci. Eng., 3(3): 1312-1318.
-
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.
-
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.
-
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 -
Somasundaram, K. and S. Radhakrishnan, 2009. Task resource allocation in grid using swift scheduler. Int. J. Comput. Commun., 4(2): 158-166.
CrossRef -
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 -
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 -
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 -
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 -
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 -
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.
-
Vivekanandan, K., D. Ramyachitra and B. Anbu, 2011. Artificial bee colony algorithm for grid scheduling. J. Converg. Inf. Technol., 6(7): 328-339.
-
Wieczorek, M., R. Prodan and T. Fahringer, 2005. Scheduling of scientific workflows in the ASKALON grid environment. SIGMOD Rec., 34(3): 56-62.
CrossRef -
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.
-
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.
-
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.
-
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 -
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.
|
|
![](http://www.maxwellsci.com/images/RJASET-maxw.jpg) |
ISSN (Online): 2040-7467
ISSN (Print): 2040-7459 |
![Submit Manuscript](../images/sub.jpg) |
Information |
|
|
|
Sales & Services |
|
|
|