基于遗传算法的RGV智能车动态调度

曹言，曹家赓，吴灵媛

（1.华北理工大学机械工程学院；2.华北理工大学经济学院；3.华北理工大学理学院，河北 唐山 063210）

RGV是一种无人驾驶、能在固定轨道上自由运行的智能车。它根据指令能自动控制移动方向和距离，并自带1个机械手臂、2只机械手爪和物料清洗槽，能够完成上下料及清洗物料等作业任务。目前RGV已经广泛运用到柔性生产制造流程中，其调度规划问题成为生产决策的重点。

图1是一个智能加工系统的示意图，由8台计算机数控机床（Computer Number Controller，CNC）、1辆轨道式自动引导车（Rail Guide Vehicle，RGV）、1条RGV直线轨道、1条上料传送带、1条下料传送带等附属设备组成。

图1 智能加工示意图

1 模型的初步建立

针对RGV动态运动的两种情况：（1）一道工序的物料加工作业情况，每台CNC安装同样的刀具，物料可以在任一台CNC上加工完成。（2）两道工序的物料加工作业情况，每个物料的第一和第二道工序分别由2台不同的CNC依次加工完成；建立动态调度模型并提供相应的求解算法，以解决整个车床加工零件变化情况。

智能加工系统的效率主要取决于：（1）调度：给RGV选择和派送任务的过程。（2）路径：RGV从输送源到目的地所走的路程，RGV调度是以子任务步为单位进行的，每个子任务步需RGV的两次操作，也就是RGV从上料传送带取到物料和将清洗后的成料放到下料传送带上，这样才能完成一个物料的加工。

考虑运输时间对系统作业流程RGV调度的问题：n个物料 {J1，J2，J3...Jn}要在 8台机器 {M1，M2，M3...Mn}上加工。每个物料包含一道或两道工序，每道工序可以选择不同的CNC加工，只能选择其中一台CNC，选择不同的加工机器所需的加工时间和运输时间也不一样。Ojh为第j个工件的第h道工序，并定义Oj(h-1)表示第Ojh的前一道工序，Oj表示物料当前所在机器的一道工序。物料J的每道工序在机器i上的加工时间是给定的，设为（J=1,2,3,…,n;i=1,2,3,…,8）。RGV调度需要为每块物料的每道工序选择最合适的CNC，使得物料的加工时间达到最小。

物 料 集 J={J1，J2，J3...Jn}，CNC集 M=Mi（i=1,2,3,…,8），Tj为物料一道工序的加工时间，Tj1为物料加工的两道工序中的第一道工序所需的加工时间，Tj2为物料加工的两道工序中的第二道工序所需的加工时间，Time1为RGV为CNC1#，3#，5#，7#一次上下料所需时间，Time2为RGV为CNC2#，4#，6#，8#一次上下料所需时间，Tj为RGV移动所需时间（n=1,2,3）。Cj为第i个物料的完工时间，Cmax为最大完工时间。考虑最小化最大完工时间，目标函数的约束条件为：

式（4）表示若工序j在第i道的开始加工时间小于前一道工序运输结束时间，则受运输时间约束；否则，工序受当前加工机器的资源约束。即考虑了运输时间对于同一机器的相邻工序的加工效率影响。

2 遗传算法求解

遗传算法（Genetic Algorithm, GA）最先是由美国的John Holland于1975年提出的。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。

（1）遗传算法的编码。遗传算法首要解决的是编码的问题，本文采用基于工序的整数编码，将工序排序和机器选择这两个子问题编成一条染色体，用来表示RGV调度的一个可行解。①工序排布部分：工序的实数编码。工件号表示每个基因的位置，每个工件号出现的次数代表这个工件对应的工序数，整个染色体长度为所有工件的所有工序数总和。例如一个可行基因串2-2，对应的工序是O21-O22，表示工件J出现的次数对应第几道工序。②机器选择部分：采用CNC上的编码。例如一个可行基因串3-2，表示的是工序O21可在CNC3#上加工，工序O22可在CNC2#上加工，如此类推。（2）初始化方法。由于遗传算法的求解质量和收敛度会受到初始解优劣的影响。随机初始化是最常使用的方法。由于本文是基于生产时间建立的模型，因此问题的可行解搜索范围比一般问题的求解还要大。故本文将采用考虑工序加工时间和运输时间的最短工作法，RGV在每道工序上选择就近较优的CNC来获得较优的初始解，收敛寻优一个物件加工过程的最优时间。（3）交叉。通过交叉操作可以让两个染色体交换基因，得到新一代个体，新个体组合了其父辈个体的特性。本文将通过部分映射交叉的方式实现基因交换，如图2所示，根据随机选中的工件集{2,4}，保持父代基因不变，然后将父代基因映射交叉得到2个子染色体。从染色体中随机选择一个基因位，在该位置随机选择一个加工机器代替染色体中那个被选中的加工机器。具体如图2所示，其中黄色部分表示基因变异部分。（4）变异。通过随机改变染色体中的一位或多位基因，产生新的染色体，模拟生物遗传中的变异。当群体早熟时，变异可以跳出局部最小，改善 GA 的局部搜索能力，增加种群的多样性。（5）解码。将染色体从左到右进行解码，工件号出现的次序表示工件要加工的工序，根据两道工序的加工机器和加工时间确定整个RGV的调度过程，并计算生产调度过程中的最大完工时间。关键是需要将工序排序部分解码成对应于机器选择部分的活动调度，具体的解码步骤如下：①读取工序部分的基因转换为相应工序Ojh；②获取该工序Ojh的加工机器Mi=JM(j，h)，并获取加工时间Pjh=T(j，h)；③计算该工序Ojh的最早加工时间Sjh和完工时间Cjh，其计算公式为：在考虑物料加工作业过程中的工序加工时间时，考虑运输时间和调整时间，计算最大完工时间。

图2 映射交叉

通过遗传算法以最大完工时间为目标调度对问题进行求解，设遗传算法中的初始种群为100，交叉概率为0.8，变异率为0.01，通过100次的迭代，求出物料加工时间的最优最大完工时间为862s。

3 结语

最优化的车床的运输次序分别为CNC1-CNC2-C N C 3-C N C 4-C N C 5、和，能够加工的最优工件数分别为376与211件。

通过RGV动态调度问题由简到繁研究，车间生产能够依照调度模型更合理地安排生产，减少不必要的等待时间与因故障浪费的调度时间，并科学筹划车辆调度的路线，使总生产时间最小，从而达到生产资源的节约与优化。