An Optimal ANT Algorithm for Balanced Scheduling in Computing Grids

K.Jairam Naik*, A.Jagan**, N. Satya Narayana***
* Assistant Professor, Department of Computer Science and Engineering, Vasavi College of Engineering, Hyderabad, Telangana, India.
** Professor, Department of Computer Science and Engineering, Dr. BV Raju Institute of Technology, Narsapur, Telangana, India.
*** Professor, Department of Computer Science and Engineering, Nagole Institute of Technology and Science, Hyderabad, Telangana, India.
Periodicity:October - December'2015
DOI : https://doi.org/10.26634/jse.10.2.3731

Abstract

Grid computing relies on distributed heterogeneous resources to support convoluted computing problems. Grids are mainly classified into computing grid and data grid. Scheduling the jobs in computing grid is a very big obstacle. For efficient and incentive based use of grid resources, optimal mechanism in grids is needed that can distribute jobs to the prime resources and balance work load among them. In the real world, the ants have an unique ability to team up for finding an optimal path for food resources. The behavior of real ants was simulated by an Ant algorithm. In this paper, the authors proposed an optimized Ant algorithm for balanced job scheduling in the computing grid environment. The primary goal of the approach is to schedule and balance the entire system load, so that no resource is overloaded or under loaded under any circumstances. To achieve the primary goal, a Novel Balanced Ant Colony Optimization (NBACO) always calculates and updates local and global pheromone values, which makes the resource always normally loaded. The secondary aim is to considerably improve grid performance in terms of increased throughput, reduced makespan and resubmission time. To achieve this goal, NBACO always finds the most successive available resources in the grid and assigns the job to it. The successive resource is the one, which has the lower tendency to fail. According to the experimental results, NBACO can outperform other job scheduling and load balancing algorithms.

Keywords

Computing Grid, Resources, Success Rate, Scheduler, Load Balancing, Pheramone Indicator.

How to Cite this Article?

Naik, K. J., Jagan, A., and Narayana, N. S. (2015). An Optimal ANT Algorithm for Balanced Scheduling in Computing Grids. i-manager’s Journal on Software Engineering, 10(2), 6-19. https://doi.org/10.26634/jse.10.2.3731

References

