AN IMPROVED GENETIC ALGORITHM FOR THE PERMUTATION FLOW-SHOP SCHEDULING PROBLEM WITH MAKESPAN CRITERION

摘要

Permutation Flow-Shop Scheduling Problem with makespan criterion is usually a strong NP-hard problem of combinatorial optimization problem and is one of the most typical production scheduling problems. It is usually very hard to find its optimal solution. In this paper, an improved Genetic Algorithm in dealing with this flow-shop scheduling problem is presented. The algorithm adopted multi-individual-crossover way, took the threshold value in the process of crossover and mutation , thus expanded the search space of solution and kept the variety of population in the course of optimizing, increased the probability of obtaining optimal solution .Through testing a series of typical Benchmark problems, the experimental results validate the effectiveness of the proposed algorithm.