A two-stage approach based on genetic algorithm for large size flow shop scheduling problem

The majority of large size flow shop scheduling problems is non-polynomial-hard (NP-hard). In the past decades, genetic algorithms have demonstrated considerable success in providing efficient solutions to many NP-hard optimization problems. But there is no literature considers the optimal parameters when designing a specific genetic algorithm. Unsuitable parameters may cause terrible solution for large and NP-hard scheduling problem. In this paper, we propose a two-stage genetic algorithm for large size flow shop, which attempts to firstly find the fittest control parameters, namely, number of population, probability of crossover, probability of mutation, for a given flow shop problem with a fraction of time using optimal-computing-budget-allocation method; and then the fittest parameters are used in the genetic algorithm for further more search operation to find optimal solution. For large size problem, the two-stage genetic algorithm can get optimal solution effectively and efficiently. The method was validated based on some hard benchmark problems of flow shop scheduling.