[1]. D. Saha, D. Menasce, and S. Porto, (1995). “Static and dynamic processor scheduling disciplines in heterogeneous parallel architectures”, Journal of Parallel and Distributed Computing, Vol.28(1), pp.1–18.
[2]. H. Yan, X. Qin, X. Li, and M.-H. Wu, (2005). “An improved ant algorithm for job scheduling in grid computing”, Proceedings of 2005 International Conference on Machine Learning and Cybernetics, Vol.5, pp.2957–2961.
[3]. M. Dorigo, and C. Blum, (2005). “Ant colony optimization theory: A survey”, Theoretical Computer Science, Vol.344(2–3), pp.243–278.
[4]. F. Dong, and S.K. Akl, (2006). “Scheduling algorithms for grid computing: State of the art and open problems”, Technical Report No. 2006-504, School of Computing, Queen's University, Kingston, Ontario, Canada.
[5]. Ruay-Shiung Chang, Jih-Sheng Chang, and Po- Sheng Lin, (2009). “An ant algorithm for balanced job scheduling in grids”, Elsevier/Future Generation Computer Systems, Vol.25, pp.20–27.
[6]. K. Jairam Naik, (2012). “Scheduling Tasks on Most Suitable Fault tolerant Resource for Execution in Comp. Grid”, IJGDC, Vol.5, No.3, pp.121–132.
[7]. K. Jairam Naik, (2013). “A Novel Fault-tolerant Task Scheduling Algorithm for Comp”, Grids, (15th ICACT- 978-1-4673- 2818-0/13 ©2013 IEEE).
[8]. D. Kondo, D.P. Anderson, and J. McLeod, (2007). “Performance evaluation of scheduling policies for volunteer computing”, Proc. IEEE International Conference on e-Science and Grid Computing, pp.415–422.
[9]. M. Dorigo, Ant Colony Optimization, Retrieved from http://www.aco-metaheuristic.org.
[10]. BOINC website. Retrieved from http://boinc. berkeley.edu/.
[11]. D. Paranhos, W. Cirne, and F. Brasileiro, (2003). “Trading cycles for information: Using replication to schedule bag-of-tasks applications on computational grids”, International Conference on Parallel and Distributed Computing (Euro-Par), Lecture Notes in Computer Science, Vol.2790, pp.169–180.
[12]. M. Dorigo, and L.M. Gambardella, (1997). “Ant colony system: A cooperative learning ap-proach to the traveling salesman problem”, IEEE Transactions on Evolutionary Computation, Vol.1(1), pp.53–66.
[13]. E.D. Taillard, and L.M. Gambardella, (1997). “Adaptive memories for the quadratic assign-ment problem”, Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland.
[14]. T. Stutzle, (1997). MAX-MIN Ant System for Quadratic Assignment Problems, Technical Report AIDA-97-04, Intellectics Group, Department of Compute Science, Darmstadt University of Technology, Germany.
[15]. R. Buyya, and M. Murshed, (2012). “GridSim: Practice and Experience”,14(2002)13–15 , Y.Haoetal./FGCS, Vol.28, pp.657–665 665.
[16]. F. Howell, (1998). “SimJava: a discrete Java event simulation package with appl. in comp. sys. modeling”, 1st Intnl Conf on Web-based Modelling and Simulation, Society for Comp. Simulation, SanDiego, CA.
[17]. Huda M, Schmidt H, and Peake I., (2005). “An agent oriented proactive fault-tolerant framework for grid computing”, Proceedings of International Conference on E-Science and Grid Computing, Melbourne, Australia, Vol.5–8, pp.304–11.
[18]. M. Dorigo, V. Maniezzo, and A. Colorni, (1996). “The ant system: Optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man, and Cybernetics, Part B, Vol.26(1), pp.29–41.
[19]. Jianfu Li, and Wei Zhang, (2006). “Solution to multiobjective optimization of flow shop problem based on ACO algorithm”, Proceeding of 2006 International Conference Computational Intelligence and Security, Vol.1, pp.417–420.
[20]. E. Burke, G. Kendall, Silva Landa, R. O'Brien, and E. Soubeiga, (2005). “An ant algorithm hyperheuristic for the project presentation scheduling problem”, IEEE Congress on Evolutionary Computing, Vol.3, pp.2263–2270.
[21]. Xiaoxia Zhang, and Lixin Tang, (2005). “CTACO— hybridizing ant colony optimization with cycle transfer search for the vehicle routing problem”, Congress on Computational Intelligence Methods and Applications, 15–17, pp.6.
[22]. E. Salari, K. Eshghi, (2005). “An ACO algorithm for graph coloring problem”, Congress on Computational Intelligence Methods and Applications, Vol.15–17, pp.5.
[23]. J. Heinonen, and F. Pettersson, (2005). “Hybrid ant colony optimization and visibility studies applied to a jobshop scheduling problem”, Applied Mathematics and Computation, Vol.187(2), pp.989–998.
[24]. Kwang Mong Sim, and Weng Hong, Sun, (2005). “Multiple ant-colony optimization for network routing”, in: Proceedings of the First International Symposium on Cyber Worlds, Vol.6–8, pp.277–281.
[25]. Robert G. Bland, Donald Goldfarb, and Michael J. Todd, (1981). “Ellipsoid method, a survey”, Operations Research, Vol.29(6), pp.1039–1091.
[26]. V. Sarkar, (1989). “Determining average program execution times and their variance”, Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pp.298–312.
[27]. C.Y. Park, (1993). “Predicting program execution times by analyzing static and dynamic program paths”, Real-Time Systems, Vol.5(1), pp.31–62
[28]. J. Engblom, and A. Ermedahl, (2000). “Modeling complex flows for worst-case execution time analysis”, Proceedings of the 21st IEEE Real-Time Systems Symposium, pp.163–174.
[29]. F. Stappert, and P. Altenbernd, (2000). “Complete worst-case execution time analysis of straight-line hard real-time programs”, Journal of Systems Architecture, Vol.46(4), pp.339–355.
[30]. M. Maheswaran, S. Ali, H.J. Siegel, D. Hensgen, and R. Freund, (1999). “Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing system”, Journal of Parallel and Distributed Computing, Vol.59, pp.107–131.
[31]. B. Bullnheimer, R.F. Hartl, and C. Strauss, (1999). “A new rank-based version of the ant system: A computational study”, Central European Journal for Operations Research and Economics, Vol.7(1), pp.25–38.
If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Single Article

North Americas,UK,
Middle East,Europe
India Rest of world
USD EUR INR USD-ROW
Online 15 15

Options for accessing this content:
  • If you would like institutional access to this content, please recommend the title to your librarian.
    Library Recommendation Form
  • If you already have i-manager's user account: Login above and proceed to purchase the article.
  • New Users: Please register, then proceed to purchase the article.