DAG Scheduling on Cluster of Workstations Using Hybrid Particle Swarm Optimization

Task Scheduling is one of the core steps to effectively exploit the capabilities of resources in cluster computing environment. Scheduling of applications modeled by Directed Acyclic Graph (DAG) is a key issue in this type of environment. The task scheduling problem has been shown to be a NP Complete in general as well as in several restricted cases. This paper presents a List Scheduling algorithm using Particle Swarm Optimization (PSO) based on the concept of Tabu Search (TS). This approach combines the excellence of both PSO and TS. This is different from the existing methods since the procedure adaptively incorporates information about Tabu lists into PSO algorithm. The proposed algorithm outperforms other algorithms in the aspects of performance and scalability. The experimental results manifest that the proposed hybrid method is effective and efficient in finding near optimal schedule length.