A Metaheuristic Algorithm for Job Scheduling in Grid Computing

Full Text (PDF, 424KB), PP.52-59

Views: 0 Downloads: 0

Author(s)

Hedieh Sajedi 1,* Maryam Rabiee 2

1. Mathematics, Statistics and Computer Science School, College of Science, University of Tehran, Tehran, Iran

2. Department of Computer, Science and Research Branch, Islamic Azad University, Khouzestan, Iran

* Corresponding author.

DOI: https://doi.org/10.5815/ijmecs.2014.05.07

Received: 16 Jan. 2014 / Revised: 14 Feb. 2014 / Accepted: 21 Mar. 2014 / Published: 8 May 2014

Index Terms

Cuckoo optimization algorithm, genetic algorithm, job scheduling, grid computing

Abstract

These days the number of issues that we can not do on time is increasing. In the mean time, scientists are trying to make questions simpler and using computers. Still, more problems that are complicated need more complex calculations by using highly advanced technology. Grid computing integrates distributed resources to solve complex scientific, industrial, and commercial problems. In order to achieve this goal, an efficient scheduling system as a vital part of the grid is required. In this paper, we introduce CUckoo-Genetic Algorithm (CUGA), which inspired from cuckoo optimization algorithm (COA) with genetic algorithm (GA) for job scheduling in grids. CUGA can be applied to minimize the completion time of machines, and it could avoid trapping in a local minimum effectively. The results illustrate that the proposed algorithm, in comparison with GA, COA, and Particle Swarm Optimization (PSO) is more efficient and provides higher performance.

Cite This Paper

Hedieh Sajedi, Maryam Rabiee, "A Metaheuristic Algorithm for Job Scheduling in Grid Computing", International Journal of Modern Education and Computer Science (IJMECS), vol.6, no.5, pp.52-59, 2014. DOI:10.5815/ijmecs.2014.05.07

Reference

[1]I. Foster, C. Kesselman, “The Grid: Blueprint for a Future Computing Infrastructure”, Morgan Kaufman Publishers, USA, 1999.
[2]I. Foster, C. Kesselman, “The Grid 2: Blueprint for a New Computing Infrastructure”, 2nd ed., Morgan Kaufmann, 2004.
[3] A. Abraham, R. Buyya, B. Nath, “Nature’s heuristics for scheduling jobs on computational grids”, The 8th IEEE International Conference on Advanced Computing and Communications (ADCOM), 2000.
[4]A. Abraham, F. Xhafa, “Meta-heuristics for Grid Scheduling Problems”, Springer-Verlag Berlin Heidelberg, pp. 1–37, 2008.
[5]M. Yaghini, R. Akhavan, “DIMMA: A Design and Implementation Methodology for Metaheuristic Algorithms”, International Journal of Applied Metaheuristic Computing, vol.1, pp.57-74, 2010.
[6]J. Schopf, “Ten actions when grid scheduling”, Mathematics and Computer Science Division, 2004.
[7]M. Aggarwal and R. Kent, “Genetic Algorithm Based Scheduler for Computational Grids”, Proceedings of the 19th International Symposium on High Performance Computing Systems and Applications (HPCS’05), 2005.
[8]L. Zhang, H. Chen, R. Sun, S. Jing, B. Yang, “A Task Scheduling Algorithm Based on PSO for Grid Computing”, International Journal of Computational Intelligence Research, vol. 4, no. 1, pp. 37–43, 2008.
[9]J. Wang, Q. Duan, “A New Algorithm for Grid Independent Task Schedule: Genetic Simulated Annealing", World Automation Congress (WAC), 2010.
[10]P. Mathiyalagan, S. Suriya, N. Sivanandam, “Modified Ant Colony Algorithm for Grid Scheduling”, (IJCSE) International Journal on Computer Science and Engineering, vol. 02, no. 02, pp. 132-139, 2010.
[11]J. Umale, S. Mahajan, “Optimized Grid Scheduling Using Two Level Decision Algorithm (TLDA)”. 1st International Conference on Parallel, Distributed and Grid Computing (PDGC), 2010.
[12]Z. Pooranian, M. Shojafar, “A Hybrid Meta-Heuristic Algorithm for Job Scheduling on Computational Grids”, Informatica 37, 2013.
[13]R. Sharma, V. K. Soni, M. K. Mishra, P. Bhuyan, “A survey of job scheduling and resource management in grid computing”, World Academy of Science, Engineering and Technology, no. 64, 2010.
[14]R. Rosemarry, P. Singhal, R. Singh, “A Study of Various Job & Resource Scheduling Algorithms in Grid Computing”, International Journal of Computer Science and Information Technologies(IJCSIT), vol. 3, pp. 5504-5507, 2012.
[15]X. Deb. Yang, “Cuckoo Search via Levy Flights”, World Congress on Nature & Biologically Inspired Computing, pp. 210-214, 2009.
[16]R. Rajabioun, “Cuckoo Optimization Algorithm”, Applied Soft Computing, pp. 5508–5518, 2011.
[17]J. Holland, “Adaptation in Natural and Artificial Systems”, University of Michigan Press, re-issued by MIT Press, 1992.
[18]J.P. Watson, “Empirical Modeling and Analysis of Local Search Algorithm for the Job-Shop Scheduling Problem”, Chapter2, Ph.D. Dissertation, 2003.
[19]Zh. Yaqin, L. Beizhi, Y. Jianguo, W. Qingxia, “Study on Modeling of Job Shop Scheduling with Multiresource Constraints”, International Conference on Artificial Intelligence and Computational Intelligence, pp. 313-317, 2010.
[20]K.S. Amirthagadeswaran, V.P. Arunachalam, “Improved solutions for job shop scheduling problems through genetic algorithm with a different method of schedule deduction”, International Journal on Advanced Manufacture Technology, pp. 532–540, 2006.
[21]L. Sun, X. Cheng, Y. Liang, “Solving Job Shop Scheduling Problem Using Genetic Algorithm with Penalty Function", International Journal of Intelligent Information Processing, vol. 1, no. 1, pp. 65-77, 2010.