Dynamic task scheduling with load balancing using parallel orthogonal particle swarm optimisation

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.