关键词: 柔性作业车间调度, 遗传算法, 约束理论, 变异操作, 瓶颈

Abstract: Flexible job shop scheduling problem is an extension of the classical job shop scheduling problem, which allows processes on the machine from alternative machine set, and the processing time will be different with the different processing machine. According to the characteristics of flexible job shop scheduling problem, a local search method based on the Theory Of Constraints（TOC） is presented, comparing the machines load rate on the critical path to find the bottleneck machine, keeping the workload balance among the machines. In order to overcome the disadvantage of traditional genetic algorithm precocious and slow convergence, multiple mutation operators are designed to increase the diversity of the population. For better retaining excellent solution in each generation, it designs Elite solution retention policies based on the Hamming distance. Benchmark problems are solved by the proposed algorithm. Computational results show the feasibility and effectiveness of the proposed algorithm.

Key words: flexible job shop scheduling, genetic algorithm, theory of constraints, mutation operator, bottleneck