Abstract
Resource Management in Grid computing system is a fundamental issue in achieving high performance due to the distributed and heterogeneous nature of the resources. The efficiency and effectiveness of Grid resource management greatly depend on the scheduling algorithm. In this paper, the problem of scheduling is represented by a weighted directed acyclic graph (DAG). Ant Colony Optimization is used for scheduling tasks on resources in Grid which simultaneously pay attention to two objectives of makespan (schedule length) and the failure probability (reliability). These objectives are conflicting and it is not possible to minimize both objectives at the same time. With the help of concept of non-dominance, we are able to choose a trade-off between makespan minimization and reliability maximization. For evaluating the algorithm, ACO is compared with NSGA-II. The metrics for evaluating the convergence and diversity of the obtained non-dominated solutions by the two algorithms are reported. The results of simulation using JAVA programming language manifest that proposed approach can be used more efficiently for allocating the tasks as compared to NSGA-II.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Foster, I., Kesselman, C., Tuecke, S.: The anatomy of the grid. Int. J. Supercomput. Appl. 15(3) (2001)
Topcuoglu, H., Hariri, S., Wu, M.Y.: Performance-effective and low complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst. 13(3), 260–274 (2002)
Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53–66 (1997)
Salari, E., Eshghi, K.: An ACO algorithm for graph coloring problem. In: Conference on Computational Intelligence Methods and Applications, December 2005
Zhang, X., Tang, L.: CT-ACO-hybridizing ant colony optimization with cycle transfer search for the vehicle routing problem. In: Conference on Computational Intelligence Methods and Applications, December 2005
Maheswaran, M., Ali, S., Siegel, H.J., Hensgen, D., Freund, R.: Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing system. J. Parallel Distrib. Comput. 59, 107–131 (1999)
Xhafa, F., Abraham, A.: Computational models and heuristic methods for grid scheduling problems. J. Future Gener. Comput. Syst. 26, 608–621 (2010)
Ye, G., Rao, R., Li, M.: A multiobjective resources scheduling approach based on genetic algorithms in grid environment. In: 5th International Conference on Grid and Cooperative Computing Workshops. pp. 504–509 (2006)
Dai, Y.S., Levitin, G.: Performance and reliability of tree structured grid services considering data dependence and failure correlation. IEEE Trans. Comput. 56(7), 925–936 (2007)
Sallim, J., Shahrir, W.M., Hussin, W.: A background study on ant colony optimization metaheuristic and its application principles in resolving three combinatorial optimization problems. In: National Conference on Software Engineering and Computer Systems, Legend Resort Kuantan (2007)
Tang, X., Li, K., Li, R., Veeravalli, B.: Reliability-aware scheduling strategy for heterogeneous distributed computing systems. J. Parallel Distrib. Comput. 70, 941–952 (2010)
Liu, G.Q., Poh, K.L., Xie, M.: Iterative list scheduling for heterogeneous computing. J. Parallel Distrib. Comput. 65(5), 654–665 (2005)
Mazurek, M., Wesolkowski, S.: Non-dominated sorting on two objectives. Defence R&D Canada—CORA, Technical Note 027, pp. 1–13, July 2009
Deb, K.: Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, New York (2001). ISBN: 0-471-87339-X
Deb, K., Jain, S.: Running performance metrics for evolutionary multi-objective optimization. In: Simulated Evolution and Learning, pp. 13–20 (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer India
About this paper
Cite this paper
Nitu, Garg, R. (2014). Multi-Objective Ant Colony Optimization for Task Scheduling in Grid Computing. In: Pant, M., Deep, K., Nagar, A., Bansal, J. (eds) Proceedings of the Third International Conference on Soft Computing for Problem Solving. Advances in Intelligent Systems and Computing, vol 259. Springer, New Delhi. https://doi.org/10.1007/978-81-322-1768-8_12
Download citation
DOI: https://doi.org/10.1007/978-81-322-1768-8_12
Published:
Publisher Name: Springer, New Delhi
Print ISBN: 978-81-322-1767-1
Online ISBN: 978-81-322-1768-8
eBook Packages: EngineeringEngineering (R0)