Scheduling Independent Tasks on Grid Computing Systems by Differential Evolution
Article Sidebar
Main Article Content
Abstract
Grid Computing aims to allow unified access to data, computing power, sensors and other resources through a single virtual laboratory. In this paper, we present Differential Evolution algorithm based on schedulers for efficiently allocating jobs to resources in a grid computing system. Scheduling is a key problem in emergent computational systems, such as Grid and P2P, in order to benefit from the large computing capacity of such systems. The general problem of optimally mapping tasks to machines in a heterogeneous computing suite has been shown to be NP-complete. Experimental results show that our algorithm improves the performance of static instances compared to the results of other algorithms reported in the literature.
Keywords: Grid computing, Heuristics, Differential Evolution, Makespan
*Corresponding author: E-mail: kuchaki@mail.uk.ac.ir
Article Details
Copyright Agreement Statement
The corresponding author has to submit Copyright Agreement form after the article is accepted for publication in order to warrant that this contribution is original and that he/she has full power to make this grant. The author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors.
The author(s) grant Current Applied Science and Technology a non-exclusive, irrevocable, royalty-free license to publish, reproduce, distribute, and archive the article in print and electronic form with effect if and when the article is accepted for publication. In the event that the article is withdrawn prior to acceptance or is declined, this agreement shall have no effect, and no party shall be bound by it.
The author(s) retain copyright of this article, including but not limited to the right to reproduce and distribute the article, to include it in a thesis or book, and to post it on an institutional or personal repository, provided that the original publication in Current Applied Science and Technology is properly cited.
References
[2] Tracy, M., Braun, T. D. and Siegel, H., 1998. High-performance Mixed-machine Heterogeneous Computing. 6th Euro-micro Workshop on Parallel and Distributed Processing, pp. 3-9.
[3] Fernandez-Baca, D., 1989. Allocating Modules to Processors in a Distributed System. IEEE Transaction, Software Engineering, pp. 1427–1436.
[4] Fidanova, S. and Durchova, M., 2006. Ant Algorithm for Grid Scheduling Problem, Large Scale Computing. LNCS, 3743, Springer, pp. 405-412.
[5] Izakian, H., Abraham, A. and Snasel, V., 2009. Comparison of Heuristics for Scheduling Independent Tasks on Heterogeneous Distributed Environments. Proceedings of the International Joint Conference on Computational Sciences and Optimization, IEEE, 1, pp. 8-12.
[6] Braun, R., Siegel, H., Beck, N., Boloni, L., Maheswaran, M., Reuther, A., Robertson, J., Theys, M., Yao, M., Hensgen, D. and Freund, R., 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, 61(6), pp. 810-837.
[7] Munir, E., Jian-Zhong, L., Sheng-Fei, S. and Rasool, Q., 2007. Performance Analysis of Task Scheduling Heuristics in Grid. Proceedings of the International Conference on Machine Learning and Cybernetics (ICMLC), 6, pp. 3093-3098.
[8] Baghban, H. and Rahmani, A., 2008. A Heuristic on Job Scheduling in Grid Computing Environment. Proceedings of the seventh IEEE International Conference on Grid and Cooperative Computing, pp. 141-146.
[9] Zhang, Q. and Zhen, L., 2009. Design of Grid Resource Management System Based on Divided Min-min Scheduling Algorithm. IEEE First International Workshop on Education Technology and Computer Science, pp. 613-618.
[10] Xhafa, F. and Abraham, A., 2008. Meta-heuristics for Grid Scheduling Problems, In: Meta-heuristics for Scheduling in Distributed Computing Environments. 146, pp. 1-37, Springer, Germany.
[11] Freund, R. and Siegel, H,. 1993. Heterogeneous Processing. IEEE Computer, 26(6), pp. 13-17.
[12] Freund, R. and Gherrity, M., 1998. Scheduling Resources in Multi-user Heterogeneous Computing Environment with Smart Net. Proceedings of the 7th IEEE HCW.
[13] Abraham, A., Buyya, R. and Nath, B., 2000. Nature's Heuristics for Scheduling Jobs on Computational Grids. Proceedings of the International Conference on Advanced Computing and Communications.
[14] Macheswaran, M., Ali, S., Siegel, H., Hensgen, D. and Freund, R., 1999. Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems. Journal of Parallel Distributed Computing, 59 (2), pp. 107-131.
[15] Xhafa, F., Barolli, L. and Durresi, A., 2007. Immediate Mode Scheduling in Grid Systems. International Journal of Web and Grid Services, 3(2), pp. 219-236.
[16] Munir, E., 2008. MaxStd: A Task Scheduling Heuristic for Heterogeneous Computing Environment. Information Technology Journal, ISSN-1812-5638.
[17] Price, K., Storn, R. and Lampinen, J., 2005. Differential Evolution A Practical Approach to Global Optimization. Natural Computing Series, Springer-Verlag, Berlin, Germany.
[18] Price, K. and Storn, R., 1997. Differential Evolution: Numerical Optimization Made Easy. Dr. Dobb’s Journal, pp. 18–24.
[19] Price. K. and Storn, R., 1995. Differential Evolution: a Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces. Technical Report, TR-95-012, ICSI.
[20] Ali, S., Siegel, H., Maheswaran, M. and Hensgen, D., 2000. Modeling Task Execution Time Behavior in Heterogeneous Computing Systems. Tamkang Journal Science and Engineering, pp. 195-207.
[21] Braun, R., Siegel, H., Beck, N., Boloni, L., Maheswaran, M., Reuther, A., Robertson, J., Theys, M. and Yao, M., 1998. A Taxonomy for Describing Matching and Scheduling Heuristics for Mixed-machine Heterogeneous Computing Systems. Proceedings of the 17th IEEE Symposium on Reliable Distributed Systems, pp. 330-335.
