基于改进的布谷鸟算法求解流水车间调度问题

高杨 云晓燕

摘  要：针对基本的布谷鸟算法在求解流水车间调度问题时存在搜索能力差、收敛速度慢的缺点，提出了一种高斯扰动的布谷鸟搜索算法（GCS）。该算法不仅增加了鸟窝移动的活力，还改善了搜索能力差的情况。仿真实验结果表明，改进的布谷鸟算法在求解流水车间调度问题上具有良好的优化性能，要优于基本的布谷鸟算法。

关键词：流水车间调度问题;高斯扰动;搜索速度

中图分类号：TP18;TB497     文献标识码：A 文章编号：2096-4706（2019）13-0018-03

Solving Flow Shop Scheduling Problem Based on Improved Cuckoo Algorithms

GAO Yang，YUN Xiaoyan

（School of Software，Liaoning University of Science and Technology，Anshan  114051，China）

Abstract：Aiming at the shortcomings of the basic cuckoo algorithm in solving flow shop scheduling problems，such as poor search ability and slow convergence speed，a new cuckoo search algorithm based on Gauss perturbation （GCS） is proposed. This algorithm not only increases the vitality of birds nest movement，but also improves the poor search ability. The simulation results show that the improved cuckoo algorithm has good optimization performance in solving flow shop scheduling problems，and is superior to the basic cuckoo algorithm.

Keywords：flow shop scheduling problem;Gauss perturbation;search speed

0  引  言

隨着世界各地的经济与技术的发展，城市整体规模不断扩大，我国成为制造业大国，产品需求量非常大。因此流水车间调度问题（Flow Shop Scheduling Problem，简称为FSSP）在先进制造业中受到了广泛的关注。

流水车间调度问题在车间生产中是极其常见的问题，也一直被认为是NP-hard问题。在求解流水车间调度问题上不但有通过启发式来解决的，另外还有通过仿生智能优化方式或群智能算法来解决的。上世纪70年代—90年代，蚁群算法、禁忌算法、遗传算法、粒子群算法、分布估计算法、萤火虫算法、贪婪算法[1-8]等一些智能优化算法逐渐被科学家提出并在实际的工程领域内取得了很大的成功。

本文针对流水车间调度的问题，提出了一种改进的布谷鸟算法。该算法与高斯扰动相结合，进而提高了搜索性能，实验结果表明该算法与基本的布谷鸟算法相比，在求解流水车间调度问题上得到了很好的改良。

1  FSSP问题的数学模型

流水车间调度问题是一个加工资源分配的问题，它主要是在满足某些加工机器、完工时间、资源配置等约束条件下，对车间的任务进行最佳分配。在满足一定的约束条件下，流水车间调度问题可描述为：一个加工系统中有n个工件要在m台机器上加工，每个工件包含a道工序，工件的加工顺序是一定的，每道工序在不同机器上加工。假设工件i在机器x上的加工时间确定，设加工的时间为tj（i=1，2，…，n;j=1，2，…，n）。该问题的主要目的是n个工件在每台机器上的加工顺序一定时，使得最小化最大完工时间[9]。在上一个假设成立的前提下，流水车间还可描述为：

（1）每个工件在每台加工机器上的加工顺序一定;

（2）每个工件在同一时间时只能在一台机器上加工;

（3）每台机器在同一时间时只能加工一个工件;

（4）工件工序的就绪时间与顺序无关，且包含在总加工时间内。

令C（ji，k）代表工件ji在机器k上完成工作时所用的时间，每个工件工作的顺序为（j1，j2，…，jm），则n个工件在m台机器上完成工作时所用的时间为：

2  基本布谷鸟算法

布谷鸟搜索（Cuckoo Search，CS）算法是由Xin-She Yang和Suash Deb开发的一种新型元启发式搜索算法，是模拟布谷鸟繁衍后代所提出一种新型群智能优化算法[11]。布谷鸟的繁殖策略就是找到和它们能产出相似的卵的鸟巢并将它们的蛋放入这个鸟巢里，同时避免这个鸟发现，它们也会移走寄主巢中的一个或多个蛋，保持鸟巢内的蛋数目不变，这样增加了自己蛋的孵化概率。如果寄主发现了该行为，寄主就会扔出外来蛋或是寻找新地方来搭建自己的鸟窝。CS算法就是通过模拟布谷鸟寻找适合孵化自己下一代鸟巢的方式来寻找最优值。为了模拟布谷鸟的繁衍机制，Yang等在文献中设定了3种理想状态[11]：

（1）每只布谷鸟一次只产一枚卵，并随机找到一个鸟窝来孵化;

（2）在随机选择的这些窝的过程当中，选择最好的鸟窝将会保存到下一代;

（3）选择的鸟窝数量n是一定的，设寄主发现外来卵的概率是Pa，Pa∈[0，1]，倘若寄主发现了鸟窝中有外来的蛋，它们就会放弃自己现有的鸟窝另寻地方搭建自己新窝。

在上文的三个理想状态基础上，参考布谷鸟孵化鸟蛋的过程，布谷鸟寻巢的位置更新公式如下：

