A NEW EFFICIENT ALGORITHM BASED ON PARALLEL BEST-FIRST SEARCH ALGORITHM FOR SCHEDULING CONCURRENT TASKS ON GRID COMPUTING

Nur Hidayah binti Omar #1, Mohamed Faidz Mohamed Said #2

# Universiti Teknologi MARA
70300 Seremban, Negeri Sembilan, MALAYSIA

1 dayahomar94@gmail.com
2 faidzms@ieee.org

 
Abstract—The explanation about parallel best-first search for scheduling concurrent tasks on Grid computing is given. Parallel algorithm can perform various instructions simultaneously like in concurrent processing that can divide a complex task, combine all the individual outputs and process multiple systems to get the final result in quick time.

Keywords—parallel, best-first search, concurrent tasks, Grid computing


REFERENCES

[1]	tutorialspoint. (2016, 12 Oct 2016). Parallel Algorithm - Quick Guide. Available: https://www.tutorialspoint.com/parallel_algorithm/parallel_algorithm_quick_guide.htm

[2]	E. Machuca, L. Mandow, J. L. Pérez de la Cruz, and A. Ruiz-Sepulveda, "A comparison of heuristic best-first algorithms for bicriterion shortest path problems," European Journal of Operational Research, vol. 217, pp. 44-53, 2012.

[3]	N. B. Karahanoglu and H. Erdogan, "A* orthogonal matching pursuit: Best-first search for compressed sensing signal recovery," Digital Signal Processing, vol. 22, pp. 555-568, 2012.

[4]	D. R. Morrison, S. H. Jacobson, J. J. Sauppe, and E. C. Sewell, "Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning," Discrete Optimization, vol. 19, pp. 79-102, 2016.

[5]	B. Mans and C. Roucairol, "Performances of parallel branch and bound algorithms with best-first search," Discrete Applied Mathematics, vol. 66, pp. 57 - 74, 1993.

[6]	A. Grama and V. Kumar, "State of the art in parallel search techniques for discrete optimization problems," IEEE Transactions on Knowledge and Data Engineering, vol. 11, pp. 28-35, 1999.

[7]	D. Allouche, S. De Givry, G. Katsirelos, T. Schiex, and M. Zytnicki, "Anytime hybrid best-first search with tree decomposition for weighted CSP," in International Conference on Principles and Practice of Constraint Programming, 2015, pp. 12-29.

[8]	E. Burns, S. Lemons, W. Ruml, and R. Zhou, "Best-first heuristic search for multicore machines," Journal of Artificial Intelligence Research, vol. 39, pp. 689-743, 2010.

[9]	E. Burns, S. Lemons, W. Ruml, and R. Zhou, "Parallel best-first search: Optimal and suboptimal solutions," in Proceedings of the International Symposium on Combinatorial Search, 2009.

[10]	M. Robnik-Šikonja, "Effective use of memory in linear space best first search," FRI, Technical Report1996.

[11]	F. Xie, "Exploration in Greedy Best-First Search for Satisficing Planning," University of Alberta, 2016.

[12]	C. Hernández, R. Asin, and J. A. Baier, "Time-Bounded Best-First Search," in Seventh Annual Symposium on Combinatorial Search, 2014.

[13]	R. Marinescu and R. Dechter, "Best-first AND/OR search for most probable explanations," arXiv preprint arXiv:1206.5268, 2012.

[14]	F. Dong and S. G. Akl, "Scheduling Algorithms for Grid Computing: State of the Art and Open Problems," Technical Report No. 2006-504, 2006.