安徽理工大学电气与信息工程 汪 鹏

分段自适应遗传算法在流水车间调度中的应用

安徽理工大学电气与信息工程 汪 鹏

针对流水车间的优化调度问题，提出一种分段自适应遗传算法，对遗传算法交叉、变异算子进行改进，从而有效避免算法陷入局部，达到算法优化调度的目的。通过对标准遗传算法和改进算法进行仿真验证得知，优化后的算法具有更好的适应度曲线，表明其有效的克服了标准遗传算法不成熟收敛问题，具有一定的工程应用价值。

分段自适应；遗传算法；流水车间

0 引言

随着市场竞争的加剧，各制造加工企业为了提高自身的竞争力，必须合理分配资源，提高设备利用率与生产效率，降低生产成本，这就需要制定良好的车间生产调度。为此本文设计一种分段自适应遗传算法，随着进化代数和适应度函数自动调整交叉概率和变异概率，以期以较快的收敛速度搜索到全局最优解，从而满足实际生产应用的需要。

1 问题描述

流水车间调度问题（Flow shop Scheduling Problem, FSSP）是一种最重要的组合优化问题， 该问题通常可以描述为n个工件要在m台不同机器上加工，每个工件有m道工序，每道工序都要在不同的机器上加工，各个工件加工顺序相同，且满足如下的约束条件：1）每个工件在机器上的加工顺序相同，且给定加工顺序是1，2，3…，m；2）一个工件不能同时在不同的机器上进行加工；3）每台机器同时只能够加工一个工件；4）工序的准备时间与顺序无关，且包含在加工时间内；……