基于蚁群—退火算法的RGV动态调度设计

金龙哲，张晓峰，曹维维，宋文韬，刘中南

(皖西学院，安徽 六安 237012)

0 引言

随着现代社会的发展，智能工厂成为当今工业化生产的主流，其中，智能加工系统很大程度上决定工厂的生产效率。常见的工厂加工系统由数控机床(CNC)、在轨道上往复运作的自动小车(RGV)、小车工作的直线轨道、用于上下料的传送带等附属设备组成。其中，RGV自动运作小车根据操作人员所下发的指令进行移动与转向，一般的RGV小车携带1个机械手臂、2只机械手爪进行物料的抓取与投放，物料的清洗在RGV小车的清洗槽上完成。在目前市场上RGV调度中，往往采用人工实时监测及就近控线原则进行RGV调度控制，该控制方法对整个系统的预测性、生产效率较低。因此本文针对RGV智能调度问题，设计了1套合适的调度算法，与普通调度相比提高了整个RGV加工系统的工作效率。

1 RGV调度模型的建立

设有1个由8台计算机数控机床(CNC)、1辆轨道式自动引导车(RGV)、1条RGV直线轨道、1条上料传送带、1条下料传送带等附属设备组成的智能加工系统，RGV根据指令能自动控制移动方向和距离，并自带1个机械手臂、2只机械手爪和物料清洗槽，能够完成上下料及清洗物料等作业任务。RGV排布如图1所示。

图1 RGV排布图

RGV工作图如图2所示。已知CNC对同种物料的加工时间相等，RGV为同侧CNC上下料及清洗的作业时间相同。因此在一定工时内，CNC的等待总时长越短，则CNC的利用率越高，加工的物料成品越多。可将CNC的等待时间最短的问题，转化为RGV小车移动总路径最短的问题。本文主要考虑无故障两道工序加工的问题。无故障两道工序加工指物料经过CNC有先后次序的两次加工，使物料产出最大。

图2 RGV工作图

两道加工工序首先要考虑CNC的分配问题，CNC的分配根据两道加工工序的加工时间比例进行确定，确定了两道加工工序分配到的CNC台数后，要考虑怎样进行安排，在安排时要考虑到RGV的移动距离以及两侧上下料的时间不同，安排完加工工序对应的CNC，要考虑RGV如何移动使系统效率最大化。

2 RGV调度算法设计

2.1 RGV基本调度原则

1)顺序排队算法[1]：在调度开始前，按照物料的完成时间从小到大排序，以此来调度小车。

2)就近算法：在原有的顺序排队算法的基础上计算小车移动到加工物料的CNC的时间，将原有的物料完成时间与小车移动到加工物料的时间相加，得到在就近算法下，新的从小到大顺序，即小车下一个会去接取时间最短的物料 。

3)CNC分配原则：由于第一道工序与第二道工序加工时间不同，所以在安装加工刀具时应按照两道工序的时间比例进行安装。当时间比例在1左右时平均分配CNC数量，否则，需要时间长的工序分配较多数量CNC。

2.2 求解算法设计

2.2.1 目标函数的建立

在某调度下，CNC加工一批物料时，所有物料加工结束时的最大完工时间[2]。而这个时间越小，说明在此调度下加工这批物料的效率越高。因此，为了求得最优调度，需要将最大完成时间的目标函数设置为求其最小值，其数学表达式如下

Tk=min{max(Lk)}

(1)

Lk=tn

(2)

其中Lk表示在第k种调度下的最大完工时间，n表示一批次物料的数量，tn表示第n个物料完工的时间，公式(2)表示最大完工时间与最后一个物料的完工时间相等。由于物料个数、CNC台数多，要求解Tk相当困难，并且Tk的解不止一种，对于目标多因素的求解方法，本文选择运用基于蚁群算法改进的退火智能算法进行求解。

2.2.2 混合智能算法设计

模拟退火算法的优点是能以一定概率从局部最优解跳到全局最优解，但搜索效率不高，由于退火每轮只能保存1个相对最优解，在搜索结果的过程中容易困在历史解中[3]。而群智能算法的优点是搜索效率高，搜索广度大，搜索速度快，但群智能算法容易陷入局部最优解，难以找到真正的解。因此本文结合退火算法与群智能算法的优点，将蚁群算法与模拟退火算法结合得到新的混合算法，结合两种特点，使搜索能力大幅度提高，解决RGV的动态调度问题。

本文模拟退火算法采用串行结构，蚁群算法采用并行搜索，从而提高了算法的优化性能，同时退火算法的概率突变性提升了蚁群算法的信息素更新能力，将搜索行为多样化。具体步骤见图3。

图3 混合算法步骤图

从图3中可以看出，蚁群算法给整个算法流程图提供初始接，模拟退火算法将得到的初始解进一步优化，依据Metropolis准则产生新解，蚁群算法随着新街的变化产生新的信息素，最后整体算法进行最优解的搜索。可见，新的混合算法不但有群智能算法的高效率，也有模拟退火算法的搜索全局最优的特点。因此为了提高动态调度的算法效率，可以采用混合算法。

2.3 系统的仿真

设置第一道与第二道工序时间如表1所示。

表1 第一道与第二道工序时间比设置表

在确定好CNC分配个数后，将各个CNC的调度时间算出来，带入混合智能算法，以公式(1)为目标函数，求解出调度原则，给出调度方案。将调度方案与普通方案进行对比，系统的作业效率可以为单位时间内系统加工物料数，经计算系统的作业效率见表2。

表2 系统的作业效率前后对比表

由表2可以看出系统的作业效率都有所提高，即本文的调度方案优于普通的就近原则调度。

3 结语

针对当前工业生产线上的加工系统，本文设计了一套基于蚁群-退火算法的RGV动态调度算法，并将传统的就近原则调度方式的加工效率与本文的调度算法仿真后的加工效率进行对比，效率有明显提高，可见本文算法的优越性。同样本文的调度算法还可应用其他领域，例如：模具电极调度问题、公交车调度问题、港口货物运输问题等类型的动态调度问题。多维度的应用能力体现本文所涉及的调度算法极好的应变性与适应力。