求解置换流水车间调度问题的一种混合算法

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

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

0.前言

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

遗传算法（GA）是研究与应用得最为广泛的智能优化算法，利用遗传算法求解PFSP问题的研究也有很多。遗传算法具有操作简单、容易实现的优点，且求解时不受约束条件限制。然而，遗传算法通常存在着过早收敛，容易陷入局部最优的现象。导致这一现象的原因在于遗传算法的交叉、变异操作具有一定的随机性，在求解PFSP问题的过程中往往会破坏构造块，产生所谓的连锁问题。为了克服遗传算法的缺陷，研究人员提出了一种不进行遗传操作的分布估计算法[5]（EDA）。EDA是一种运用统计学习的新型优化算法。相比GA，EDA在全局搜索上有较大的优势，而局部搜索能力不足，同样会导致局部最优[6][7]。以混合优化为思路，本文将设计一种EDA与GA结合的混合算法来求解PFSP问题，混合算法通过EDA的概率模型和GA的交叉变异操作两种方式来生成个体，并引入模糊控制理论[8]来自适应调节两种算法生成个体的比例。

1.置换流水车间调度问题

PFSP问题通常假设：

（1）n台工件在m台机器上加工。

（2）每个工件以相同的顺序在m台机器上加工。

（3）每个工件在每台机器上的加工时间是预先确定的。

（4）每台机器只能同时加工一个工件。

2.混合算法设计

2.1种群初始化

初始种群含有PS个个体，利用经典的启发式方法NEH[9]算法产生1个个体，其余PS-1个个体采用随机初始化的方法生成。

2.2选择

根据PFSP问题所给的加工时间表计算出种群中所有个体的总完工时间Cmax，显然Cmax越小，个体的质量就越好，据此可将评价个体好坏的适应度函数设为1/Cmax。本文选择的是轮盘赌法，加工时间越小，适应度值越高，个体被选择的概率也就越大

2.3概率模型

2.4局部搜索

对概率模型采样即可得到新一代的个体，对个体进行局部搜索可以提高EDA的性能[11]，本文将对较好的个体进行局部搜索，分别有如下三种搜索方法：

插入：选择一个工件并随机插入到某一位置。

交换：随机选择两个工件并交换其所在位置。

倒置：随机选择两个工件，将这两个工件之间的序列反转。

2.5交叉算子

2.6变异算子

2.7模糊逻辑控制

混合优化策略中，不同算法的比例是影响算法性能的关键，传统的算法比例混合方法主要包括固定比例和动态比例两种。使用固定比例时，比例值将在整个算法搜索过程中保持不变。这种方法需要进行试验来确定合适的比例值，其缺点在于为寻找到最佳比例值所需进行的试验多，耗时久。而动态比例调节则只需预先确定一个比例的初始值，而在运行过程中会根据搜索情况调节比例。调节方式又可以分为两种：一种是应用传统的启发式规则控制算法生成个体的比例，这些规则可以用确定的数学公式表示；而另一种是用人工智能技术自适应调整生成个体的比例，最常见的是将模糊逻辑应用于比例调节，能根据算法性能的变化来实现比例控制[12]。为了使混合算法具有优良的适应性，本文采用模糊逻辑控制来进行比例调节：在EDA表现良好时提高EDA生成个体的比例发挥其全局搜索的优势，在EDA求得解的质量下降时提高GA生成个体的比例，以避免出现局部最优。

3.EDA-GA混合算法

通过以上设计，EDA-GA混合算法的步骤如下：

3.1种群和概率模型的初始化

产生初始种群，迭代次数t=1，概率模型P中pij=1/n

3.2对种群个体进行评价并选择出优势个体

以轮盘赌法选择出用以更新EDA概率模型的优势个体和待进行交叉变异操作的父代个体。

3.3更新概率模型并对概率模型取样生成个体 对优势个体进行统计学习完成概率模型的更新，然后对概率模型抽样产生PS个个体，局部搜索后，把最好的rate（t）*PS个个体加入到下一代种群，rate（t）为当前EDA所生成个体的比例。

3.4交叉操作和变异操作

对父代分别进行交叉操作和变异操作，共产生（1-rate（t））*PS个个体，将这些个体加入到下一代种群中。

3.5模糊逻辑控制调节比例

新一代种群生成后，将种群平均完工时间与上一代进行比较，得到模糊输入量，根据模糊判断规则确定下一次迭代时EDA所生成个体的比例rate（t+1）。

3.6终止条件判断

4.实验结果

4.1参数设置

4.2结果分析

PFSP问题的基准算例有很多，其中Car和Rec类算例运行时间段短，计算快捷，因此选用这两种算例来验证本文所设计混合算法的有效性。每个算例用matlab独立运行10次，并与GA，EDA的结果进行比较。测试结果如表3所示。其中，BRE=×100、ARE=×100为每种算法求得的最优解C与三种算法测试所得的最好解C*的相对偏差百分比的最小值和平均值。

从表3的实验结果可以看出，对测试问题Car1～Car8和Rec01～Rec37，本文设计的EDA-GA混合算法ARE与BRE均优于EDA和GA，说明GA的引入使得EDA的优化性能有了很大的改进。对于Rec39、Rec41，混合算法BRE不如GA，说明优化性能稍弱于GA，但相比EDA解的质量有显著提高。因此总体而言，EDA-GA混合算法的性能是要强于GA和EDA。

5.结论

针对EDA和GA各自在全局搜索和局部搜索的不同侧重，本文设计了一种EDA-GA混合算法对以最小化总完工时间为优化目标的PFSP问题进行了求解。在混合算法中， EDA和GA各自生成一定比例的个体进行混合，在两种算法比例的调节上使用了模糊逻辑控制的方法，其中模糊输入量为每一代种群个体总加工时间的平均值的变化，而模糊输出量为EDA在下一次迭代中所生成个体的比例。由此，混合算法综合了EDA和GA的优点，运用Car和Rec类进行算例仿真，实验结果证明上述EDA-GA混合算法是有效的。 [科]

【参考文献】

[2]JohnsonS M.Optimal two-and three-stage production schedules with setup times included[J].Naval research logistics quarterly，1954，1（1）：61-68.

[3]Zhang Y，Li X.Estimation of distribution algorithm for permutation flow shops with total flow time minimization[J].Computers & Industrial Engineering，2011，60（4）：706-718.

[5]LarranagaP，LozanoJA.Estimationofdistributionalgorithms：Anewtoolforevolutionary

computation[M].Springer，2002.

[7]ChenSH，ChenMC，Chang P C，et al.Guidelines for developing effective estimation of distribution algorithms in solving single machine scheduling problems[J].Expert Systems with Applications，2010，37（9）：6441-6451.

[8]Chan F T S，Prakash A，Mishra N.Priority-based scheduling in flexible system using AISwithFLCapproach[J].International Journal of Production Research，2013，51（16）：4880-4895.

[9]Nawaz M，Enscore Jr E E，Ham I.A heuristic algorithm for the m-machine，n-job flow-shop sequencing problem[J].Omega，1983，11（1）：91-95.