An Improved Genetic Algorithm for Optimization of Operation Sequencing

摘要

To solve the operation sequencing problem in CAPP that is a NP-hard problem, an improved genetic algorithm (IGA) is developed to minimize the total cost. In the IGA, a feasible operation sequence (FOS) satisfying the precedence constraints is encoded by a permutation. Then a fragment crossover and a fragment mutation with adaptive operation probabilities, along with a new elitist-based crossover strategy, are designed to evolve chromosomes and keep the feasibility of the chromosomes. The proposed IGA was applied to two industrial cases, and was compared with existing GA, ant colony optimization (ACO) and particle swarm optimization (PSO) against the two cases. The comparative results show that the IGA is superior to the GA with fixed crossover and mutation probabilities with respect to exploration ability, and indicate that IGA outperforms existing GA, ACO and PSO for solution quality.