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 Transfer Statement
The copyright of this article is transferred to Current Applied Science and Technology journal with effect if and when the article is accepted for publication. The copyright transfer covers the exclusive right to reproduce and distribute the article, including reprints, translations, photographic reproductions, electronic form (offline, online) or any other reproductions of similar nature.
The author warrants 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.
Here is the link for download: Copyright transfer form.pdf
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.