其中a为步长的大小，并且一般情况下a=1。⊕为点对点乘法。Levy（λ）是随机搜索的路径，并且a服从Levy分布。Levy（λ）～u=t-λ，（1<λ≤3）。xi（t）代表第t代鸟窝在第i个鸟窝的位置。随机产生一个数Ra，Ra与Pa进行数值比较，若Ra>Pa，则对xi（t+1）进行随机改变鸟巢位置，获得一组新的鸟巢。否则不变。比较出新鸟窝位置与当前鸟窝位置哪个是最优解，并保留这个最优解。

3  求解流水车间的GCS算法思想

GCS算法是在CS算法的基础上加了个高斯扰动，更加快速地找到了更优的鸟窝位置。若CS算法在第t次循环时找到了一组较优的鸟窝的位置为：xi（t）i=1，2，…，n。而这个GCS算法就是在CS算法执行第t次循环时加入高斯扰动，不让它执行下一次循环，而是进一步搜寻。设矩阵Pt=[x1（t），x2（t），x3（t），…，xn（t）]T，令Pt为m*n阶矩阵。则GCS为Pt′=Pt+a⊕β。其中β为m*n阶矩阵，⊕为点对点乘法，因为β的取值范围比较大，所以设a=1/4来控制β的取值范围，进而适当地增大了鸟窝移动的活力，经过高斯扰动得到了一个Pt′，让它与Pt进行比较，得到更优的位置，再继续进行GCS算法，得到下一个更优的位置Pt″。

4  GCS算法具体实施步骤

Step1：初始化参数，随机产生宿主鸟窝的个数为n，外来蛋发现的概率为Pa，寄生鸟窝的维度为m，初始化鸟窝的位置。

Step2：依照测试函数计算出当前最优鸟窝的位置Xj（0）j ∈{1，2，…，n}和最优值Fmin。

Step3：保留上一代最优鸟窝的位置，并操作Step2對剩余鸟窝的位置进行更新，获得最新的一组鸟窝位置，并对这组鸟窝进行测试，将最优鸟窝位置与上一代鸟窝位置进行比较，得出一组最优的位置来替代之前的鸟窝位置，令最新的一组鸟窝位置为Kt=[x1（t），x2（t），x3（t），…，xn（t）]T。

Step4：在最新的一组鸟窝位置中，用服从随机分布的r∈[0，1]与Pa进行比较。若r>Pa，则保留Kt中发现几率最小的鸟窝位置，并对剩余鸟窝的位置进行随机改变，获得一组新的鸟窝位置Pt。

Step5：对Pt加入高斯扰动，又得到一组鸟窝的位置Pt′，与Pt进行比较得出最优的一组鸟窝位置，让测试值中最好的替换之前的鸟窝位置，令现在最优的一组鸟窝位置为Pt″，并将Pt″赋值给Pt，以便更好地进入下一次循环。

Step6：对Pt连续执行Step4的步骤，在Pt中找到最优的鸟窝位置和最优解为Fmin，并且判断Fmin是否达到了算法的终止条件，倘若达到，则输出最优位置和最优值，不然连续执行这个Step3。

5  仿真实例

为了进一步测试GCS算法的搜索性能，本文中选用了Benchmarks测试函数集中的Sphere函数、Rastrigin函数进行测试，用于测试GCS算法的函数参数如表1所示。首先设鸟窝数量n=20，维度为10，并且最大迭代次数为4000，若迭代次数大于4000认为寻优失败。测试函数如下：

6  结  论

本文的目的是最小化最大完成时间，在基本布谷鸟算法迭代的过程当中对更新后的鸟窝位置加入高斯扰动，扩大了搜索范围，增加了鸟窝位置变化的多样性。与基本布谷鸟算法寻优结果比较，得出改良后的布谷鸟算法搜索性能更好，证明了该算法在求解流水车间调度的问题中是有效的。

参考文献：

[1] 刘延风，刘三阳.多构造蚁群优化求解置换流水车间调度问题 [J].计算机科学，2010，37（1）：222-224.

[2] 屈国强，周永良.蚁群优化结合变邻域搜索求解NWFS调度问题 [J].计算机工程与应用，2012，48（16）：216-219+248.

[3] 张建萍，张武贞.基于改进的禁忌搜索算法求解车间作业调度问题 [J].信息技术与信息化，2011（3）：77-80.

[4] 姚嫣菲.基于改进遗传算法的车间作业调度问题研究 [D].杭州：浙江大学，2011.

[5] 王凌，刘波.微粒群优化与调度算法 [M].北京：清华大学出版社，2008：114-137.

[6] 王轩，李元香.分布估计算法在车间调度问题中的应用研究 [D].青岛：中国石油大学（华东），2012.

[7] 李永林，叶春明.基于萤火虫算法的零等待流水线调度优化 [J].机械设计与研究.2013，29（6）：50-54.

[8] Pan Q K，Wang L，Zhao B H . An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion [J].The International Journal of Advanced Manufacturing Technology，2008，38（7-8）：778-786.

[9] 肖辉辉，段艳明.基于差分进化的布谷鸟搜索算法 [J].计算机应用，2014，34（6）：1631-1635+1640.

[10] Yang X S，Deb S . Cuckoo Search via Levy Flights [J].Mathematics，2010：210-214.

作者简介：高杨（1997-），女，汉族，辽宁朝阳人，本科在读，研究方向：软件工程。