A genetic algorithm to minimize the makespan for three machine flow shop scheduling problems

Abstract EN

The aim of this paper is to propose genetic algorithm to finding the optimal schedule with minimum makespan for n jobs in flow shop environment with three machines.

In this pape, a new approach for selection, a new crossover operation (3PLOX) and a new stopping criteria based on the lower bound of the makespan (LB) are proposed.

Also, a new procedure of calculating the make span for n jobs at processing by three machine in flow shop environment is suggested.

In order to examine the effectiveness of the proposed GA, a comparison was made with Johnson's algorithm.

After the application on several problems which generated randomly by uniform distribution, the results showed that the proposed GA is better than Johnson's algorithm with rate 94 % in finding the optimal sequence for scheduling jobs which gives optimal makespan.