IMMEDIATE/BATCH MODE SCHEDULING ALGORITHMS FOR GRID COMPUTING: A REVIEW

J.Y Maipan-uku; I Rabiu; Amit Mishra

doi:10.29121/granthaalayah.v5.i7.2017.2103

Authors

J.Y Maipan-uku Department of Mathematics and Computer Science, Faculty of Natural Sciences, Ibrahim Badamasi Babangida University, Lapai, Niger State, Nigeria
I. Rabiu Department of Mathematics and Computer Science, Faculty of Natural Sciences, Ibrahim Badamasi Babangida University, Lapai, Niger State, Nigeria
Dr. Amit Mishra Department of Mathematics and Computer Science, Faculty of Natural Sciences, Ibrahim Badamasi Babangida University, Lapai, Niger State, Nigeria

DOI:

https://doi.org/10.29121/granthaalayah.v5.i7.2017.2103

Keywords:

Grid Computing, Scheduling, MET, MCT, Min-Min, Max-Min

Abstract [English]

Immediate/on-line and Batch mode heuristics are two methods used for scheduling in the computational grid environment. In the former, task is mapped onto a resource as soon as it arrives at the scheduler, while the later, tasks are not mapped onto resource as they arrive, instead they are collected into a set that is examined for mapping at prescheduled times called mapping events. This paper reviews the literature concerning Minimum Execution Time (MET) along with Minimum Completion Time (MCT) algorithms of online mode heuristics and more emphasis on Min-Min along with Max-Min algorithms of batch mode heuristics, while focusing on the details of their basic concepts, approaches, techniques, and open problems.

Downloads

Download data is not yet available.

References

Alharbi, F, (2012). Simple Scheduling Algorithm with Load Balancing for Grid Computing. Asian Transactions on Computers. 2, pp. 8-9.

Amalarethinam, G.D.I. & Kfatheen V.S., (2014). Max-min Average Algorithm for Scheduling Tasks in Grid Computing Systems. International Journal of Computer Science and Information Technologies. 3, pp. 3659-62.

Amalarethinam, D. G., & Mary, G. J. (2011). A new DAG based Dynamic Task Scheduling Algorithm (DYTAS) for Multiprocessor Systems. International Journal of Computer Applications, 19 (8), pp. 24-28.

Anand, K.C., Rajendra, S., (2011). New Heuristic for Scheduling of Independent Tasks in Computational Grid. International Journal of Grid and Distributed Computing. 4(3), pp. 25-27.

Anousha, S., Anousha, S., & Ahmadi, M. (2014). A New Heuristic Algorithm for Improving Total Completion Time in Grid Computing. In Multimedia and Ubiquitous Engineering, Springer Berlin Heidelberg, pp. 17-26. DOI: https://doi.org/10.1007/978-3-642-54900-7_3

Bansal, S., & Hota, C. (2011). Efficient Algorithm on Heterogeneous Computing System. International Conference on Recent Trends in Information Systems, (78-1-4577-0792-6/11), pp. 57-61. DOI: https://doi.org/10.1109/ReTIS.2011.6146840

Bardsiri, A. K., & Hashemi, S. M. (2012). A Comparative Study on Seven Static Mapping Heuristics for Grid Scheduling Problem. International Journal of Software Engineering and Its Applications, 6 (4), pp. 247-256.

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. 61, pp. 823 – 831. DOI: https://doi.org/10.1006/jpdc.2000.1714

Cao, L., Liu, X., Wang, H., & Zhang, Z. (2014). OPT-Min-Min Scheduling Algorithm of Grid Resources. Journal of Software, 9 (7), pp. 1868-1875. DOI: https://doi.org/10.4304/jsw.9.7.1868-1875

Chaturvedi, A.K, & Sahu, R., (2011). New Heuristic for Scheduling of Independent Tasks in Computational Grid. International Journal of Grid and Distributed Computing. 4 (3), pp. 25-27.

Chen, H., Wang, F., Helian, N. & Akanmu, G., (2013). User-Priority Guided Min-Min Scheduling Algorithm For Load Balancing in Cloud Computing. University of Kent, Canterbury, United Kingdom. (1 - 8), pp. 1-6.

Devipriya, S., & Ramesh, C. (2013). Improved Max-Min Heuristic Model for Task Scheduling in Cloud. IEEE, pp. 883-888. DOI: https://doi.org/10.1109/ICGCE.2013.6823559

Dong, F. & Selim, G. A. (2006). Scheduling Algorithms for Grid Computing: State of the Art and Open Problems. School of Computing, Queen’s University, Kingston, Ontario. Technical Report No. 2006-504.

Doreen, D., Miriam, H., & Easwarakumar, K. (2010). A Double Min Min Algorithm for Task Metascheduler on Hypercubic P2P Grid Systems. International Journal of Computer Science Issues, 7 (4).

