Journal of Applied Mathematics and Decision Sciences 
Volume 2006 (2006), Article ID 65746, 17 pages
doi:10.1155/JAMDS/2006/65746

Parallel genetic algorithms with migration for the hybrid flow shop scheduling problem

K. Belkadi,1,2 M. Gourgand,2 and M. Benyettou1

 1Department of Computer Science, University of Sciences and Technology of Oran Mohamed Boudiaf, BP 1505 Oran M'Naouer, Oran 31000, Algeria
2LIMOS Laboratory, University of Blaise Pascal, Clermont Ferrand, Campus of Cézeaux, Aubière Cedex 63173, France
Received 17 March 2006; Revised 17 July 2006; Accepted 2 August 2006

Abstract

This paper addresses scheduling problems in hybrid flow shop-like systems with a migration parallel genetic algorithm (PGA_MIG). This parallel genetic algorithm model allows genetic diversity by the application of selection and reproduction mechanisms nearer to nature. The space structure of the population is modified by dividing it into disjoined subpopulations. From time to time, individuals are exchanged between the different subpopulations (migration). Influence of parameters and dedicated strategies are studied. These parameters are the number of independent subpopulations, the interconnection topology between subpopulations, the choice/replacement strategy of the migrant individuals, and the migration frequency. A comparison between the sequential and parallel version of genetic algorithm (GA) is provided. This comparison relates to the quality of the solution and the execution time of the two versions. The efficiency of the parallel model highly depends on the parameters and especially on the migration frequency. In the same way this parallel model gives a significant improvement of computational time if it is implemented on a parallel architecture which offers an acceptable number of processors (as many processors as subpopulations).