基于自适应遗传算法的流水车间作业调度
沈 斌1，周莹君2,3，王家海2
【摘 要】流水车间调度问题是NP完全问题。提出一种新的自适应遗传算法，采用初始种群复合化、适应度相同个体的筛选策略、改进自适应交叉变异概率等方法提高算法性能。通过仿真比较，从最优解出现的代数、最优解的相对误差以及随机若干次试验对算法的影响3个方面证明该算法的优越性。 【期刊名称】计算机工程 【年(卷),期】2010(036)014 【总页数】3
【关键词】自适应遗传算法；流水车间作业调度；算法改进
流水车间作业调度问题又称为流水车间加工排序问题，是离散制造业车间调度的一种类型。该问题作为生产管理中的重要课题被广泛研究。
1 流水车间调度问题
流水车间调度问题一般可以描述为：n个工件在m台机器上加工，每个工件需要经过 m道工序，每道工序要求不同的机器，n个工件在m台机器上的加工顺序相同，并有如下假设：(1)每个工件在机器上的加工顺序相同，且是确定的；(2)每台机器在每个时刻只能加工某个工件的某道工序；(3)一个工件不能同时在不同机器上加工；(4)工序的准备时间与顺序无关，且包含在加工时间中。 流水车间调度问题就是求满足最大完工时间最小化的最优化调度方案。
2 NG自适应双种群遗传算法
2.1 编码设计
本文采用最自然的编码方式，即用染色体表示工件的顺序，工件的个数就是染
色体的长度。 2.2 适应度函数确定
对于n个工件、m台机器的流水车间调度问题，设工件在机器上的加工时间为 ti j(i=1,2，…,n; j=1,2,… ,m)，工件的调度顺序为 J1,J2,… ，Jn，工件Ji在机器k上的完工时间为c( Ji,k)，求解最大完工时间的步骤如下：
适应度函数是指对个体进行评价，是优化过程发展的依据，遵循的原则是保证最大化问题和非负性，一般由目标函数进行线性变换、幂函数变换、指数变换来得到适应度函数[1]。以最大完工时间作为目标函数，适应度函数表示为其倒数。令表示k个染色体vk的最大完工时间，则适应度函数表示为 2.3 算子改进 2.3.1 种群复合化
本文采用NEH启发式算法[2]和加权时间启发式算法[3]相结合的启发式算法，随机产生初始种群以提高搜索效果和质量，使初始种群分散地分布于解空间。群体规模影响遗传优化最终结果和执行效率，若较小则不能提供足够采样点，若较大则会增加计算量，导致收敛时间过长，因此，其取值一般为50～200。 2.3.2 带非线性排序的轮盘赌选择
本文采用带非线性排序[4]的轮盘赌选择法进行选择操作，以避免算法过早收敛。 2.3.3 NG自适应操作
遗传算法是一个动态寻优过程，恒定的控制参数不一定合理，而自适应控制参数则有助于调整算法的搜索行为和能力。一种方案是G自适应[5]在进化初期采用较大的遗传概率确保种群在全局范围内搜索，当进化后期逼近最优解时，种群应该采用较小遗传概率来增强局部搜索能力和加速收敛。另一种方案是在进
化过程中随着个体适应度函数、群体中最大适应度函数以及平均适应度函数之间的关系，即时调整自适应参数，典型方法有F、Sin、Cos[4]。对上述方案描述如下：
(1)G自适应，根据适应度及进化代数来调节个体的交叉率、变异率，具体如下： 其中，pc为交叉概率； pc_max 为最大交叉概率； pc_min为最小交叉概率；pm为变异概率； pm_max为最大变异概率； pm_min为最小变异概率；itmax为最大迭代代数；iter为当前代数；f'为需要交叉的2个个体的较大适应度； f为需要变异的个体适应度； favg为种群平均适应度。
(2)F自适应，根据种群最大适应度和平均适应度来调节交叉变异概率，即 由式(7)～式(10)可以看出，G自适应在迭代次数小时，交叉变异概率大，当迭代次数大时，其交叉变异概率小。F自适应在个体适应度较大时，交叉变异概率小，当个体适应度较小时，交叉变异概率大。如果当迭代次数小时，个体适应度较小，则G与F的策略是相同的，即交叉变异概率较大。若当迭代次数小时，个体适应度较大，则G自适应还是选择较大的交叉变异概率，将导致适应度好的个体流失，因此，本文在既考虑迭代次数和染色体适应度值的情况下，对G进行改进，提出新的 NG(New Genetic)自适应操作，即随机分配2个因子权重。自适应参数设计的数学表达式如下： 其中，α、β为随机产生的权重系数。 2.3.4 复合交叉
本文采用单位置次序交叉 Reeves法[6]和线性次序交叉LOX[7]相结合的随机复合交叉操作，能使父串的特征通过多种方式遗传给子串，从而子串能部分或全部继承父串结构特征和有效基因。
基于自适应遗传算法的流水车间作业调度