Etminani, K., Naghibzadeh, M., & Yanehsari, N.R., (2008). A Hybrid Min-Min Max-Min Algorithm with Improved Performance. Department of Computer Engineering, Ferdowsi University of Mashad, Iran., e.g. 32, pp.1 – 3.

Freund RF, Gherrity M, Ambrosius S, Campbell M, Halderman M, Hensgen D. (1998). Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet. HCW ‘98, Orlando, FL; pp. 184–99. DOI: https://doi.org/10.1109/HCW.1998.666558

Fujimoto, N., & Hagihara, K. (2004). A Comparison among Grid Scheduling Algorithms for Independent Coarse-Grained Tasks. 2(04), pp. 7-7. DOI: https://doi.org/10.1109/SAINTW.2004.1268711

Ghosh, T., Goswami, R., Bera, S., & Barman, S. (2012). Load Balanced Static Grid Scheduling Using Max-Min Heuristic. 2nd IEEE International Conference on Parallel, Distributed and Grid Computing, pp. 419-423. DOI: https://doi.org/10.1109/PDGC.2012.6449857

Gupta, K., & Singh, M., (2012). Heuristic Based Task Scheduling In Grid. International Journal of Engineering and Technology (IJET). 4, pp. 254 – 258.

Hak Du, K., & Jin Suk, K., (2001). An On-line Scheduling Algorithm for Grid Computing Systems. Electronics and Telecommunications Research Institute, Taejon, Korea & School of Computer Science, University of Seoul, Seoul, Korea., e.g. 32, pp.2 – 6.

HE. X, X-He Sun, & Laszewski. G.V., (2003). QoS Guided Min- Min Heuristic for Grid Task Scheduling. Journal of Computer Science and Technology. 18, pp. 442-451.

Hemamalini, M., & Srinath, M. V. (2015). Memory Constrained Load Shared Minimum Execution Time Grid Task Scheduling Algorithm in a Heterogeneous Environment. Indian Journal of Science and Technology, 8 (15). DOI: https://doi.org/10.17485/ijst/2015/v8i15/71373

Hemamalini, M., (2012). Review of Grid Task Scheduling in Distributed Heterogeneous Environment. International Journal of Computer Applications. 40 (24 - 30), pp. 24 – 26. DOI: https://doi.org/10.5120/4929-7159

Hesam, I., Ajith, A., senior member, IEEE, VS., (2009). Comparison of Heuristics for Scheduling Independent Tasks on Heterogeneous Distributed Environment. International Joint Conference on Computational Sciences and Optimization. (8 -12), pp. 8-10.

Kamalam, G. K., & Bhaskaran, V. M. (2010). An improved Min-Mean heuristic scheduling algorithm for mapping independent tasks on heterogeneous computing environment. Journal of Computational cognition.

Kartal, E., Tabak, B. B., C., and Cevdet, A., (2014). Improving the Performance of Independent Task Assignment Heuristics MinMin, MaxMin and Sufferage. Ieee Transactions on Parallel and Distributed Systems. 25 (1244 - 1256), pp. 1248 – 1249.

Kaur, R., & Patra, P. (2013). Resource Allocation with improved MinMin Algorithm. International Journal of Computer Applications, 76 (15), pp. 61-67. DOI: https://doi.org/10.5120/13327-0918

Kfatheen, S.V., Banu, M.N., & Selvi, S.K., (2014). TAAG: An Efficient Task Allocation Algorithm for Grid Environment. International Journal of Engineering and Technology (IJET). 4 (1961 – 1969), pp. 1961-1968.

Kfatheen, S.V., Banu, M.N., & Selvi, S.K., (2014). TLLB: Two-Level Load Balanced Algorithm for Static Meta-Task Scheduling in Grid Computing. International Journal of Computer Applications (0975 – 8887). 105 (38 - 43), pp. 38 – 41.

Kim, H., & Kim, J. 2004. An online scheduling algorithm for grid computing systems, Grid and Cooperative Computing, pp. 34-39.

Kokilavani, T. & Amalarethinam, D.I.G., (2011). Load Balanced Min-Min Algorithm for Static Meta-Task Scheduling in Grid Computing. International Journal of Computer Applications (0975 – 8887). 20 (2) (43 – 49), pp. 43-47.

Liu, K., Chen, J., Jin, H., & Yang, Y. (2009). A Min-Min Average Algorithm for Scheduling Transaction-Intensive Grid Workflows. New Zealand. Conferences in Research and Practice in Information Technology, 99, pp. 1-8.

Liu, L., & Li, G. (2010). An Improved MIN-MIN Grid Tasks Scheduling Algorithm Based on QoS Constraints. 201O International Conference on Optics, Photonics and Energy Engineering, 10 (978-1-4244-5236-1110), pp. 281-283.

Luo, P., & Shi, Z. (2007). A revisit of fast greedy heuristics for mapping a class of independent tasks onto heterogeneous computing systems (K. Lü, Ed.). Journal of Parallel and Distributed Computing, 67 (0743-7315/$), pp. 695-714. DOI: https://doi.org/10.1016/j.jpdc.2007.03.003

