An Availability-Aware Task Scheduling Algorithm For Heterogeneous Systems Using Particle Swarm Optimization

Clusters, grids and peer-to-peer (P2P) networks are a popular paradigm for parallel and distributed computing. In a grid environment the resources are geographically distributed, managed and owned by different organizations with their own policies and interconnected via the Internet. This introduces a number of resource management issues and scheduling strategies in the domain of security, resources and heterogeneity. The resource management and scheduling systems for grid computing need to manage resources depending on several factors like consumers or the owners and hence continuously adapt to changes in resource availability.A major challenge in task scheduling is the availability of resources. In a heterogeneous environment, where processors operate at different speeds and are not continuously available for computation, achieving a better make-span is a key issue. The problem escalates with as we take multiclass applications in to account. Most existing algorithms do not take in to account the problems imposed by multiclass applications.In this research we investigate an existing scheduling algorithm which takes in to account the multiclass applications. This existing algorithm known as Scheduling Strategy with Availability Constraints, SSAC, has proved to be a good trade-off between availability and responsiveness while maintaining a good performance in the average response time of multiclass tasks. But it tends to distribute tasks to some nodes that can provide high availability levels to fully satisfy the tasks'availability requirements, so it might assign a large number of tasks to a node with a high availability level. As a result, the makespan may be influenced due to load imbalance. Our proposed approach try to further optimize this scheduling strategy by using Particle Swarm Optimization technique.Particle Swarm Optimization (PSO) is a population based heuristic search technique to find solutions to continuous nonlinear functions. Each particle represents a potential solution within the search space. PSO is initialized with a swarm of random solutions and searches for optima by updating generations.We have compared our results with other popular scheduling algorithms such as SSAC and MINMIN. In the simulation various representative instances based on practical data have been selected to experiment. Our results indicate that our proposed technique using particle swarm optimization is a better solution for reducing the makespan considerably.