混合遗传算法求解车间作业调度问题

周海峰

（江苏广播电视大学，江苏 南京 210017）

混合遗传算法求解车间作业调度问题

周海峰

（江苏广播电视大学，江苏 南京 210017）

所谓生产调度问题，其实质如何分配资源使其更优化.这里我们所讲的资源指的是车间生产所需的设备资源.对车间生产作业调度问题进行求解，其目的就是要找出一个能够将一组工件更为科学、合理的安排到机器上从而实现最优化的生产作业方案.本文采用一种启发式算法和遗传算法相结合的混合遗传算法，在运用过程中给出其应用方法.

启发式算法；遗传算法；车间作业调度

1 生产调度问题

调度就是指对共同使用的资源进行统一的时间分配，其作用是为了实现某一目的.而本文所提出的车间作业生产调度，则是指利用一组机床在加工一组零件时，对每台车床加工工件的顺序进行合理的安排，实现诸如总加工时长、总加工成本或相对加工时长等指标的最优化.通常若干不同工序组成了零件的整个加工过程，并且该过程要满足对应的约束关系.在车间作业调度过程中，约束条件的内容与数量会随着作业环境及作业要求的变化而变化，比如加工设备条件或者零件的加工工艺要求等等.

本文定义n个工件的集合为：P={P1,P2,…,Pn}；而m台加工车床的集合则为：M={M1,M2,…,Mm}；工件Pi加工工序数目定义为Ki；则其加工工序定义为：Pi1(Ji1),Pi2(Ji2),…,PiKi(JiKi)(Ki∈Z+,i=1,2,…,n)这其中Z+为正整数，零件Pi在进行第Ki道工序表示为JiKi，（JiKi∈M）；而被加工零件经过第Ki道工序加工的开始时间表示为STiKi；被加工零件Pi在进行第Ki道工序的加工的结束时间表示为ETiKi；TiKi为工件Pi加工第Ki道工序的时间.按照上文所述的定义，则车间作业调度的约束条件为以下几个：第一，每个工序中均包含一个工序集合，该工序集合由多道工序组合而成，且要预先给定工件加工工序的顺序；第二，某台机器同时只可以加工一个零件的其中一道工序；再次，加工零件不一样，其各工序间不存在先后的约束条件，工件相同，其工序需符合前后的约束关系；第四，工序PiKi(JiKi)和PiKi+1(JiKi+1)，二者的时间相距为零，即STiK-i+1-ETiKi=0；第五，每个零件在进行每道工序加工时，其开始时间要大于等于零，即STiKi+1-ETiKi=0；第五，每个工件每道加工工序的开工时间必须大于或者等于零，即STiKi≥0；第六，所有的要件要在预定交期前全部完工，设Ti为加工工件Pi的总时间，即∑TiKi=Ti.

2 混合遗传算法

本文所提出的混合遗传算法的应用为：将启发式算法融入遗传算法中，再利用该混合算法求解车间生产调度排序的问题.遗传算法为一种群体优化算法，其通过选择和变异及交叉等不同操作，不断的进化解集性能，从而可以使搜索的速度得到进一步提高.不过遗传算法也存在不足，即难以控制早熟及收敛性等问题.作为传统的启发式算法，有着搜索速度快且结构简单的优点，但是其也存在搜索能力差且容易陷入局部最优等不足.基于二者的优势与不足，将其进行结合，将启发式算法融入遗传算法中，重新构造出的混合遗传算法能力更强，对于求解比较复杂的优化问题有着积极的意义.该混合方法融合了遗传算法的记忆功能和并行性，并将其与启发式算法的快速搜索优势相结合，使得求解质量得到了进一步的提高.具体来讲对遗传算法进行改进的方法主要为以下几点：第一，将启发式嵌入初始化中，产生一个初始解群，且该初始解群要具备良好的适应性能，这种方法可以使混合遗传算法优于启发式算法；第二，把启发式融入评估函数中，将染色体进行解码转换为生产调度；第三，对个体变异及交叉率进行自适应设计.上述几点中，在进行个体中全局搜索时主要采用遗传算法；而对染色体部分搜索则利用启发式算法.由于启发式与遗传算法二者存在相应的互补性，所以二者相混合的算法更优于两种单独算法.