Maheswaran, M., Ali, S., and Siegel, H. J., Hensgen, D., & Freund, F. R., (1999). Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems1. Journal of Parallel and Distributed Computing. 59 (107 - 131), pp. 107 – 118. DOI: https://doi.org/10.1006/jpdc.1999.1581

Maipan-uku, J.Y, Muhammed, A., Abdullah, A., Hussin, M. (2016). Efficient Loads Balancing for Grid Computing System Using Min-Min Scheduling Algorithm. International Journal of Applied Engineering Research (IJAER).

Mao, Y., Chen, X., & 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 255, pp. 457-465. DOI: https://doi.org/10.1007/978-81-322-1759-6_53

Min-You Wu, M.U., Shu, W. & Zhang, H., (2000). A Static Mapping Algorithm for Meta-tasks on Heterogeneous Computing Systems. IEEE. 1 (1 - 11), pp. 1 – 6.

Mrs. Minal, S., Prof. Rajesh, B., & Prof. Rupesh, M., (2013). Task Assignment in Heterogeneous Environment with Advanced Scheduling Algorithms. International Journal of Advanced Research in Computer Science and Software Engineering. 3 (1079 - 1083), pp. 1079 – 1082.

Mukherjee, A. (2011). An Efficient Job-Grouping Based Scheduling Algorithm for Fine-Grained Jobs in Computational Grids (Doctoral dissertation).

Panda, S.K., Agrawal, P., & Mohapatra, D.P., (2013). X-DualMake: Novel Immediate Mode Scheduling Heuristics in Computational Grids. Department of Computer Science and engineering Indian School of Mines, Dhanbad, India, IBM Bangalore, India, National Institute of Technology Rourkela, India. (1 – 6), pp. 1-2.

Parsa, S and Reza, E. M., (2009). RASA: A New Task Scheduling Algorithm in Grid Environment. World Applied Sciences Journal 7 (Special Issue of Computer & IT). (152-160), pp. 152-155. DOI: https://doi.org/10.4156/jdcta.vol3.issue4.10

Pinel, F., Dorronsoro, B., Pecero, J.E., Bouvry, P., & Khan, S.U. (2012). A two-phase heuristic for the energy-efficient scheduling of independent tasks on computational grids. Cluster Computer.

Plaszczak, P., & Wellner, R. (2006). With Grid computing the savvy manager's guide. Amsterdam: Elsevier/Morgan Kaufmann. 1, pp. 5.

Reda, N. M., Tawfik, A., Marzok, M. A., & Khamis, S. M. (2014). Sort-Mid tasks scheduling algorithm in grid computing. Journal of Advanced Research.

Sharma, M.G., Bansal, P., (2012). Min-Min Approach for Scheduling in Grid Environment. International Journal of Latest Trends in Engineering and Technology (IJLTET). 1 (26 - 34), pp. 26.

Singh. M and Suri. P.K, QPS., (2008). A QoS Based Predictive Max-Min, Min-Min Switcher Algorithm for Job Scheduling in a Grid. Information Technology Journal. 7 (1176 – 1181), pp. 1176-80. DOI: https://doi.org/10.3923/itj.2008.1176.1181

Soheil, A., & Mahmoud, A., (2013). An Improved Min-Min Task Scheduling Algorithm in Grid Computing. © Springer-Verlag Berlin Heidelberg., e.g. 32 (103 - 113), pp.103 – 106.

Tseng, L-Y., Chin, Y-H., Wang, S-C., (2009). A minimized makespan scheduler with multiple factors for Grid computing systems. Expert Systems with Applications journal homepage: www.elsevier.com/locate/eswa. 36 (11118–11130), pp. 11120-28. DOI: https://doi.org/10.1016/j.eswa.2009.02.071

Vijayalakshmi, R., & Vasudevan, V. (2015). Static Batch Mode Heuristic Algorithm for Mapping Independent Tasks in Computational Grid. Journal of Computer Science, 11 (1), pp. 224. DOI: https://doi.org/10.3844/jcssp.2015.224.229

Wu, M. Y., Shu, W., & Zhang, H. (2000, May). Segmented min-min: A static mapping algorithm for meta-tasks on heterogeneous computing systems. Inhcw. IEEE, pp. 375.

Xhafa, F., Barolli, L., & Durresi, A. (2007). Batch mode scheduling in grid systems. International Journal of Web and Grid Services, 3 (1), pp. 19-19. DOI: https://doi.org/10.1504/IJWGS.2007.012635

Yu, X., & Yu, X. (2009, August). A new grid computation-based Min-Min algorithm. In Fuzzy Systems and Knowledge Discovery. FSKD'09. Sixth International Conference on. IEEE. 1, pp. 43-45. DOI: https://doi.org/10.1109/FSKD.2009.81