李梦琳 马雯秋

[摘要]本文围绕着智能RGV的动态调度问题进行研究。以TSP问题为基础，建立了基于TSP问题的启发式RGV动态调度模型，并利用模拟退火算法进行求解，给出了一道工序情况下的RGV动态调度策略。

[关键词]TSP;最优序列;模拟退火算法

一、问题重述

一个智能加工系统包括8台计算机数控机床（CNC）CNC#1-CNC#8、1辆轨道式自动引导车（RGV）、1条RGV直线轨道、1条上料传送带、1条下料传送带。RGV是一种既可无人驾驶又可以在固定轨道上自由运行的智能车，它能够根据指令控制自身移动距离和方向，且其自带一个机械手臂、两只机械手爪和物料清洗槽，从而能完成上下料及清洗物料等任务。

针对一道工序的物料加工作业情况：每台CNC安装相同刀具，物料可在任一台CNC上完成加工。对于一般问题进行研究，给出RGV的动态调度模型和其相应的求解算法。

二、模型的建立与求解

在智能加工系统工作过程中，通常当CNC处于空闲状态或加工完成时会立即向RGV发出上料需求信号，此时RGV会接受CNC发出的信号并自行判断CNC的上下料作业次序，并通过发送指令信号来确定其服务CNC上下料的个数和顺序。考虑到一道工序系统作业流程是周期性循环的，因此定义一个作业周期是RGV为系统内所有CNC完成一轮服务的过程，在考虑RGV的调度问题时，由于RGV服务CNC的顺序不同会导致一个作业周期的时间不同，因此在制定调度策略时，我们要确定一个作业周期内RGV服务CNC的最优序列。

为了确定最优服务序列，我们需要分别确定序列中元素的个数和顺序。在一个作业周期内，使总时间最小的循环工作的CNC个数是最优序列个数。根据相关智能加工系统作业参数的数据计算得知，最优序列的元素个数为8个。

以下将基于SP算法确定最优序列。

设加工系统一个周期作业的总时间为T=t₁+t₂，其中t₁表示RGV为所有CNC提供上下料服务所需的时间，t₂表示RGV移动过程所需的时间。

由于在一个周期内，RGV服务的对象为CNC#1-CNC#8，因此RGV为CNC提供上下料服务的时间在不同序列顺序情况下都保持不变，而t₂会受到序列顺序的影响，因此，若希望总时间T最小，需找到RGV服务CNC的最佳顺序使得t₂最小。

考虑到序列中的元素个数为8，因此RGV在一次作业周期中对每台CNC都提供服务且只提供一次服务，因此我们建立基于TSP的RGV动态调度模型。

由于此问题是一个较复杂的优化问题，由于Lingo求解不一定能够得到全局最优解，因此采用模拟退火算法来寻求全局最优解。

针对以上通过模拟退火方法求得的CNC最优序列解，給出以下RGV调度方案：

考虑到RGV的移动受到CNC发出信号的影响，当有CNC向RGV发出信号时，RGV才会移动，而不同CNC发出信号的过程中，就存在RGV向哪边移动的选择问题，因此我们通过考虑CNC的信号发出情况来制定RGV的调度策略。

首先将信号的发出顺序分为两种：不同CNC同时发出信号、不同CNC先后（不同时）发出信号。

RGV在收集到CNC的需求信号后，会做出相应的判断和选择，决定前往工作台的顺序。若信号均不同时发出，则RGV收到何处的信号，就前往何处进行作业，即按照CNC信号发出时间先后顺序来决定RGV的移动;若存在信号同时发出，则需要RGV做出相应的判断，此时需要将同时发出的信号位置进行归类处理，以传送带为中心对称分布的两台 CNC作为一类信号（忽略纵向分布的工作台的先后顺序带来的影响，只考虑横向分布的工作台的信号发出顺序），可以分出四类信号，结果如表1。

将同时发出信号数量作为分类指标进行归类整理，分别针对不同的情况进行调度策略的选择。

其次企业只需根据实际情况制定调度策略即可。

最后针对此模型，作出如下评价：

将RGV与CNC之间的动态调度关系抽象为序列，构造TSP模型，寻找总路程最小的回路圈，具有一定的新颖性与合理性。本文使用了模拟退火算法找出TSP的最优解，结果真实可靠，计算方便。通过TSP问题求解出的最优解对应的序列，来求解具体每个零件的加工CNC序号、开始加工时间以及加工结束时间需要一定的计算过程。

参考文献：

司守奎，孙兆亮.数学建模算法与应用（第二版[M].北京：国防工业出版社，2015.