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

摘要： 柔性作业车间调度问题是经典作业车间调度问题的扩展，它允许工序在可选加工机器集中任意一台上加工，加工时间随加工机器不同而不同。针对柔性作业车间调度问题的特点，提出一种基于约束理论的局部搜索方法，对关键路径上的机器的负荷率进行比较，寻找瓶颈机器，以保证各机器之间的负荷平衡。为了克服传统遗传算法早熟和收敛慢的缺点，设计多种变异操作，增加种群多样性。为了更好保留每代中的优良解，设计了基于海明距离的精英解保留策略。运用提出的算法求解基准测试问题，验证了算法的可行性和有效性。

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