Abstract: The characteristic of the flexible job shop scheduling problem (FJSP) is analyzed, an improved genetic algorithm is proposed to solve the FJSP. To keep workload balance among the machines, improve the quality of the initial population and accelerate the speed of the algorithm’s convergence, a new initialization method is proposed, which combines with global search, local search and random generation. Considering the characteristic of the problem, rational chromosome encoding, crossover operator and mutation operator are designed to prevent the generation of illegal solutions, avoid chromosome repair and improve efficiency of the algorithm. The improved genetic algorithm is tested on instances taken from the literature and compared with their results. The computation results show that the improved genetic algorithm is feasible and effective.

Key words: Flexible job shop scheduling, Genetic algorithm, Initialization