Heuristic Methods For Task Scheduling In Heterogeneous Computing Environments

Heterogeneous computing (HC) environment is composed of various resources with different computational capabilities to meet the demands of computing-intensive applications that have diverse computational requirements and constraints. In HC systems and computational grids, a diverse set of geographically distributed resources are used to solve challenging problems. A major challenge in using these systems is to effectively use available resources. System resources are shared among applications. Applications are submitted from various users with specific QoS requirements. One way to take advantage of HC or computational grids is to decompose an application into several tasks based on the computational requirements. Different tasks may be best suited for different machines. Once the application is decomposed into tasks, each task needs to be assigned to suitable machine in order to optimize a given objective function. The problem of assigning application tasks to the machines in a HC environment has been shown, in general, to be NP-complete. Therefore the development of heuristic techniques to find near optimal solution is required. The focus of this dissertation is the assignment of application tasks onto HC systems and computational grids.We developed several scheduling algorithms to address the problem of producing efficient schedules in HC environment and computational grids. We propose a new task scheduling heuristic, high standard deviation first (HSTDF), which considers the standard deviation of expected execution time of a task as a selection criterion. Standard deviation of expected execution time of task represents the amount of variation in task execution time on different machines: Our conclusion is tasks having high standard deviation must be assigned first for scheduling. Intuitively, tasks having low standard deviation of task execution time have less variation in execution time on different machines and hence, their delayed assignment for scheduling will not affect overall makespan much. Moreover, the tasks with higher standard deviation of task execution time exhibit more variation in their execution time on different machines. A delayed assignment of such tasks might hinder their chances of occupying faster machines as some other tasks might occupy these machines earlier. Such a scenario would result in an increase in the system makespan, so the tasks having high standard deviation must be assigned first. Large numbers of experiments were carried out to check the effectiveness of proposed heuristic in different scenarios, which clearly revealed that proposed heuristic outperformed existing heuristics in terms of average makespan and hence provided strong evidence that using standard deviation of execution time as selection criterion improved task scheduling.Next, in this thesis we introduce a novel QoS guided task scheduling algorithm for Grid computing. The term quality of service (QoS) is used differently based on its context while applying it to a resource. For instance, QoS for a network may mean the desirable bandwidth for the application; QoS for CPU may mean the requested speed, like FLOPS, or the utilization of the underlying CPU. In our study, a one dimension QoS is considered. We represent the QoS of a network by its bandwidth. In current Grid task scheduling, tasks with different levels of QoS requests compete for resources. While a task with no QoS request can be executed on both high QoS and low QoS resources, a task that requests a high QoS service can only be executed on a resource providing high quality of service. Thus, it is possible for low QoS tasks to occupy high QoS resources while high QoS tasks wait as low QoS resources remain idle. To overcome this shortcoming, we present the new task scheduling algorithm for computational grids which take the QoS matching into consideration while taking the scheduling decision.A plethora of heuristics has been proposed for assignment of tasks to machines in HC environment. Each heuristic has different underlying assumptions to produce near optimal solution however no work reports which heuristic should be used for a given set of tasks to be executed on different machines. To solve this dilemma, we conduct a performance evaluation of task scheduling heuristics in HC environment and find out the task assignment strategy that gives the minimum makespan. A collection of 16 greedy heuristics, including 7 newly proposed ones, are implemented, analyzed, and systematically compared within a uniform model of task execution time. This model is implemented by the coefficient-of-variation based method. Extensive simulations illustrate the circumstances when a specific greedy heuristic would outperform the other 15 greedy heuristics.