基于Memetic算法的RGV动态调度模型

王 帅

（长春光华学院基础教研部，吉林长春 130033）

1 简述

RGV引导车在工作周期内不会出现故障等情况,其连续移动1 个单位,2 个单位和3 个单位的时间不同,每台数控机床CNC 一次只能加工一个物料[1]。利用TS算法处理RGV运行轨迹如图1所示。

图1 RGV运行轨迹图

采用Memetic算法处理流程图如图2。

图2 Memetic算法处理流程图

对于基于Memetic 算法的调度模型研究很多主要将算法的求解结果和设定问题的下界进行比较[2-3]。为了对模型的实用性进行检验,可以利用相关的数据进行处理,分析比较两个算法的数据,运用问题一所建立的模型将智能加工系统作业的三组参数分别代入模型求解。数据代入模型,由此可得,RGV的平均流经时间,CNC 完成一个两道工序的物料所需的总时间,RGV 上下物料的总时间,清洗作业的时间。然后求和总用时和CNC的效率。

2 模型假设与约定

模型建立假设8 台数控机床CNC 分别标号si,i=1,2,3,4,5,6,7,8;RGV 引导车在工作时间内不会停止工作。xrli为物料Ji存储在上时其值为1 否则为0;yrKi为当物料Ji是机床N上第k次加工的物料时其值为1否则为0;为当物料Ji完成处理到下料传送ωie带上时,e值为1 否则其值为0;ziv为当运送i由RGV 来执行时v值为1否则其值为0。

3 RGV动态调度模型建立

给定一组物料在机床上加工序列在确定RGV 搬运物料时间后决策变量,xrli,yrKi,ωie与ziv的值都能确定此时直线往复RGV 调度问题的模型可构建如下:当有RGV 在轨道上有序的给任意CNC 机床按放生料,在加工过程中CNC未出现故障的情况下利用题目中给定的系统作业参数计算,利用TS 算法对该过程求解。以下约束成立条件组为:

r=1,…,m;l=1,…,n;i=1,…,NUM;

e=1,…,N;v=1,2,

使得Gi-1≤Gi,i=2,…NUM;

以上约束给出了RGV 的上料顺序和RGV 运送的开始时间、完成时间、开始位置和完成位置的计算方式;当任意CNC 发生故障时，将可能发生CNC 故障的情况进行归纳总结分为以下4类故障处理，约束其中故障i和故障j为两个不同的机床发生故障,满足i≠j,当有故障机床i分配给其他CNC1,故障机床j分派给其他CNC2,待机床修复后重新进行工作。具体TS算法流程图如图3。

图3 TS算法流程图

对于两道加工过程的物料加工作业情况,利用以工序为标准的编码方式进行工序编号,即每一道工序都对应相应的工号,要保证每个物料号出现的次数与物料的工序总数相等,然后利用Memetic 算法中的染色体次序方法进行编译,第k次出现的物料序号,就是该物料的第k次工序。对于m个物料在n台上加工的调度问题,记任务i是在CNC 上的操作为Oicnc每个操作所需时间为Ticnc,T(Oicnc)为操作Oicnc的开始时间,m(i)为在第i个CNC 上加工的物料总数目,目标是最小化最大完工时间。即数学表达式为:min{max(T(Oi,m(i))+Ti,m(i))}i=1,2,…,n式中约束条件有，同一物料不同操作之间的时间约束:

T(Oi+1,m(i))-Tij≥T(Oij)，

同一CNC不同操作之间的时间约束:

T(Oi,m(i)+1)-Tij≥T(Oij)，

每个操作的开始时间为正T(Oij)≥0。假设当出现:机床3 出现故障,导致加工时间延误10～20 分钟,利用Memetic 算法要对所有工序进行重新调度,来解决出现故障情况下的RGV调度和CNC。

4 模型求解

已知RGV工作以及CNC机床调度对于一道工序和两道工序的物料加工情况（包含CNC 故障时的调度情况）,依据所建立的模型以及求解方案可以有以解决策略。

