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

• Data Base Technique

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

文/顾蕾

Ziegler[2],Wang等[3]就依靠启发式算法解决

本文选取静态流水车间作为摘了某些类型车间的调度问题。当前情况下，相 研究对象，主要针对标准遗传算 要法进行改进。提出一种交叉率PcLeiste[4]给出的一种构以及变异率Pm对来说由Framinan和随个体适应程度改变而改变，能够使个体更快跳出造型启发式算法，算是最优的启发式算法。最局部最优或能够保护优良个体的改进遗传算法。选择个体的时候近时间，人们对于遗传算法的研究越来越深采用锦标赛选择法，在一定范围内设置可变的交叉率和变异率，入，更多的学者开始选择使用遗传算法来解决变大或变小根据适应程度改变。各种类型车间的调度问题[5-7]。但是标准的最后选取标准算例来验证，通过真实数据证明改进后的遗传算法遗传算法本身就存在一定的缺陷，例如容易出更能够跳出过早收敛，最小最大时间明显缩短。现早熟或者容易陷入局部最优。这些缺点如果在算法实际执行之前不解决的化，就会带入到实际的应用当中，那么我们得出的所谓的最优

【关键词】静态流水车间 生产调度 遗传算法解很有可能并不是最优解。本文针对GA的这些缺陷，对标准GA进行交叉和变异上的改进，提出一种改进遗传算法对静态流水车间进行求

1 引言

解，并验证改进后的结果更优。

目前，制造业虽然发展快速，但是很多2 问题描述

制造业企业的生产车间还是在使用以人的经验为主的生产调度方式。生产一线工人主要依靠静态流水车间调度问题研究就是在调度自己日积月累的经验来进度产品生产的调度，之前就做好准备的n个工件逐个流入m台机在这种模式下很难实现生产的标准化，很容易器中（假设机器不会发生故障），工件排成一产生生产设备使用不均衡、浪费时间等问题。队在m台机器上一次性流过，一台机器一次

这一系列文体的产生无形之中推动了生产方式只能加工一个工件，每个步骤的准备时间和加的创新，科学合理的基于人工智能化的生产调工时间已知，求解此类型车间最优的调度方案。

度方式由此产生。静态流水车间是在开始调度3 求解静态流水车间调度的改进GA算法

之前全部工件就已经做好即将加工的准备，假设不会发生突发故障，开始加工后工件像流水3.1 求解思想

一样流入流出。在这种车间模式下所有的工件当要解决实际生产当中的问题的时候，加工步骤都是一样的。

选取的算法的效率是否能满足需求是解决问题Johnson[1]最先解决了两台机床的的关键。首先要做的就是选取具体的参数合集，flowshop调度问题，从此专家学者么开始了对然后通过使用GA算法去寻找此参数合集当中于不同类型车间的调度问题的研究。在此之前的最优解。我们在选取参数的时候主要关注群的生产调度问题的解决全是依靠工人们积累体的规模、交叉率和变异率这几项指标。当我的经验来解决的，后来人们开始使用运筹学、们选取求解的参数不同时，GA算法的性能也线性规划、拉格朗日松弛、分支定界法等应用会受到不同的影响，求解的结果也会不相同。数学的方法来解决生产调度问题。再后来人们综上所述，要想体现GA算法的最优性能，最开始引入算法，依靠智能算法去解决生产中先要做的就是选取合适的参数集。

的调度问题，例如启发式算法，Rajendran和

当通过算法去进行问题的优化的过程中，

118 •电子技术与软件工程 Electronic Technology & Software Engineering

如何去选择合适的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，该编码用集合来表示：

Vi=[7 6 8 10 9 4 3 5 2 1]

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

（1）

（2） （3） （4）

Data Base Technique 数据库技术

最大完成时间为：

Tmax=T(σn，m) （5）σ2,…,σn}，求的是{σ1，使得Tmax的值最小，d,b,c,e][e,b,a,c,d]3.3 算法实现

法。

•

参考文献

即求最小化最大完成时间。3.2.2 生成初始种群

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

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

Fit(vkk)=1/Cmax

3.2.4 GA算子的设计

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

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

（2）交叉。

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

2.随机生成两个自然数r1和r2，r1例如：取父本基因片段为[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,

采用国际标准算例15×15来进行标准GA[1]宋存利.求解混合流水车间调度的改进

算法和改进GA算法的比较。贪婪遗传算法[J].系统工程与电子技3.3.1 标准GA算法

术,2019,05:1079-1086.

例：种群数M=100，迭代次数T=150，[2]Fajendran C, Ziegler H. An efficient

代沟GGAP=1，交叉率Pc=0.3，变异率heuristic forscheduling in a flowshop Pm=0.2；工件数n=15，工序数m=15。to minimize total weightedflowtime 3.3.2 改进GA算法

of jobs [J]. European Journal 例：种群数M=100，迭代次数T=150，ofOperational Research,1997,103: 代沟GGAP=1，交叉率Pc1=0.3，Pc2=0.5；变129～138.

异率Pm1=0.1，Pm2=0.3；工件数n=15，工序数[3]Wanc C,Chu C, Proth J M. Heuristic

m=15。approachesfor n /m /F /∑ 3.4 结果比较Cischeduling problems [ J ].European Journal of Operational Research, 3.4.1 最优工序发生变化

1997,96: 636～644.

标准遗传算法：

[4]Framinan J M,Leisten R. An efficient

7→3→9→13→15→11→2→4→8→14→6constructiveheuristic for flowtime →5→10→1→12；

minimization in permutationflow 改进遗传算法：

shops[J]. OMEGA,2003,31: 311～317.8→13→7→14→15→2→4→1→3→9→6[5]王芳,唐秋华,饶运清,张超勇,张利

→11→5→10→12。平.求解柔性流水车间调度问题的高效分3.4.2 最小最大时间改变

布估算算法[J].自动化学报,2017(02).根据结果可知在40代时就已经取得了最[6]鞠全勇,朱剑英.基于混合遗传算法的动

优，出现早熟现象，对标准遗传算法进行改进态车间调度系统的研究[J].中国机械工从迭代曲线可以看出标准遗传算法在迭代到程,2007,(1):40-43.

40代的时候就达到了最优，出现过早收敛现[7]张志鹏, 黄明.基于改进多目标遗传算法

象，而改进后的迭代结果现实在60代以后才求解混合流水车间调度问题[J].计算机开始出现收敛，同时求解最小最大完成时间得应用与软件,2015,10:291-293+314. 出后者时间更短。

[8]顾蕾，基于改进遗传算法的流水车间调度

4 结论

研究[D].南昌大学,2016.

本文从静态流水车间着手解决其调度问

题，采用GA算法求解后发现出现早市现象，

作者简介

顾蕾（1990-），女，河北省邢台市人。硕士

于是进行算法改进，引入可自我调节的交叉

研究生。广东理工学院经济管理学院标准化工

率和变异率，改进后的GA算法，经过标准算

程教研室主任。主要研究方向为生产系统标准

例认证，明显优于标准GA算法得出的结果，

化与优化。

改进后的GA算法解决了标准GA算法出现过

早收敛的问题，从而达到要求的优化效果，对

于静态流水车间的调度优化提供了更多一种方

作者单位

广东理工学院 广东省肇庆市 526000

Electronic Technology & Software Engineering 电子技术与软件工程• 119