Scheduling in Grid Systems using Ant Colony Algorithm

Full Text (PDF, 343KB), PP.16-22

Views: 0 Downloads: 0

Author(s)

Saeed Molaiy 1,* Mehdi Effatparvar 2

1. Department of Computer Engineering, Germi branch, Islamic Azad University, Germi, Iran

2. ECE Department, Ardabil branch, Islamic Azad University, Ardabil, Iran

* Corresponding author.

DOI: https://doi.org/10.5815/ijcnis.2014.02.03

Received: 1 May 2013 / Revised: 17 Aug. 2013 / Accepted: 26 Oct. 2013 / Published: 8 Jan. 2014

Index Terms

Grid systems, scheduling, response time, utilization

Abstract

Task scheduling is an important factor that directly influences the performance and efficiency of the system. Grid computing utilizes the distributed heterogeneous resources in order to support complicated computing problems. Grid can be classified into two types: computing grid and data grid. Job scheduling in computing grid is a very important problem. To utilize grids efficiently, we need a good job scheduling algorithm to assign jobs to resources in grids. This paper presents a new algorithm based on ant colony optimization (ACO) metaheuristic for solving this problem. In this study, a proposed ACO algorithm for scheduling in Grid systems will be presented. Simulation results indicate our ACO algorithm optimizes total response time and also it increase utilization.

Cite This Paper

Saeed Molaiy, Mehdi Effatparvar, "Scheduling in Grid Systems using Ant Colony Algorithm", International Journal of Computer Network and Information Security(IJCNIS), vol.6, no.2, pp.16-22, 2014. DOI:10.5815/ijcnis.2014.02.03

Reference

[1]Heusse, M., S. Guerin, D. Snyersy and P. Kuntz, 1998. A new distributed and adaptive approach to routing and load balancing in dynamic communication networks. University of Washington.
[2]Salehi, M.A. and H. Deldari, 2006. Grid load balancing using an echo system of intelligent ants. Proceedings of the 24th IASTED International Conference on Parallel and Distributed Computing and Networks, Feb. 14-16, ACTA Press, Innsbruck, Austria, Anaheim, CA, USA., pp: 47-52.
[3]Sim, K.M. and W.H. Sun, 2003b. Ant colony optimization for routing and load-balancing: Survey and new directions. IEEE Trans. Syst. Man Cybern.-Part A: Syst. Hum., 33: 560-572.
[4]Sim, K.M. and W.H. Sun, 2003a. Multiple ant colony optimization for load balancing. Lecture Notes Comput. Sci., 2690: 467-471. DOI: 10.1007/b11717.
[5]Bulancea, C., B. Paechter and A. Carter, 1996. Using ACO metaheuristics on load balancing algorithm. Trans. Syst. Man Cybernet.
[6]A. Colorni, M. Dorigo et V. Maniezzo, Distributed Optimization by Ant Colonies, actes de la première conférence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134-142, 1991.
[7]M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.
[8]Tarasewich, P. and P.R. McMullen, 2002. Swarm intelligence: Powers in numbers. Commun. ACM, 45: 62-67.
[9]Krohn, J., 2001. Ant algorithms and the swarm intelligence model of problem solving. Proceedings of the Conference on the UMM Computer Science Discipline Seminar, (CCSDS’01), UMM University of Minesota Morris, Morris, pp: 1-6.
[10]Colorni, A., M. Dorigo and V. Maniezzo, 1992. Distributed optimization by ant colonies. Proceeding of the 1st European Conference on Artificial Life, (ECAL’92), Elsevier Publishing, Paris, France, pp: 134-142.
[11]Merkle, D., M. Middendorf H. Schmeck, 2000. Pheromone evaluation in ant colony optimization. Proceedings of the 26th Annual IEEE International Conference on Industrial Electronics, Control and Instrumentation, Oct. 22- 28, IEEE Xplore Press, Nagoya, Japan, pp: 2726-2731.
[12]Middendorf, M., F. Reischle and H. Schmeck, 2000. Information exchange in multi colony ant algorithms. Lecture Notes Comput. Sci., 1800: 645-652. DOI: 10.1007/3-540-45591-4_87.
[13]Siriluck Lorpunmanae, Mohd Noor Sap, Abdul Hanan Abdullah and Aboamama Atahar Ahmed, “Multi-Constraint Dynamic Scheduling of Indepent jobs onto Grid Environment”, Jurnal Teknologi Maklumat, 2007.
[14]Kousalya.K and Subramanie.P, “Ant algorithms for Grid Scheduling Powered by local search”, IEEE International Journal, 2008.
[15]Huiyan, Xue-Qin-Shein, Xing Li, Ming-Hui Wu, “An Improved Ant Algorithm for Job Scheduling in Grid Computing”, 18-21 August 2005.
[16]Li Liu, Yi Yang, Lian Li and Wanbin Shi, “Using Ant Colony Optimization for SuperScheduling in Computational Grid”, Proceedings of the 2006 IEEE Asia-Pacific Conference on Services Computing (APSCC'06), 2006.
[17]H. Yan, X. Shen, X. Li and M. Wu, “An Improved Ant Algorithm for Job Scheduling in Grid Computing”, In Proceedings of the Fourth International Conference on Machine Learning and Cybernetics, 18-21 August 2005.
[18]D. Klus´aˇ cek, L. Matyska, and H. Rudov´a, “Grid scheduling simulation environment”, Submitted to MISTA, 3rd Multidisciplinary International Scheduling Conference: Theory and Applications, France, 2007.
[19]T. D. Braun, H. J. Siegel, N. Beck, L. L. Bölöni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, B. Yao, D. Hensgen and R. F. Freund (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. Vol.61 (6): Pages 810-837.
[20]C. Ernemann , V. Hamscher and R. Yahyapour, “Benefits of Global Grid Computing for Job Scheduling”, Proceedings of the Fifth IEEE/ACM International Workshop on Grid Computing (GRID’04), 2004.
[21]R. Buyya and M. Murshed, “GridSim: A toolkit for the modeling and simulation of distributed resource management and scheduling for Grid computing”, The Journal of Concurrency and Computation: Practice and Experience (CCPE), 14:1175-1220, 2002.
[22]P. Fibich, L. Matyska, and H. Rudov´a, “Model of Grid Scheduling Problem”, In Exploring Planning and Scheduling for Web Services, Grid and Autonomic Computing, Papers from the AAAI-05 workshop. Technical Report WS-05-03, AAAI Press, 2005.
[23]R. Baraglia, R. Ferrini, and P. Ritrovato, “A static mapping heuristics to map parallel applications to heterogeneous computing systems”, Research articles. Concurrency and Computation: Practice and Experience, 17(13):1579–1605, 2005.
[24]Shih-Tang, L., C. Ruey-Maw, H. Yueh-Min and W. Chung-Lun, 2008. Multiprocessor system scheduling with precedence and resource constraints using an enhanced ant colony system. Expert Syst. Appli., 34: 2071-2081. DOI: 10.1016/j.eswa.2007.02.022.
[25]Braun, D.T., H.J. Siegel, N. Beck, L.L. Boloni and M. Maheswaran et al., 2001. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J. Parallel Distributed Computer, 61: 810-837. DOI: 10.1006/jpdc.2000.1714.