A NEW EFFICIENT ALGORITHM BASED ON FLOYD’S ALGORITHM FOR SCHEDULING CONCURRENT TASKS ON GRID COMPUTING

Nurul Sakinah Muhamad Mahadi #1, Mohamed Faidz Mohamed Said #2

# Universiti Teknologi MARA
70300 Seremban, Negeri Sembilan, MALAYSIA

1 sakinahmahadi92@gmail.com
2 faidzms@ieee.org
 
Abstract—This article is about new efficient algorithm based on Floyd’s algorithm for scheduling concurrent tasks on Grid computing. Floyd-Warshall (FW) algorithm is proficiently and concurrently used for the discovery of the shortest paths between every pair of vertices in a weighted and possible directed graph. Grid computing is a processor architecture that collaborates computer resources from different domains to accomplish a main goal.

Keywords: Floyd’s algorithm, scheduling concurrent task, Grid computing


REFERENCES

[1]	"What is Grid Computing_ - Definition from Techopedia," https://www.techopedia.com/definition/87/grid-computing, 2016.

[2]	A. Aini and A. Salehipour, "Speeding up the Floyd–Warshall algorithm for the cycled shortest path problem," Applied Mathematics Letters, vol. 25, pp. 1-5, 2012.

[3]	K. C. Kiwiel, "On Floyd and Rivest's SELECT algorithm," Theoretical computer science, vol. 347, pp. 214-238, 2005.

[4]	A. Singh and P. K. Mishra, "Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm," International Journal of Computer Applications, vol. 107, 2014.

[5]	C. Papadimitriou and M. Sideri, "On the Floyd–Warshall algorithm for logic programs," The journal of logic programming, vol. 41, pp. 129-137, 1999.

[6]	I.-M. Alifieraki, A. Andreou, C. Andrikos, D. Bliablias, Athanasios-Akanthos Chasapis, George Chatzikonstantis, et al., "Parallelizing the Floyd-Warshall Algorithm on Modern Multicore Platforms: Lessons Learned," 5th Conference of Electrical and Computer Engineering Students, University of Thrace, Xanthi, Greece, 2012.

[7]	W. Qiao, G. Zeng, A. Hua, and F. Zhang, "Scheduling and executing heterogeneous task graph in grid computing environment," in International Conference on Grid and Cooperative Computing, 2005, pp. 474-479.

[8]	M. Meddeber, B. Yagoubi, and W. Kadri, "A Static Tasks Assignment for Grid Computing," in the Proceedings of the 3rd International Conference on Computer Science and its Applications (CIIA’11), Saida, Algeria, 2011.

[9]	M. Wu and X.-H. Sun, "A general self-adaptive task scheduling system for non-dedicated heterogeneous computing," in Cluster Computing, 2003. Proceedings. 2003 IEEE International Conference on, 2003, pp. 354-361.

[10]	S. Sharma, A. Chhabra, and S. Sharma, "Comparative analysis of scheduling algorithms for grid computing," in Advances in Computing, Communications and Informatics (ICACCI), 2015 International Conference on, 2015, pp. 349-354.

[11]	N. M. Reda, A. Tawfik, M. A. Marzok, and S. M. Khamis, "Sort-Mid tasks scheduling algorithm in grid computing," J Adv Res, vol. 6, pp. 987-93, Nov 2015.

[12]	F. Dong and S. G. Akl, "Scheduling algorithms for grid computing: State of the art and open problems," 2006.

[13]	F. S. Gharehchopogh, M. Ahadi, I. Maleki, R. Habibpour, and A. Kamalinia, "Analysis of Scheduling Algorithms in Grid Computing Environment," International Journal of Innovation and Applied Studies, vol. 4, pp. 560-567, 2013.

[14]	H. B. Prajapati and V. A. Shah, "Scheduling in grid computing environment," in 2014 Fourth International Conference on Advanced Computing & Communication Technologies, 2014, pp. 315-324.