Improved genetic algorithm for the permutation flowshop scheduling problem

摘要

Genetic algorithms (GAs) are search heuristics used to solve global optimization problems in complex search spaces. We wish to show that the efficiency of GAs in solving a flowshop problem can be improved significantly by tailoring the various GA operators to suit the structure of the problem. The flowshop problem is one of scheduling jobs in an assembly line with the objective of minimizing the completion time or makespan. We compare the performance of GA using the standard implementation and a modified search strategy that tries to use problem specific information. We present empirical evidence via extensive simulation studies supported by statistical tests of improvement in efficiency.