Population based Heuristic Approaches for Grid Job Scheduling

Abstract

Several strategies and approaches have been proposed to provide quality solutions for the grid job scheduling problem. Recently population based heuristics approaches are used widely to solve this problem. These approaches have demonstrated a surprising degree of effectiveness for handling combinatorial optimization problems. In this paper, the population based approaches for grid job scheduling have been studied. The focus was on investigating the criteria that help in the selection of the best scheduling algorithm for a certain type of grid and also shedding the light on how to improve the available population based approaches.

References

• Dabas, P. & Arya, A. (2013). Grid computing: An introduction. International journal of advanced research in computer science and software engineering. 3(3), 2013.
• Chandak, A. , Sahoo, B. & Turuk, A. (2011). Heuristic task allocation strategies for computational grid. International Journal advanced networking and applications, 5(2), 804-810.
• Kaur, A. & Goyal, S. (2011). A survey on the applications of bee colony optimization techniques. International journal on computer science and engineering (IJCSE), 8(3) August 2011.
• Xhafa, F. & Abraham, A. (2008), Meta-heuristics for grid scheduling problems. F. Xhafa, A. Abraham (Eds. ). Meta for scheduling in distributed Computer Environment, SCI 146, 2008, pp. 1-37, springer-verlag Berlin Heidelberg.
• Malarizhi, N. & Uthariaraj, V. (2012). Comparison of resource scheduling in centralized, decentralized and hybrid grid environment. International journal of emerging technology and advanced engineering, 2(7), 382-388, July 2012.
• Schopf , J. (2002). A General architecture for scheduling on the grid. Special issue of JPDC on grid computing, 2002,1000-1002.
• Dong, F. & Akl, S. (2006). Scheduling algorithms for grid computing: state of the arts and open problems, Technical Report No. 2006-504, School of Computing, Queen's University Kingston, Ontario, January 2006.
• Berman, F. (1998). High-performance schedulers. In Ed. By Foster I. & Kesselman, C. Kaufman, M. publishers, the grid: blue print for a future computing infrastructures, 1998.
• Raju, M. & Divya, T. and Rao, T. (2010). Efficient resource scheduling in data grid. Proceedings of the international conference on information science and applications ICISA, 2010, Chennai, India
• Kaur, G. (2008). Makespan optimization algorithm for scheduling in grid. Msc thesis, Thapar university, Patiala, India, 2008.
• Koulouzis, S. , Wood, T. & Groen, D. (2006). An Investigation into the Use of Genetic Algorithms for Grid Scheduling.
• Deb, K. (1997). Genetic Algorithm in Search and Optimization: The Technique and Applications. Proceeding of International Workshop on Soft Computing and Intelligent System, pp. 58-87, 1997.
• Abraham, A. , Buyya, R. & Nath, B. (2000). Nature's heuristics for scheduling job on computational grids. In Proceeding of 8th IEEE International Conference on Advanced Computing and Communications (ADCOM 2000).
• Kim, S. & Weissman, J. B. (2004). A genetic algorithm based approach for scheduling decomposable data grid applications. In Proceeding of International Conference on parallel processing ICPP 2004. pp 406-413
• Carretero, j. & Xhafa, F. (2006). Use of genetic algorithms for scheduling jobs in large Scale grid applications. Technological and economic development of economy, 6(1), 11–17. http://www. tede. vgtu. lt.
• Elghirani, A. , Subrata, R. , Zomaya, A. & Al Mazari, A. (2008). Performance Enhancement through Hybrid Replication and Genetic Algorithm Co-Scheduling in Data Grids. IEEE.
• Bhana, S. & Gopalan, N. (2008). A hyper-heuristic approach for efficient resources scheduling in grid. International Journal of computers, communications & control, 3(3), 249-258.
• Entezari-Maleki, R. & Movaghar, A. (2011). A Genetic Algorithm to Increase the Throughput of the Computational Grids. International Journal of Grid and Distributed Computing, 4(2), June, 2011.
• Kennedy, J. & Eberhart, R. (1995). Particle swarm optimization. In Proceeding of International Conference on neural network. pp 1940-1948.
• Izakian, H. , Ladani, B. , Zamanifar, K. & Abraham, A. (2010). A Novel Particle Swarm Optimization Approach for Grid Job Scheduling.
• Zhang, L. , Chen, Y. , Sun, R. , Jing, S. & Yang, B. (2008). A Task Scheduling Algorithm Based on PSO for Grid Computing. In International Journal of Computational Intelligence Research, 4(1), 37–43.
• Mathiyalagan, P. Dhepthie, U. & Sivanandam, S. (2010). Grid scheduling using enhanced PSO algorithm. International Journal on Computer Science and Engineering (IJCSE), 2(2), 140-145
• Shakerian, R. , Kamali, M. , Hedayati, M. & Alipour, M. (2011). Comparative study of ant colony optimization and particle swarm optimization for grid scheduling. TJMCS 3(2), 469-474.
• Dorigo, M. (1996). The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26(1), 1996,1-13.
• Kousalya, K. & Balasubramanie, P. (2008). An enhanced ant algorithm for grid scheduling problem. International Journal of Computer Science and Network Security IJCSNS, 8(4), April 2008.
• Kousalya, K. & Balasubramanie, P. (2009). To improve Ant algorithm's grid scheduling using local search. International Journal of computational cognition , 4(7), Dec. 2009.
• Semnani, S. H. , Zamanifar, K. , Nematbakhsh, N. , (2009). New Heuristic in Ant Colony Optimization to Solve Job Scheduling Problem in Grid.
• Xu, Z. , Hou, X. & Sun, J. , (2003). Ant algorithm-based task scheduling in grid computing. Electrical and Computer Engineering, IEEE CCECE 2003. Canadian Conference , 2, 1107-1110, 4-7 May 2003, 10. 1109/CCECE. 2003. 1226090.
• Lorpunmanee, S. , Sap, M. N. , Abdullah, A. H. , Chompoo-inwai, C. (2007). An Ant Colony Optimization for Dynamic Job Scheduling in Grid Environment. World Academy of Science, Engineering and Technology, 29, 2007.
• Kousalya, K. & Balasubramanie, P. (2008). Ant Algorithm for Grid Scheduling Powered by Local Search. International Journal Open Problems Computer, Mathematics, 1(3), December 2008.
• Mathiyalagan, P. , Suriya, S. ,Sivanandam, S. (2010). Modified ant colony algorithm for grid scheduling. International journal computer science and engineering. 2(2), pp 132-139.
• Maruthanayagam, D. & Umarani, R. (2010). Enhanced ant colony algorithm for grid scheduling. International journal computer technology applications, 1 (1), 43-53.
• Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization. Technical report, October 2005.
• Akbari, R. , Zeighami, V. & Ziarati, K. (2010). Artificial bee colony for resource constrained project scheduling problem. Growing science Ltd.
• Davidovic, T. , Selmic, M. & Teodorovic, D. (2009). Bee colony optimization for scheduling independent tasks. In Proceedings of the Symposium on Information Technology, YUINFO 2009, (on CD 116. pdf), Kopaonik, Serbia, March 08-11, 2009.
• Davidovi?, T. , Šelmi?, M. & Teodorovi?, D. (2009). Scheduling Independent Tasks: Bee Colony Optimization Approach. In Proceeding 17th Mediterranean Conference on Control and Automation, (pp. 1020-1025), Makedonia Palace, Thessaloniki, Greece, June 24-26, 2009.
• Karaboga, D. & Ozturk, C. (2011). A novel clustering approach: artificial bee colony (ABC) algorithm. Applied soft computing 11, 652-657.
• Vivekanandan, K. , Ramyachitra, D. & Anbu, B. (2011). Artificial bee colony algorithm for grid scheduling. Journal of Convergence Information Technology, 6(7), July 2011.
• Gupta, M. , & Sharma, G. , (2012). An Efficient Modified Artificial Bee Colony Algorithm for Job Scheduling Problem. International Journal of Soft Computing and Engineering (IJSCE), 1(6), January 2012, ISSN: 2231-2307.
• Meihong, W. & Wenhua, Z. (2010). A comparison of four popular heuristics for task scheduling problem in computational grid. 6th International Conference on Wireless Communications Networking and Mobile Computing (WiCOM), 2010. pp1-4.
• Li, H. , Wang, L. & Liu, J. (2010). Task scheduling of computational grid based on particle swarm algorithm.

Index Terms

Keywords