A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks

Abstract

The multistage hybrid flow-shop scheduling problem with multiprocessor tasks has been found in many practical situations. Due to the essential complexity of the problem, many researchers started to apply metaheuristics to solve the problem. In this paper, we address the problem by using particle swarm optimization (PSO), a novel metaheuristic inspired by the flocking behaviour of birds. The proposed PSO algorithm has several features, such as a new encoding scheme, an implementation of the best velocity equation and neighbourhood topology among several different variants, and an effective incorporation of local search. To verify the PSO algorithm, computational experiments are conducted to make a comparison with two existing genetic algorithms (GAs) and an ant colony system (ACS) algorithm based on the same benchmark problems. The results show that the proposed PSO algorithm outperforms all the existing algorithms for the considered problem.

Keywords:

• Scheduling
• Hybrid flow-shop
• Multiprocessor tasks
• Particle swarm optimization

Acknowledgement

This work is partially supported by the National Science Council, Taiwan, Republic of China, under grant number NSC 95-2811-E011-006.