Title: Dynamic task scheduling with load balancing using parallel orthogonal particle swarm optimisation
Author: S.N. Sivanandam, P. Visalakshi
Department of Computer Science and Engineering, PSG College of Technology, Coimbatore, Tamilnadu 641004, India.
Department of Computer Science and Engineering, PSG College of Technology, Coimbatore, Tamilnadu 641004, India
Journal: Int. J. of Bio-Inspired Computation, 2009 Vol.1, No.4, pp.276 - 286
Abstract: This paper presents a novel approach for dynamic task scheduling using particle swarm optimisation. Particle swarm optimisation (PSO) is a population-based meta-heuristic method which can be used to solve np-hard problems. The algorithm has been developed to dynamically schedule heterogeneous tasks on to heterogeneous processors in a distributed setup. Load balancing which is a major issue in task scheduling is also considered. The nature of the tasks are independent and non pre-emptive. Different approaches using PSO has been tried namely PSO with fixed inertia, PSO with variable inertia, PSO with elitism, MPSO, parallel PSO, hybrid PSO, orthogonal PSO and parallel orthogonal PSO. The performance of PSO and its variants is also compared with the genetic algorithm concept. The objective of the algorithms is to minimise the make-span of the entire schedule. Benchmark problems have been taken and validated. The result depicts that the dynamic task scheduling implemented using parallel orthogonal particle swarm optimisation technique is cost-effective in nature when compared to the other algorithms tested.
Keywords: genetic algorithms; GAs; particle swarm optimisation; inertia; elitism; modified particle swarm optimisation; MPSO; hybrid PSO; HPSO; parallel PSO; orthogonal PSO; OPSO; parallel orthogonal PSO; POPSO; modified PSO; dynamic scheduling; load balancing; task scheduling; bio-inspired computation.
Available online 28 Apr 2009