The motivation of Grid computing is to aggregate the power of widely distributed resources, and provide non-trivial services to users. To achieve this goal, an efficient Grid scheduling System is an essential part of the Grid. Rather than covering the whole Grid scheduling area, this survey provides a review of the subject mainly from the perspective of scheduling algorithms. In this review, the challenges for Grid scheduling are identified. First, the architecture of components involved in scheduling is briefly introduced to provide an intuitive image of the Grid scheduling process. Then various Grid scheduling algorithms are discussed from different points of view, such as static vs. dynamic policies, objective functions, applications models, adaptation, constraints, strategies dealing with dynamic behavior of resources, and so on. Thus, in this paper, the following definition for the term Grid adopted: “A type of parallel and distributed system that enables the sharing, selection, and aggregation of geographically distributed autonomous and heterogeneous resources dynamically at runtime depending on their availability, capability, performance, cost, and users' quality-of-service requirements”. To facilitate the discussion, the following frequently used terms are defined: A task is an atomic unit to be scheduled by the scheduler and assigned to a resource. The properties of a task are parameters like CPU/memory requirement, deadline, priority, etc. A job (or metatask, or application) is a set of atomic tasks that will be carried out on a set of resources. Jobs can have a recursive structure, meaning that jobs are composed of sub-jobs and/or tasks, and sub-jobs can themselves be decomposed further into atomic tasks. In this paper, the term job, application and metatask are interchangeable. A resource is something that is required to carry out an operation, for example: a processor for data processing, a data storage device, or a network link for data transporting. A site (or node) is an autonomous entity composed of one or multiple resources. A task scheduling is the mapping of tasks to a selected group of resources which may be distributed in multiple administrative domains.

1. Foster, I., Kesselman, C.: The Grid: Blueprint for a New Computing Infrastructure Second edition, Morgan-Kaufman, 2004.
2. M. Baker, R. Buyya, D. Laforenza: Grids and Grid technologies for wide-area distributed computing, Sotware – Practice and Experience, 2002, John Wiley & Sons, Ltd.
3. M. Baker, R. Buyya and D. Laforenza, Grids and Grid Technologies for Wide-area Distributed Computing, in J. of Software-Practice & Experience, Vol. 32, No.15, pp: 1437-1466, December 2002.
4. F. Berman, R. Wolski, S. Figueria, J. Schopf and G. Shao, Application-Level Scheduling on Distributed Heterogeneous Networks, in Proc. of the 1996 ACM/IEEE Conference on Supercomputing, Article No: 39, Pittsburgh, Pennsylvania USA, November 1996.
5. F. Berman, High-Performance Schedulers, chapter in The Grid: Blueprint for a Future Computing Infrastructure, edited by I. Foster and C. Kesselman, Morgan Kaufmann Publishers, 1998.
6. F. Berman, R. Wolski, H. Casanova, W. Cirne, H. Dail, M. Faerman, S. Figueira, J. Hayes, G. Obertelli, J. Schopf, G. Shao, S. Smallen, N. Spring, A. Su and D. Zagorodnov, Adaptive Computing on the Grid Using AppLeS, in IEEE Trans. On Parallel and Distributed Systems (TPDS), Vol.14, No.4, pp.369--382, 2003.
7. F. Berman, High-Performance Schedulers, chapter in The Grid: Blueprint for a Future Computing Infrastructure, Morgan Kaufmann Publishers, 1998.
8. J. Bester, I. Foster, C. Kesselman, J. Tedesco and S. Tuecke, GASS: A Data Movement and Access Service for Wide Area Computing Systems, in Proc. of the 6th Workshop on I/O in Parallel and Distributed Systems, pp.: 78-88, Atlanta, Georgia USA, May 1999.
9. J Blythe, S Jain, E Deelman, Y Gil, K Vahi and A Mandal,K Kennedy, Task Scheduling Strategies for Workflow-based Applications in Grids, in Proc. Of International Symposium on Cluster Computing and Grid (CCGrid’05), pp.759-767, Cardiff, UK, May 2005.
10. R. Braun, H. Siegel, N. Beck, L. Boloni, M. Maheswaran, A. Reuther, J. Robertson, M. Theys, B. Yao, D. Hensgen and R. Freund, A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems, in J. of Parallel and Distributed Computing, vol.61, No. 6, pp. 810-837, 2001.
11. R. Buyya, J. Giddy, and D. Abramson, An Evaluation of Economy-based Resource Trading and Scheduling on Computational Power Grids for Parameter Sweep Applications, in Proc. of the 2nd International Workshop on Active Middleware Services (AMS 2000), pp. 221-230, , Pittsburgh, USA, August 2000.
12. R. Buyya and D. Abramson and J. Giddy and H. Stockinger, Economic Models for Resource Management and Scheduling in Grid Computing, in J. of Concurrency and Computation: Practice and Experience, Volume 14, Issue.13-15, pp. 1507-1542, Wiley Press, December 2002.
13. R. Buyya, D. Abramson, and S. Venugopal, The Grid Economy, in Proc. of the IEEE, Vol. 93, No. 3, pp. 698-714, IEEE Press, New York, USA, March 2005.
14. J. Cao, S. A. Jarvis, S. Saini, G. R. Nudd, Grid Flow: Workflow Management for Grid Computing, in Proc. of the 3rd International Symposium on Cluster Computing and the Grid (CCGrid’03), pp.198-205, Tokyo, Japan, May 2003.

OLB MET Min_min GA Tabu A*