Max-Average: An Extended Max-Min Scheduling Algorithm for Grid Computing Environtment
Keywords:Scheduling Algorithm, Grid Computing, Minimum Execution Time (MET), Minimum Completion Time (MCT),
AbstractSharing numerous computational and communication power from connected heterogeneous systems over the world are the two key points of Grid computing. Grid computing can also be referred as a computing platform for users to utilise the remote heterogeneous resources for solving their large scale jobs that require a huge amount of processing power or a huge data storage. Sharing these resources that way effectively requires a very good scheduling strategy, which is the focus of this research. This paper presents a new proposed grid based scheduling algorithm called Max-Average, inspired from Max-Min algorithm. In order to produce good quality solutions, the proposed algorithm is designed in two phases; firstly it uses an initial task queue like the traditional Max -Min for estimating task completion time for each of resources, and in the second phase choose the fitting resource for scheduling according to requirements. The results from our simulation showed that our proposed algorithm is performing better in producing good quality solutions, particularly in executing tasks fast and in balancing the load (resource utilisation) among the resources more effectively when compared to standard Minimum Execution Time (MET), Minimum Completion Time (MCT), Min-Min, and Max-Min heuristic approaches
Xhafa, F. (2008). Metaheuristics for Scheduling in Distributed Computing Environments. Springer-Verlag, pp. 2-9.
Jacob, B. (2005). Introduction to grid computing. United States: IBM, International Technical Support Organization. Vol. 1(1), pp. 100.
Kokilavani, T. and Amalarethinam, D.I.G., (2011). Load Balanced MinMin Algorithm for Static Meta-Task Scheduling in Grid Computing. International Journal of Computer Applications. Vol. 20(2), pp. 43-47.
Kokilavani, T., and Amalarethinam, D. I. (2010). Applying
Nontraditional Optimization Techniques to Task Scheduling In Grid Computing-An Overview. International Journal of Research & Reviews in Computer Science. Vol. 1(4), pp. 34-38.
Hemamalini, M., (2012). Review of Grid Task Scheduling in Distributed Heterogeneous Environment. International Journal of Computer Applications. Vol. 40 (2), pp. 24 – 26.
Maheswaran, M., Ali, Siegel, H. J., Hensgen, D. and Freund, F. R. (1999). Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems1. Journal of Parallel and Distributed Computing. Vol. 59(2), pp.107 – 131.
Braun, T. D., Siegel, H. J. and Beck, N., (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, pp. 823 – 831.
Fujimoto, N., and Hagihara, K. (2004). A Comparison among Grid Scheduling Algorithms for Independent Coarse-Grained Tasks. Vol. 2(4), pp. 7-7.
Xhafa, F., Barolli, L., and Durresi, A. (2007). Batch mode scheduling in grid systems. International Journal of Web and Grid Services, Vol. 3(1), pp. 19-19.
Luo, P., and Shi, Z. (2007). A revisit of fast greedy heuristics for mapping a class of independent tasks onto heterogeneous computing systems. Journal of Parallel and Distributed Computing. Vol. 67(6), pp. 695-714.
Ming, G., and Li, H. (2011). An Improved Algorithm Based on MaxMin for Cloud Task Scheduling. Recent Advances in Computer Science and Information Engineering Lecture Notes in Electrical Engineering.Vol. 125, pp. 217-223.
Amalarethinam, G.D.I. and Kfatheen V.S., (2014). Max-min Average Algorithm for Scheduling Tasks in Grid Computing Systems. International Journal of Computer Science and Information Technologies. Vol. 3, pp. 3659-62.
Devipriya, S., and Ramesh, C. (2013). Improved Max-Min Heuristic Model for Task Scheduling in Cloud. IEEE, pp. 883-888.
Mao, Y., Chen, X., and Li, X. (2014). Max–Min Task Scheduling Algorithm for Load Balance in Cloud Computing. Proceedings of International Conference on Computer Science and Information Technology, Advances in Intelligent Systems and Computing. Vol. 255, pp. 457-465.
Li, X., Mao, Y., Xiao, X., and Zhuang, Y. (2014). An Improved MaxMin Task-Scheduling Algorithm for Elastic Cloud. International Symposium on Computer, Consumer and Control, pp. 340-343.
Etminani, K., Naghibzadeh, M., and Yanehsari, N.R., (2007). A Hybrid Min-Min Max-Min Algorithm with Improved Performance. Department of Computer Engineering, Ferdowsi University of Mashad, Iran. Vol.32, pp. 1 – 3.
Li, W., and Zhang, W. (2009). An improved Scheduling Algorithm for Grid Tasks. International Symposium on Intelligent Ubiquitous Computing and Education. Vol. 35, pp. 9-12.
Parsa, S and Reza, E. M., (2009). RASA: A New Task Scheduling Algorithm in Grid Environment. World Applied Sciences Journal. Vol. 7, pp. 152-155.
Gupta, K., and Singh, M., (2012). Heuristic Based Task Scheduling In Grid. International Journal of Engineering and Technology (IJET). Vol. 4, pp. 254 – 258.
Anousha, S., Shoeib, A., and Ahmadi, M. (2014). A New Heuristic Algorithm for Improving Total Completion Time in Grid Computing. Springer-Verlag Berlin Heidelberg, pp. 17-26.
Panda, S., Agrawal, P., Khilar, P., & Mohapatra, D. (2014). SkewnessBased Min-Min Max-Min Heuristic for Grid Task Scheduling. In 4thIEEE International Conference on Advanced Computing and Communication Technologies. pp. 282-289.
Vijayalakshmi, R., and Vasudevan, V. (2015). Static Batch Mode Heuristic Algorithm for Mapping Independent Tasks in
Computational Grid. Journal of Computer Science. Vol. 11(1), pp.
How to Cite
TRANSFER OF COPYRIGHT AGREEMENT
The manuscript is herewith submitted for publication in the Journal of Telecommunication, Electronic and Computer Engineering (JTEC). It has not been published before, and it is not under consideration for publication in any other journals. It contains no material that is scandalous, obscene, libelous or otherwise contrary to law. When the manuscript is accepted for publication, I, as the author, hereby agree to transfer to JTEC, all rights including those pertaining to electronic forms and transmissions, under existing copyright laws, except for the following, which the author(s) specifically retain(s):
- All proprietary right other than copyright, such as patent rights
- The right to make further copies of all or part of the published article for my use in classroom teaching
- The right to reuse all or part of this manuscript in a compilation of my own works or in a textbook of which I am the author; and
- The right to make copies of the published work for internal distribution within the institution that employs me
I agree that copies made under these circumstances will continue to carry the copyright notice that appears in the original published work. I agree to inform my co-authors, if any, of the above terms. I certify that I have obtained written permission for the use of text, tables, and/or illustrations from any copyrighted source(s), and I agree to supply such written permission(s) to JTEC upon request.