3 利用混合遗传算法进行车间作业调度的求解

3.1 参数编码

在进行遗传算法的求解过程中，要将问题所在空间的相关参数转化为遗传空间的参数，还要经过基因依据所对应的结构组成染色体，这个将问题空间参数向着遗传空间参数转化的过程可以称之为编码.编码的表达方法有很多，有基于工序的、基于工件的或者基于位置列表的以及基于机床的表达等等，本文所采用的是基于机床的表达方法.将染色体进行编码为设备序列，以该序列为基码，编码的具体实现为：

工件编号为1,2,3,…n；各工件的对应的工序编号为1,2,3,…k；对应的机床编号为1,2,3,…m.从而符号1.1.1则代表工件1的1工序在机床1上完成，以3（工件）×3（机床）为例：假如工件的加工工序最多为4，机床所对应不存在的加工工序则定义为0.0.0，工件的各加工工序要能满足工序先后关系的约束.

3.2 生成初始种群与设计适应度函数

可以通过随机产生的方法来产生初始种群，以便于达到解空间所有状态的遍历.对约束条件进行检验，判断其是否为可行解，假如判断结果为是，则将其加入初始种群，如果不是则淘汰.不过由于初始群体为随机产生，因此进化的代数有所加大，从而遗传算法的计算时间也相应大幅度增加.此处加入启发式算法，将该算法局部搜索能力强的特点加以充分利用，从而优良个体产生的速度就有所提高.个体适应函数应为工件总加工时间单调递减函数，即个体适应度的函数值随着总工时的减小而增加，反之总工时越大，则个体适应度的函数值就越小.个体i的适应函数值可以进行以下定义：

上式中：Cmax是f(x)的最大值估计.

3.3 交叉操作

交叉算子利用一点交叉运算，参与交叉运算的包括两个个体母体M与父体F，按照自适应交叉概率Pc进行相应的交叉运算.记交叉运算两个体体母体M及父体F，其经过交叉运算所产生的子代个体记为D与S，L是染色体的长度.整数p为随机生产，且1

上式中：fmax：群体最大适应度值

favg：每代群体平均适应度值

f：要交叉的两个个体比较大的适应度值.

算法的收敛程度和自适应调整为反向关系，因此防止算法收敛于局部最优十分有效，并且可以保存更优的进化结果.

3.4 变异操作

利用互换变异进行变异操作，即整数m先随机生成，其取值范围为机床的数量.在该机器中随机选择某一工序，将该工序和相临的工序进行互换.需要注意的是，在变异时要看相临的工序是否为加工同一工件.其自适应变异概率Pm进行如下定义：

3.5 目标函数

本文求解的目标为工件完工时间的最小化，其目标函数为：

其中 i=（1，2…n）

4 结论

生产调度问题为NP问题，即可用多项式时间算法对其猜测准确性加以验证，因此最优解确定算法相对较难确定.而且遗传算法又具体备相应的优良特性，因此在车间生产调度问题方面，遗传算法为后续的研究趋势.本文所提出将启发式规则融入遗传算法的混合遗传算法，在进行调度算法的求解过程中，即可以发挥遗传算法的长处，又可以充分利用启发式算法快速搜索的特点，从而取得了更优的分配效果，且通过实例可以证明，该方法所求解的调度结果相对较优.

〔1〕(日)玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社,2007.

〔2〕鞠全勇,朱剑英.基于混合遗传算法的动态车间调度系统的研究[J].中国机械工程,2009(11).

〔3〕祁建程,杨建刚.并行混合遗传算法在车间调度问题的应用[J].计算机应用与软件,2011(1).

〔4〕丁书斌,李启堂,徐继涛，等.混合遗传算法求解经典作业车间调度问题[J].煤矿机械,2007(1).

〔5〕杨开兵.多目标混合遗传算法求解流水车间调度问题[J].电脑与信息技术,2008(6).

〔6〕张华,陶泽.基于混合遗传算法的车间调度问题的研究[J].机械设计与制造,2005(3).

TP18

A

1673-260X（2011）09-0018-02