关键词: 车间作业调度, 遗传算法, 交叉算子, 局部搜索

Abstract: To overcome the limitations of traditional Genetic Algorithm (GA) when solving the problem of job-shop scheduling, an improved GA was proposed by taking advantages of traditional GA and local search. A new crossover operator, Precedence Operation Crossover (POX), for operation-based representation was created. To avoid premature convergence, which appeared in the course of solving job-shop scheduling by applying conventional GA. The concept of an improved generation alteration model was introduced. After a schedule was obtained, a local search heuristic was applied to improve the solution. Its efficiency was validated by applying improved GA to Muth and Thompsons benchmark problem.

Key words: job-shop scheduling, genetic algorithm, crossover operator, local search