张晓霞 吕云虹

(辽宁科技大学软件学院 辽宁 鞍山 114051)

一种求解混合零空闲置换流水车间调度禁忌分布估计算法

张晓霞 吕云虹

(辽宁科技大学软件学院 辽宁 鞍山 114051)

结合混合零空闲置换流水车间调度问题MNPFSP(Mixed no-idle permutation flowshop scheduling problem)的特性，运用基于概率模型的分布估计算法解决该问题。算法将启发式算法融入分布估计算法中提高了初始解的质量。为了避免算法陷入局部最优，将禁忌算法融入分布估计算法中，提出一种禁忌分布估计算法求解混合零空闲置换流水车间问题。为了提高种群的多样性，加入了三种邻域搜索。实例测试结果显示，该算法求解混合零空闲置换流水车间问题具有很好的优势。

混合零空闲置换流水车间调度问题算法 分布估计算法 启发式算法 禁忌算法

0 引 言

置换流水车间调度问题属于经典的调度问题，它是在流水车间调度问题约束的基础上，进一步增加所有工件在任一台机器上的加工顺序均相同的约束后形成的生产调度问题[1]。零空闲置换流水车间调度问题NPFSP(No-idle permutation flowshop scheduling problem)是在置换流水车间调度问题的前提下，设置一台机器一旦开始加工就不能中断，直到加工完所有的工件。当前关于NPFSP的研究，在实际生产过程中，NPFSP是很少存在的，更多的是混合零空闲调度问题，因此研究混合零空闲置换流水车间调度问题MNPFSP具有十分重要的意义。

MNPFSP是典型NP难题。对于问题规模较小的MNPFSP，可以采用精确算法来求得问题的解，例如启发式算法等。但在解决实际问题的情况下，MNPFSP问题规模相对较大，问题相对复杂，此时不适合用精确算法求解该问题。……