当加工生料i分配给CNCS1,加工生料j分派给CNCS2，且加工生料i的开始位置大于等于加工生料j的开始位置时,约束3 保证了加工生料j开始后加工生料i开始前S2有足够的时间载货驶过并上料;加工生料i的开始位置S1到达加工生料i的开始位置的最早时间为Gj+u+,此时CNCS1与CNCS2不会发生冲突,当加工生料i的开始位置大于等于加工生料j的完成位置时,约束4 保证了加工生料j完成后加工生料i开始前v2 有足够的时间空行驶过上料;加工生料i的开始位置,当加工生料i的完成位置大于等于加工生料j的开始位置时,约束5 保证了在加工生料j开始后加工生料完成前v2 有足够的时间载货驶过上料,加工生料i的完成位置v1到加工生料i的完成位置的最早时间为Gj+u+,加工生料i的最早完成时间为Gj+u+,当加工生料i的完成位置大于等于加工生料j的完成位置时，约束6保证了在运送j完成后加工生料i完成前，S2有足够的时间空行驶过加工生料i的完成位置。具体RGV调度求解如下:

利用TS 算法处理两道工序的物料加工如图4所示。

图4 TS算法处理两道工序的物料过程图

对于给定系统作业参数的三组数据，由平均流经时间方程可知

由工序完成时间方程可知，完成一道工序的物料所需时间:T1=c1；完成两道工序的物料所需总时间:T11=c11+C12。假设任务开始的时间为:T(Oij)=0，根据题目给出的RGV在各个CNC上下料的时间,RGV完成一个物料清洗的时间S以及公式:

Tmin=min{max(T(Oij)+T1+T11+S)},

代入求解,CNC 加工完成一个一道工序物料所需的最小总时间为:Tmin1，CNC 加工完成一个一道工序物料所需的最小总时间为:Tmin12。

依据所给的系统作业参数对问题一建立的两类模型进行相应的实用性检验和算法的有效性校验。

5 模型检验

模型采用TS（禁忌搜索）算法,将连续8 小时作业情况绘制成图5和图6所示。

图5 一道物料加工顺序

图6 两道物料加工顺序

从图5-6 可以看出8 小时对于一道工序的作业情况,该流程较为效率合适。在一个工作周期内,不能够有效的处理故障情况,对于TS 算法处理两道工序该算法的效率较低。对于使用TS算法进行直线的RGV部分调度情况如图7所示。

图7 两道物料加工顺序

图7所示RGV 调度搜索过程是根据CNC 发出的请求搜寻最近的目标,当出现故障情况时,对RGV 调度影响较大,对其工作会效率影响较大。

同样为验证算法的有效性将TS算法的求解结果与设定问题的下界进行比较。记为TS算法求得的解的平均值则与下界的定义下表给出了9 组算例的计算结果如表1所示。

表1 组算例的计算结果

以两道工序为基础,采用Memetic 算法对RGV 引导车进行调度和数控机床CNC 的分配。图示说明了利用Memetic 算法进行两道工序的操作是相对高效的,能够在作业时间内对物料进行合理的一道工序加工，其效率和TS算法比较是更高效的，从图中清晰可见完成一道工序的数量上也领先于TS算法。

RGV调度搜索过程的最优解,和平均解之间有较小的差距,说明故障情况对RGV 调度影响较小,相应的工作效率较高。为了验证算法的有效性本文同样将Memetic 算法的求解结果也和设定问题的下界进行比较。记Cts为TS 算法求得的解的平均值则Cts与下界的gap定义为：gap=(Cts-LB)/LB。

表2给出了9组算例的计算结果。

表2 组算例的计算结果

通过对TS 算法和Memetic 算法的校验能够看出Memetic 算法更适用于该种情况的智能RGV 动态调度,其中TS 算法对于故障的处理能力要远低于Memetic算法,Memetic 算法对于发生故障时对RGV 小车的重新调度和CNC的重新分配更为稳定。