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 Complet...

Full description

Saved in:
Bibliographic Details
Main Authors: Padmavathi, S., Suguna, M., Shalinie, S.M.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
DAG Scheduling
Optimal scheduling
Particle swarm optimization
Processor scheduling
Program processors
Schedules
Scheduling
Tabu Search
Task Scheduling
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2157-0477
2157-0485
DOI:10.1109/ICETET.2008.245