Scheduling is a fundamental process for grid computing systems. Its goal is to map user tasks to suitable resources for execution. The major part of a grid scheduler is to decide which resource is suitable for each task, depending on a scheduling algorithm. Many scheduling algorithms have been designed for reaching optimality. The Suffrage algorithm has shown a superlative performance over most meta-task scheduling algorithms regarding resource selection. However, providing a full power use of resources is still a challenge. In this paper, a new heuristic algorithm is proposed. It aims to maximizing resource utilization and minimizing the makespan. Its decision is based on detecting the maximum average value of completion times among certain tasks. These tasks are selected depending on their suffrage values. The task having the maximum average is then assigned to the resource with the minimum completion time. Experimental results show that the proposed algorithm outperforms other algorithms in terms of utilization and makespan.

1. T. L. Casavant, and J. G. Kuhl, “A taxonomy of scheduling in general-purpose distributed computing systems,” IEEE Trans. Softw. Eng., vol. 14, no. 2, pp. 141-154, 1988. https://dx.doi.org/10.1109/32.4634
2. S. Venugopal, R. Buyya and R. Winton, “A grid service broker for scheduling distributed data-oriented applications on global grids,” in Proc. of the 2nd Workshop on Middleware for Grid Computing, 2004, pp. 75-80. https://dx.doi.org/10.1145/1028493.1028506
3. D. P. Spooner, S. A. Jarvis, J. Cao, S. Saini and G. R. Nudd, “Local grid scheduling techniques using performance prediction,” in IEE Proc. on Conpit. Digit. Tech., 2003, vol. 150, no. 2. https://dx.doi.org/10.1049/ip-cdt:20030280
4. F. Dong and S. G. Akl, “Scheduling algorithms for grid computing: State of the art and open problems,” Rep. of School of Computing held at Queen’s Univ. Kingston, Ontario, USA, 2006.
5. N. Preve, Eds., “Computational and Data Grids: Principles, Applications and Design: Principles, Applications and Design,” IGI Global, 2011. PMCid:PMC3096920
6. B. A. Shirazi, A. R. Hurson and K. M. Kavi, “Scheduling and load balancing in parallel and distributed systems,” IEEE Computer Society Press, 1995. PMCid:PMC2034067
7. S. Anousha and M. Ahmadi, “An improved Min-Min task scheduling algorithm in grid computing,” in Grid and Pervasive Computing,” Springer Berlin Heidelberg, 2013. PMid:24228243 PMCid:PMC3817802
8. N. M. Reda, A. Tawfik, M. A. Marzok, and S. M. Khames, “Sort-Mid tasks scheduling algorithm in grid computing,” J. Advan. Res., vol. 6, no. 6, pp. 987-993. 2014. https://dx.doi.org/10.1016/j.jare.2014.11.010 PMid:26644937 PMCid:PMC4642166
9. M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. F. Freund, “Dynamic mapping of a class of independent tasks onto heterogeneous computing systems,” J. Parallel Distr. Com., vol. 59, no. 2, pp. 107-131, 1999. https://dx.doi.org/10.1006/jpdc.1999.1581
10. G. Sharma, and P. Banga, “Task aware switcher scheduling for batch mode mapping in computational grid environment,” Int. J. of Adv. Res. in Comput. Sci. and Softw. Eng., vol. 3, no. 6, pp. 1292-1299, 2013.
11. H. Izakian, A. Abraham and V. Snasel, “Comparison of heuristics for scheduling independent tasks on heterogeneous distributed environments,” in Proc. of the 2009 Int. Joint Conf. on Computational Sciences and Optimization, 2009, vol. 1, pp. 8-12. https://dx.doi.org/10.1109/CSO.2009.487
12. G. Ritchie and J. Levine, “A hybrid ant algorithm for scheduling independent jobs in heterogeneous computing environments,” in Proc. of the 23rd Workshop of the UK Planning and Scheduling Special Interest Group, 2004, pp. 1-7.
13. T. D. Braun, H. J. Siegel and N. A. Beck, “Comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems,” J. of Parallel Distr Com, 61, 810-837, 2001. https://dx.doi.org/10.1006/jpdc.2000.1714
14. M. K. Rafsanjani, and A. K. Bardsiri, “A new heuristic approach for scheduling independent tasks on heterogeneous computing systems,” Int. J. of Machine Learning and Computing, vol. 2, no. 4, pp. 371-376, 2012. https://dx.doi.org/10.7763/IJMLC.2012.V2.147

N. M. Reda, A. Tawfik, M. A. Marzok and S. M. Khamis, “Range-suffrage algorithm for grid task scheduling,” International Journal of Applied and Physical Sciences, vol. 1, no. 2, pp. 42-50. 2015.