This paper proposes a dynamic workload’s threshold-based scheduling and load balancing algorithm for distributed computing systems. It takes into account the dynamicity and heterogeneity of available system resources, and tasks. It automatically updates the workload thresholds upon any significant change of any resource workload and balances the system’s workload using the new thresholds. Unlike most of the current scheduling and load balancing algorithms, the proposed algorithm uses the resource’s load as a workload index instead of number of tasks. The number of tasks is not a good workload index especially when the weights of tasks are different. A node can be overloaded even if it has a number of tasks less than that in an under-loaded node. A simulation model is built to evaluate the performance of the proposed algorithm. The performance of the proposed algorithm is evaluated and compared with that of Min–Min, and Ant Colony scheduling algorithms using mean task response time, average utilization of processing nodes, and load balancing level as performance metrics. The results show that the proposed algorithm reduces the task mean response time, improves resources utilization, and load balancing level compared with the other two studied algorithms in the range of system’s parameters values examined.
F.Alharbi, Simple scheduling algorithm with load balancing for grid computing, Asian Transactions on Computers2(2) (2012), 8–15.
2.
O.Beaumont, A.Legrand, L.Marchal and Y.Robert, Steady-state scheduling on heterogeneous clusters, International Journal of Foundations of Computer Science16(2) (2005), 163–194.
3.
R.Buyya, A grid simulation toolkit for resource modeling and application scheduling for parallel and distributed computing, available at: www.buyya.com/gridsim/.
4.
R.Buyya, M.Murshed and D.Abramson, A deadline and budget constrained cost–time optimization algorithm for scheduling task farming applications on global grids, in: Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, USA, 2002, pp. 24–27, available at: http://arxiv.org/ftp/cs/papers/0203/0203020.pdf.
5.
J.Cao, D.P.Spooner, S.A.Jarvis and G.R.Nudd, Grid load balancing using intelligent agents, Future Generation Computer Systems21(1) (2005), 135–149.
6.
F.Dong and S.G.Akl, Scheduling algorithms for grid computing: State of the art and open problems, Technical report, School of Computing, Queen’s University Kingston, Ontario, January 2006.
7.
S.F.El-Zoghdy, Numerical studies on a paradox for non-cooperative dynamic load balancing in distributed computer systems, in: IASTED International Conference on Parallel and Distributed Computing and Networks (PDCN 2006), Innsbruck, Austria, 14–16 February 2006, 2006, pp. 238–243.
8.
S.F.El-Zoghdy, A capacity-based load balancing and job migration algorithm for heterogeneous computational grids, International Journal of Computer Networks & Communications (IJCNC)4(1) (2012), 113–125.
9.
S.F.El-Zoghdy, A hierarchical load balancing policy for grid computing environment, I.J. Computer Network and Information Security5 (2012), 1–12.
10.
S.F.El-Zoghdy, An AntNet-based load balancing algorithm for grid computing environments, International Journal of Computer Applications83(7) (2013), 41–48.
11.
S.F.El-Zoghdy, H.Kameda and J.Li, A comparative study of static and dynamic individually optimal load balancing policies, in: Proceedings of the IASTED International Conference on Networks, Parallel and Distributed Processing and Applications, 2002, pp. 200–205.
12.
S.F.El-Zoghdy, H.Kameda and J.Li, Numerical studies on a paradox for non-cooperative static load balancing in distributed computer systems, Computers and Operation Research33(2) (2006), 345–355.
13.
I.Foster and C.Kesselman (eds), The Grid 2: Blueprint for a New Computing Infrastructure, 2nd edn, Morgan Kaufmann Publishers, USA, 2004.
14.
I.Foster, C.Kesselman and S.Tuecke, The anatomy of the grid: Enabling scalable virtual organizations, International Journal of High Performance Computing Applications15(2) (2001), 200–222.
15.
R.K.Gupta and J.Ahmed, Dynamic load balancing by scheduling in computational grid system, International Journal of Advanced Research in Computer Science and Software Engineering4(6) (2014), 267–272.
16.
X.He, X.Sun and G.von Laszewski, QoS guided Min–Min heuristic for grid task scheduling, Journal of Computer Science and Technology18(4) (2003), 442–451.
17.
H.Johansson and J.Steensland, A performance characterization of load balancing algorithms for parallel SAMR applications, Technical Report 2006-047, Department of Information Technology, Uppsala University, 2006.
18.
H.Kameda, J.Li, C.Kim and Y.Zhang, Optimal Load Balancing in Distributed Computer Systems, Springer, London, 1997.
19.
P.Keerthika and N.Kasthuri, A hybrid scheduling algorithm with load balancing for computational grid, International Journal of Advanced Science and Technology58 (2013), 13–28.
20.
P.Kumar, Load balancing and job migration in grid environment, Master thesis, Thapar University, 2009.
21.
Y.Li, Y.Yang, M.Ma and L.Zhou, A hybrid load balancing strategy of sequential tasks for grid computing environments, Future Generation Computer Systems25 (2009), 819–828.
22.
J.Lin, B.Gong, H.Liu, C.Yang and Y.Tian, An application demand aware scheduling algorithm in heterogeneous environment, in: IEEE Proceedings of the 11th International Conference on Computer Supported Cooperative Work in Design, IEEE Xplore Press, Melbourne, Vic, 2007, pp. 509–604.
23.
K.Lu, R.Subrata and A.Y.Zomaya, On the performance-driven load distribution for heterogeneous computational grids, Journal of Computer and System Science73(8) (2007), 1191–1206.
24.
S.A.Ludwig and A.Moallem, Swarm intelligence approaches for grid load balancing, Journal of Grid Computing9(3) (2011), 279–301.
25.
N.Malarvizhi and V.R.Uthariaraj, A new mechanism for job scheduling in computational grid network environments, in: Proceedings of the 5th International Conference on Active Media Technology, Lecture Notes in Computer Science, Vol. 5820, Springer, 2009, pp. 490–500.
26.
A.Moallem, Using swarm intelligence for distributed job scheduling on the grid, Master thesis, University of Saskatchewan, Canada, 2009.
27.
M.Nandagopal and R.V.Uthariaraj, Hierarchical status information exchange scheduling and load balancing for computational grid environments, IJCSNS International Journal of Computer Science and Network Security10(2) (2010), 177–185.
28.
F.Palmieri, Network-aware scheduling for real-time execution support in data-intensive optical grids, Future Generation Computer Systems25(7) (2009), 794–803.
29.
F.Palmieri and S.Pardi, Towards a federated Metropolitan area grid environment: The SCoPE network-aware infrastructure, Future Generation Computer Systems26(8) (2010), 1241–1256.
30.
H.S.Qurbonboyevich and T.-Y.Choe, Two-level dynamic load balancing algorithm using load thresholds and pairwise immigration, International Journal on Computer Science and Engineering5(04) (2013), 211–220.
31.
P.Suresh and P.Balasubramanie, User demand aware grid scheduling model with hierarchical load balancing, Mathematical Problems in Engineering2013 (2013), 1–8.
32.
P.Suresh, P.Balasubramanie and P.Keerthika, Prioritized user demand approach for scheduling meta tasks on heterogeneous grid environment, International Journal of Computer Applications23(1) (2011), 6–12.
33.
A.Touzene, S.Al Yahia, K.Day and B.Arafeh, Load balancing grid computing middleware, in: IASTED International Conference on Web Technologies, Applications, and Services, 2005.
34.
M.Vasile, F.Pop, R.Tutueanu, V.Cristea and J.Kolodziej, Resource-aware hybrid scheduling algorithm in heterogeneous distributed computing, Future Generation Computer Systems51 (2015), 61–71.
35.
L.Wenzheng and Z.Wenyue, An improved scheduling algorithm for grid tasks, in: Proceedings of the International Symposium on Intelligent Ubiquitous Computing and Education (IUCE’09), May 2009, 2009, pp. 9–12.
36.
B.Yagoubi, H.Nadia and H.T.Lilia, Dynamic load balancing in grid computing, African Journal of Research in Computer Science and Applied Mathematics7 (2007), 1–19.
37.
B.Yagoubi and Y.Slimani, Task load balancing strategy for grid computing, Journal of Computer Science3(3) (2007), 186–194.
38.
Y.Zhu, A survey on grid scheduling systems, Technical report, Department of Computer Science, Hong Kong University of Science and Technology, 2003.
