Abstract: Aiming at the flexible job shop scheduling problem that expects to complete production with the minimum number of machines, a bi-level optimization model is established that minimizes the makespan as the inner goal and the minimum number of machines as the outer goal. That is, under the conditions of meeting the due date and minimizing the makespan, it tries to reduce the number of machines to find the minimum number of machines for workshop scheduling. According to the characteristics of the model and algorithm, a genetic algorithm based on the great mutation strategy is designed. The algorithm uses two-dimensional chromosome coding, sequence selection strategy, and uses the priority operation crossover operator and the great mutation strategy to ensure the diversity of the population. After verification and analysis of examples, the model is established and is better than the scheduling model of the specified number of machines, which can save manpower and processing costs for the enterprise and improve the utilization rate of machines. Compared with the other five algorithms, it can be seen that the algorithm is effective and can achieve better optimization goals.

Key words: flexible job shop scheduling, minimum number of machines, genetic algorithm, bi-level optimization, great mutation strategy

摘要： 针对期望以最小机器数完成生产的柔性作业车间调度问题，建立了最小化最大完工时间为内层目标，最小机器数为外层目标的双层优化模型，即在满足交货期、最小化最大完工时间的条件下，尝试减少机器数量，以寻求车间调度的最少机器数。依据模型、算法特点，设计了一种基于大变异策略的遗传算法，该算法采用二维染色体编码、顺序选择策略，同时运用优先操作交叉算子和大变异策略的方法，来保证种群的多样性。经过实例验证分析，模型成立，并优于指定机器数的调度模型，能够为企业节省人力、加工成本，提高机器利用率。与其他五种算法比较可知，算法有效，能够获得较好的优化目标。

关键词: 柔性作业车间调度, 最小机器数, 遗传算法, 双层优化, 大变异策略