求解静态流水车间调度的改进遗传算法

文/顾蕾

1 引言

目前，制造业虽然发展快速，但是很多制造业企业的生产车间还是在使用以人的经验为主的生产调度方式。生产一线工人主要依靠自己日积月累的经验来进度产品生产的调度，在这种模式下很难实现生产的标准化，很容易产生生产设备使用不均衡、浪费时间等问题。这一系列文体的产生无形之中推动了生产方式的创新，科学合理的基于人工智能化的生产调度方式由此产生。静态流水车间是在开始调度之前全部工件就已经做好即将加工的准备，假设不会发生突发故障，开始加工后工件像流水一样流入流出。在这种车间模式下所有的工件加工步骤都是一样的。

Johnson[1]最先解决了两台机床的flowshop调度问题，从此专家学者么开始了对于不同类型车间的调度问题的研究。在此之前的生产调度问题的解决全是依靠工人们积累的经验来解决的，后来人们开始使用运筹学、线性规划、拉格朗日松弛、分支定界法等应用数学的方法来解决生产调度问题。再后来人们开始引入算法，依靠智能算法去解决生产中的调度问题，例如启发式算法，Rajendran和Ziegler[2],Wang等[3]就依靠启发式算法解决了某些类型车间的调度问题。当前情况下，相对来说由Framinan和Leiste[4]给出的一种构造型启发式算法，算是最优的启发式算法。最近时间，人们对于遗传算法的研究越来越深入，更多的学者开始选择使用遗传算法来解决各种类型车间的调度问题[5-7]。但是标准的遗传算法本身就存在一定的缺陷，例如容易出现早熟或者容易陷入局部最优。这些缺点如果在算法实际执行之前不解决的化，就会带入到实际的应用当中，那么我们得出的所谓的最优解很有可能并不是最优解。本文针对GA的这些缺陷，对标准GA进行交叉和变异上的改进，提出一种改进遗传算法对静态流水车间进行求解，并验证改进后的结果更优。

2 问题描述

静态流水车间调度问题研究就是在调度之前就做好准备的n个工件逐个流入m台机器中（假设机器不会发生故障），工件排成一队在m台机器上一次性流过，一台机器一次只能加工一个工件，每个步骤的准备时间和加工时间已知，求解此类型车间最优的调度方案。

3 求解静态流水车间调度的改进GA算法

3.1 求解思想

当要解决实际生产当中的问题的时候，选取的算法的效率是否能满足需求是解决问题的关键。首先要做的就是选取具体的参数合集，然后通过使用GA算法去寻找此参数合集当中的最优解。我们在选取参数的时候主要关注群体的规模、交叉率和变异率这几项指标。当我们选取求解的参数不同时，GA算法的性能也会受到不同的影响，求解的结果也会不相同。综上所述，要想体现GA算法的最优性能，最先要做的就是选取合适的参数集。

当通过算法去进行问题的优化的过程中，如何去选择合适的Pc和Pm，这是是需要不断地试验反复的尝试才能够确认的，这是一个相当复杂繁琐的过程，需要不断地尝试，尝试过后确定最佳的Pc和Pm。

在改进的CA算法中，要求Pc和Pm的值不是固定的，而是要随着个体适应度的变化二变化的。当种群在进行搜索的时候出现个体适应度越来越靠近或出现局部最优的时候，Pc和Pm的值会自动增加，使种群的适应度趋于分散然后跳出局部最优的困境。当种群在进行搜索的时候出现个体适应度越来越分散的时候，Pc和Pm的值会反方向变动，通过减小概率来保证优良的个体能够不被淘汰。在交叉和变异的过程中，如果个体适应度高于群体平均水平，Pc和Pm的值自动降低，保证此个体能维持高适应度然后进入到下一代；如果个体适应度低于群体平均水平， Pc和Pm的值自动升高，使该个体在交叉或者变异的过程中被淘汰[8]。所以Pc和Pm在改进后的GA算法当中并不是固定的数值，而是随着适应度的变化而改变的。

3.2 求解步骤

3.2.1 编码

该编码方式选取以工件在机器上的加工顺序来进行编码，即n道工序的编码长度就为n，基因数为n-1，以10道工序编码为例，随机产生一组编码：σ7，σ6，σ8，σ10，σ9，σ4，σ3，σ5，σ2，σ1，该编码用集合来表示：

T(ji,k)表示工件σi在机器k上的加工所需时间， n个工件在m台机器上的加工所需要的时间为：

最大完成时间为：

求的是{σ1，σ2,…,σn}，使得Tmax的值最小，即求最小化最大完成时间。

3.2.2 生成初始种群

随机生成初始种群，然后取适应度高的个体，把它们放入随机种群当中，然后在随机产生个体，如此反复进行下去，直到达到需要的种群数后跳出循环。

3.2.3 个体适应度函数

求解的目标函数为适应度函数，Ckmax为最大完成时间函数，表示第k个染色体的最大加工完成时间。用此公式来计算单个染色体的适应度。适应度函数为：

3.2.4 GA算子的设计

（1）选择。锦标赛选择法：

每一轮里选择一个选项后，在之前的选择中再进行选择。通常最后的选择就是锦标赛的“获胜者”。选取n个个体，个体i的适应度用Fi表示，此时个体i可能被选中遗传到下一代的概率为：

（2）交叉。

1.随机选择父本个体两个；

2.随机生成两个自然数r1和r2，r1＜r2；

3.将r1至r2之间的片段互换位置，得到两个新的子代，然后得到的两个子代进行修补，使其存在冲突

例如：取父本基因片段为[d,c,a,b,e][e,c,b,d,a]；r1=2,r2=4；

进行交叉得到：[a,c,b,d,e][e,c,a,b,a]；

进行修补后得到：[a,c,b,d,e][e,c,a,b,d]；

（3）变异。

1.随机选择父本个体两个r1，r2

[a,c,b,d,e][e,c,a,b,d]；

2.逆转变异

随机从染色体中截一段基因，接着把该片段反序置换，然后插回断裂处。

例如：r1=2,r2=4；那么染色体的变异为[a,d,b,c,e][e,b,a,c,d]

3.3 算法实现

采用国际标准算例15×15来进行标准GA算法和改进GA算法的比较。

3.3.1 标准GA算法

例：种群数M=100，迭代次数T=150，代沟GGAP=1，交叉率Pc=0.3，变异率Pm=0.2；工件数n=15，工序数m=15。

3.3.2 改进GA算法

例：种群数M=100，迭代次数T=150，代沟GGAP=1，交叉率Pc1=0.3，Pc2=0.5；变异率Pm1=0.1，Pm2=0.3；工件数n=15，工序数m=15。

3.4 结果比较

3.4.1 最优工序发生变化

标准遗传算法：

改进遗传算法：

3.4.2 最小最大时间改变

根据结果可知在40代时就已经取得了最优，出现早熟现象，对标准遗传算法进行改进从迭代曲线可以看出标准遗传算法在迭代到40代的时候就达到了最优，出现过早收敛现象，而改进后的迭代结果现实在60代以后才开始出现收敛，同时求解最小最大完成时间得出后者时间更短。

4 结论

本文从静态流水车间着手解决其调度问题，采用GA算法求解后发现出现早市现象，于是进行算法改进，引入可自我调节的交叉率和变异率，改进后的GA算法，经过标准算例认证，明显优于标准GA算法得出的结果，改进后的GA算法解决了标准GA算法出现过早收敛的问题，从而达到要求的优化效果，对于静态流水车间的调度优化提供了更多一种方法。