刘祝智

【摘 要】置换流水车间调度问题是一类经典的组合优化问题，智能优化算法是求解该问题的首要方法。遺传算法和分布估计算法在PFSP问题上均存在着一定的缺陷，即无法平衡局部搜索和全局搜索。为了克服它们的缺陷，本文将分布估计算法与遗传算法结合，并引入模糊逻辑控制来调节两种算法的参与率，最后用基准算例的测试结果证实了本文所设计的混合算法是有效的。

【关键词】置换流水车间调度；分布估计算法；遗传算法；模糊逻辑控制

0.前言

置换流水车间调度问题（PFSP）是对经典的流水车间调度问题进行简化后得到的一类子问题，最早在石化工业中得到应用，随后扩展到制造系统、生产线组装和信息设备服务上[1]。该问题一般可以描述为，n个待加工工件需要在m台机器上进行加工。问题的目标是求出这n个工件在每台机器上的加工顺序，从而使得某个调度指标达到最优，最常用的指标为工件的总完工时间（makespan）最短。

PFSP最早由Johnson于1954年进行研究[2]，具有NP难性质[3]。求解方法主要有数学规划，启发式方法和基于人工智能的元启发式算法[4]。数学规划等适用于小规模问题，启发式方法计算便捷，却又无法保证解的质量。随着计算智能的发展，基于人工智能的元启发式优化算法成为研究的重点。

遗传算法（GA）是研究与应用得最为广泛的智能优化算法，利用遗传算法求解PFSP问题的研究也有很多。遗传算法具有操作简单、容易实现的优点，且求解时不受约束条件限制。……