The week's pick
Random Articles
Reseach Article
Load Balanced Min-Min Algorithm for Static Meta-Task Scheduling in Grid Computing
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 20 - Number 2 |
| Year of Publication: 2011 |
| Authors: T. Kokilavani, D.I. George Amalarethinam |
10.5120/2403-3197
|
T. Kokilavani, D.I. George Amalarethinam . Load Balanced Min-Min Algorithm for Static Meta-Task Scheduling in Grid Computing. International Journal of Computer Applications. 20, 2 ( April 2011), 42-48. DOI=10.5120/2403-3197
Abstract
Grid computing has become a real alternative to traditional supercomputing environments for developing parallel applications that harness massive computational resources. However, the complexity incurred in building such parallel Grid-aware applications is higher than the traditional parallel computing environments. It addresses issues such as resource discovery, heterogeneity, fault tolerance and task scheduling. Load balanced task scheduling is very important problem in complex grid environment. So task scheduling which is one of the NP-Complete problems becomes a focus of research scholars in grid computing area. The traditional Min-Min algorithm is a simple algorithm that produces a schedule that minimizes the makespan than the other traditional algorithms in the literature. But it fails to produce a load balanced schedule. In this paper a Load Balanced Min-Min (LBMM) algorithm is proposed that reduces the makespan and increases the resource utilization. The proposed method has two-phases. In the first phase the traditional Min-Min algorithm is executed and in the second phase the tasks are rescheduled to use the unutilized resources effectively.
References
- Braun, T.D., Siegel, H.J., Beck, N., Boloni, L.L., Maheswaran, M., Reuther, A.I., Robertson, J.P., et al. “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, No. 6, pp.810–837, 2001
- Chapman. C, Musolesi. M, Emmerich. W, Mascolo. C, ”Predictive Resource Scheduling in Computational Grids” in Parallel and Distributed Processing Symposium, IEEE International Vol. 26, pp.1 – 10, 2007
- Ian Foster, Carl Kesselman, Steven Tuecke, “The Anatomy of the Grid Enabling Scalable Virtual Organizations” International Journal of Supercomputer Applications, 2001.
- Siriluck Lorpunmanee, Mohd Noor Sap, Abdul Hanan Abdullah, and Chai Chompoo-inwai, “An Ant Colony Optimization for Dynamic Job Scheduling in Grid Environment”, World Academy of Science, Engineering and Technology 29, pp. 314- 321, 2007.
- Dantong Yu and Thomas G. Robertazzi “Divisible Load Scheduling for Grid Computing”, PDCS’2003, 15th Int’l Conf. Parallel and Distributed Computing and Systems. IASTED, pp. 1 – 9, 2003.
- Kokilavani.T and George Amalarethinam.D.I, Applying Non-Traditional Optimization Techniques to Task Scheduling in Grid Computing, International Journal of Research and Reviews in Computer Science, Vol. 1, No. 4, Dec 2010, pp. 34 - 38
- Saeed Parsa, Reza Entezari-Maleki RASA: A New Grid Task Scheduling Algorithm , International Journal of Digital Content Technology and its Applications Volume 3, Number 4, December 2009
- Geoffrey Falzon, Maozhen Li, “Enhancing list scheduling heuristics for dependent job scheduling in grid computing environments”, Journal of Supercomputing, Springer, March 2010.
- Doreen Hephzibah Miriam. D and Easwarakumar. K.S, A Double Min Min Algorithm for Task Metascheduler on Hypercubic P2P Grid Systems, IJCSI International Journal of Computer Science Issues, Vol. 7, Issue 4, No 5, July 2010.
- He. X, X-He Sun, and Laszewski. G.V, "QoS Guided Min-min Heuristic for Grid Task Scheduling," Journal of Computer Science and Technology, Vol. 18, pp. 442-451, 2003.
- Kamalam.G.K and Muralibhaskaran.V, , A New Heuristic Approach:Min-Mean Algorithm For Scheduling Meta-Tasks On Heterogenous Computing Systems, IJCSNS International Journal of Computer Science and Network Security, VOL.10 No.1, January 2010.
- Sameer Singh Chauhan,R. Joshi. C, QoS Guided Heuristic Algorithms for Grid Task Scheduling, International Journal of Computer Applications (0975 – 8887), pp 24-31, Volume 2, No.9, June 2010.
- Singh. M and Suri. P.K, QPS A QoS Based Predictive Max-Min, Min-Min Switcher Algorithm for Job Scheduling in a Grid, Information Technology Journal, Year: 2008, Volume: 7, Issue: 8, Page No.: 1176-1181.
- Yagoubi. B, and Slimani. Y, "Task Load Balancing Strategy for Grid Computing," Journal of Computer Science, Vol. 3, No. 3, pp. 186-194, 2007.
- Dong. F, Luo. J, Gao. L and Ge. L, "A Grid Task Scheduling Algorithm Based on QoS Priority Grouping," In the Proceedings of the Fifth International Conference on Grid and Cooperative Computing (GCC’06), IEEE, 2006.
- Etminani .K, and Naghibzadeh. M, "A Min-min Max-min Selective Algorithm for Grid Task Scheduling," The Third IEEE/IFIP International Conference on Internet, Uzbekistan, 2007.
- Maheswaran. M, Ali. Sh, Jay Siegel. H, Hensgen. D, and Freund.R.F, "Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems, Journal of Parallel and Distributed Computing, Vol. 59, pp. 107-131, 1999.
- Ranganathan, K. and Foster, I., “Decoupling Computation and Data Scheduling in Distributed Data Intensive Applications”, Proceedings of the 11th IEEE Symposium on High Performance Distributed Computing (HPDC-11), Edinburgh, Scotland, July 2002.
- Ullah Munir. E, Li. J, and Shi. Sh, 2007. QoS Sufferage Heuristic for Independent Task Scheduling in Grid. Information Technology Journal, 6 (8): 1166-1170.
Index Terms
Keywords