Scheduling of jobs is a challenging problem in grid. Efficient job scheduling is essential for the effective utilization of the resources. We propose a grid model as a collection of clusters. In this paper, we apply Divisible Load Theory (DLT) and Least Cost Method (LCM) to model the grid scheduling problem involving multiple worker nodes in each cluster. We propose a hybrid job scheduling algorithm that minimizes the overall processing time of the job in a grid system that consists of heterogeneous hosts. The results show that the proposed algorithm is feasible and improves the makespan considerably.

1. Tracy D. Braun, Howard Jay Siegel, and Noah Beck, “A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems”, Journal of Parallel and Distributed Computing, Vol.61, pp. 810 – 837, 2001.
2. V.Bharadwaj, D.Ghose, and T.G.Robertazzi, “Diisible Laoad Theory: A New Paradigm for Load Scheduling in Distributed Systems”, Cluster Computing on Divisible Load Scheduling, pp. 7 – 18, 2003.
3. T.G.Robertazzi, “Ten Reasons to use Divisible Load Theory”, Computer, Vol.36, No.5,pp. 63 – 68.
4. Monir Abdullah, Mohamed Othman, Hamidah Ibrahim, and Shamala Subramaniam, “Load Allocation Model for Scheduling Divisible Data Grid Applications”, Journal of Computer Science 5(10), pp. 760 – 763, 2009.
5. I.Foster, C.Kesselman, and S.Tuecke, “ The Anatomy of the Grid: Enabling Scalable Virtual Organizations”, International Journal on High Performance Computing Applications, Vol.15, No.3, pp. 200 – 222, 2001.
6. Ruchir Shah, Bhardwaj Veeravalli, Senior Member, IEEE, and Manoj Misra, Member, IEEE, “ On the Design of Adaptive and Decetralized Load-Balancing Algorithms with Load Estimation for Computational Grid Environments.
7. Wim Depoorter, Ruben Van Den Bossche, Kurt Vanmechelen, and Jan Broeckhove, “ Evaluating the Divisible Load Assumption in the Context of Economic Grid Scheduling with Deadline Based QoS Guarantees”, 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, pp. 452 – 459, 2009.
8. Syed Nasir Mehmood Shah, Ahmad Kamil Bin Mahmood, and Alan Oxley 2010, “Hybrid Resource Allocation for Grid Computing”, in Proceedings of the IEEE Second International Conference on Computer Research and Development, 426 – 431.
9. D.Yu, T.G.Robertazzi 2003, “Divisible Load Scheduling for Grid Computing ”, in Proceedings of the International Conference on Parallel and Distributed Computing Systems.
10. G.Murugesan, and C.Chellappan 2009, “An Economical Model for Optimal Distribution of Loads for Grid Applications ”, in Internal Joural of Computer and Network Security,Vol.1,No.1.
11. Jaehwan Lee, Pete Keleher, Alan Sussman, “Decentralized dynamic scheduling across heterogeneous multi-core desktop grids”, in 2010 IEEE International Symposium on Parallel&Distributed Processing, Workshops and Phd Forum, pp.1-9.
12. Po-Chi Shih, Kuo-Chan Huang, Che-Rung Lee, I-Hsin Chung, Yeh-Ching Chung, "A Performance Goal Oriented Processor Allocation Technique for Centralized Heterogeneous Multi-cluster Environments," ccgrid, pp.614-615, 2011 11th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, 2011
13. Amril Nazir, Hao Liu, Søren-Aksel Sørensen, "A Rental-Based Approach in a Cluster or a Grid Environment," cit, pp.2501-2508, 2010 10th IEEE International Conference on Computer and Information Technology, 2010
14. Anwar Mamat, Ying Lu, Jitender Deogun, Steve Goddard, "An Efficient Algorithm for Real-Time Divisible Load Scheduling," rtas, pp.323-332, 2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium, 2010.
15. Syed Nasir Mehmood Shah, Ahmad Kamil Bin Mahmood, Alan Oxley, "Modified Least Cost Method for Grid Resource Allocation," cyberc, pp.218-225, 2010 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, 2010.

Grid Job Scheduling Cluster Coordinator Node Worker Node Heterogeneous Hosts