Algorithms For Task Scheduling On Grid Computing

The Grid is a new national information infrastructure for many future applications. It has been a research focus in the field of information technology in recent years. In a grid computing environment, the problem of task scheduling is very critical. In this thesis, models and algorithms for scheduling tasks in the grid are studied. The main results are as follows:1. Models for task scheduling including application model, platform model and scheduling objective are investigated in detail. The trade-off between model accuracy and model simplicity is discussed. Several parameters of more realistic task scheduling model are induced.2. The problem of divisible task scheduling is studied and the following results are presented. First, optimal algorithms based on a more realistic model, i.e., non-zero start-up cost for non-blocking model of communication, are proposed for scheduling large workload on heterogeneous system. Second, a periodic multi-installment algorithm is proposed and closed-form expressions for optimal parameters on homogeneous systems are derived. Third, two kinds of heuristic scheduling algorithm are proposed for scheduling divisible load on arbitrary topological network.3. The problem of independent task scheduling is studied and the following results are acquired. First, a local search algorithm is proposed to solve the problem of task scheduling in homogeneous environment. Second, a memory based algorithm is proposed for scheduling same-size tasks on heterogeneous platform. Third, a concept of task scheduling priority is proposed and a class of scheduling algorithm can be derived according to the priority. Fourth, a local search algorithm is proposed for task scheduling in heterogeneous system.4. The problem of dependent task scheduling is studied and an efficient list scheduling algorithm based on critical path is presented. By means of a new approach for constructing the task list, and an efficient processor selection procedure using looking ahead strategy, the algorithm shortens the makespan greatly.