李夢(mèng)琳 馬雯秋

[摘要]本文圍繞著智能RGV的動(dòng)態(tài)調(diào)度問(wèn)題進(jìn)行研究。以TSP問(wèn)題為基礎(chǔ)，建立了基于TSP問(wèn)題的啟發(fā)式RGV動(dòng)態(tài)調(diào)度模型，并利用模擬退火算法進(jìn)行求解，給出了一道工序情況下的RGV動(dòng)態(tài)調(diào)度策略。

[關(guān)鍵詞]TSP;最優(yōu)序列;模擬退火算法

一、問(wèn)題重述

一個(gè)智能加工系統(tǒng)包括8臺(tái)計(jì)算機(jī)數(shù)控機(jī)床（CNC）CNC#1-CNC#8、1輛軌道式自動(dòng)引導(dǎo)車（RGV）、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶。RGV是一種既可無(wú)人駕駛又可以在固定軌道上自由運(yùn)行的智能車，它能夠根據(jù)指令控制自身移動(dòng)距離和方向，且其自帶一個(gè)機(jī)械手臂、兩只機(jī)械手爪和物料清洗槽，從而能完成上下料及清洗物料等任務(wù)。

針對(duì)一道工序的物料加工作業(yè)情況：每臺(tái)CNC安裝相同刀具，物料可在任一臺(tái)CNC上完成加工。對(duì)于一般問(wèn)題進(jìn)行研究，給出RGV的動(dòng)態(tài)調(diào)度模型和其相應(yīng)的求解算法。

二、模型的建立與求解

在智能加工系統(tǒng)工作過(guò)程中，通常當(dāng)CNC處于空閑狀態(tài)或加工完成時(shí)會(huì)立即向RGV發(fā)出上料需求信號(hào)，此時(shí)RGV會(huì)接受CNC發(fā)出的信號(hào)并自行判斷CNC的上下料作業(yè)次序，并通過(guò)發(fā)送指令信號(hào)來(lái)確定其服務(wù)CNC上下料的個(gè)數(shù)和順序。考慮到一道工序系統(tǒng)作業(yè)流程是周期性循環(huán)的，因此定義一個(gè)作業(yè)周期是RGV為系統(tǒng)內(nèi)所有CNC完成一輪服務(wù)的過(guò)程，在考慮RGV的調(diào)度問(wèn)題時(shí)，由于RGV服務(wù)CNC的順序不同會(huì)導(dǎo)致一個(gè)作業(yè)周期的時(shí)間不同，因此在制定調(diào)度策略時(shí)，我們要確定一個(gè)作業(yè)周期內(nèi)RGV服務(wù)CNC的最優(yōu)序列。

為了確定最優(yōu)服務(wù)序列，我們需要分別確定序列中元素的個(gè)數(shù)和順序。在一個(gè)作業(yè)周期內(nèi)，使總時(shí)間最小的循環(huán)工作的CNC個(gè)數(shù)是最優(yōu)序列個(gè)數(shù)。根據(jù)相關(guān)智能加工系統(tǒng)作業(yè)參數(shù)的數(shù)據(jù)計(jì)算得知，最優(yōu)序列的元素個(gè)數(shù)為8個(gè)。

以下將基于SP算法確定最優(yōu)序列。

設(shè)加工系統(tǒng)一個(gè)周期作業(yè)的總時(shí)間為T=t₁+t₂，其中t₁表示RGV為所有CNC提供上下料服務(wù)所需的時(shí)間，t₂表示RGV移動(dòng)過(guò)程所需的時(shí)間。

由于在一個(gè)周期內(nèi)，RGV服務(wù)的對(duì)象為CNC#1-CNC#8，因此RGV為CNC提供上下料服務(wù)的時(shí)間在不同序列順序情況下都保持不變，而t₂會(huì)受到序列順序的影響，因此，若希望總時(shí)間T最小，需找到RGV服務(wù)CNC的最佳順序使得t₂最小。

考慮到序列中的元素個(gè)數(shù)為8，因此RGV在一次作業(yè)周期中對(duì)每臺(tái)CNC都提供服務(wù)且只提供一次服務(wù)，因此我們建立基于TSP的RGV動(dòng)態(tài)調(diào)度模型。

由于此問(wèn)題是一個(gè)較復(fù)雜的優(yōu)化問(wèn)題，由于Lingo求解不一定能夠得到全局最優(yōu)解，因此采用模擬退火算法來(lái)尋求全局最優(yōu)解。

針對(duì)以上通過(guò)模擬退火方法求得的CNC最優(yōu)序列解，給出以下RGV調(diào)度方案：

考慮到RGV的移動(dòng)受到CNC發(fā)出信號(hào)的影響，當(dāng)有CNC向RGV發(fā)出信號(hào)時(shí)，RGV才會(huì)移動(dòng)，而不同CNC發(fā)出信號(hào)的過(guò)程中，就存在RGV向哪邊移動(dòng)的選擇問(wèn)題，因此我們通過(guò)考慮CNC的信號(hào)發(fā)出情況來(lái)制定RGV的調(diào)度策略。

首先將信號(hào)的發(fā)出順序分為兩種：不同CNC同時(shí)發(fā)出信號(hào)、不同CNC先后（不同時(shí)）發(fā)出信號(hào)。

RGV在收集到CNC的需求信號(hào)后，會(huì)做出相應(yīng)的判斷和選擇，決定前往工作臺(tái)的順序。若信號(hào)均不同時(shí)發(fā)出，則RGV收到何處的信號(hào)，就前往何處進(jìn)行作業(yè)，即按照CNC信號(hào)發(fā)出時(shí)間先后順序來(lái)決定RGV的移動(dòng);若存在信號(hào)同時(shí)發(fā)出，則需要RGV做出相應(yīng)的判斷，此時(shí)需要將同時(shí)發(fā)出的信號(hào)位置進(jìn)行歸類處理，以傳送帶為中心對(duì)稱分布的兩臺(tái) CNC作為一類信號(hào)（忽略縱向分布的工作臺(tái)的先后順序帶來(lái)的影響，只考慮橫向分布的工作臺(tái)的信號(hào)發(fā)出順序），可以分出四類信號(hào)，結(jié)果如表1。

將同時(shí)發(fā)出信號(hào)數(shù)量作為分類指標(biāo)進(jìn)行歸類整理，分別針對(duì)不同的情況進(jìn)行調(diào)度策略的選擇。

其次企業(yè)只需根據(jù)實(shí)際情況制定調(diào)度策略即可。

最后針對(duì)此模型，作出如下評(píng)價(jià)：

將RGV與CNC之間的動(dòng)態(tài)調(diào)度關(guān)系抽象為序列，構(gòu)造TSP模型，尋找總路程最小的回路圈，具有一定的新穎性與合理性。本文使用了模擬退火算法找出TSP的最優(yōu)解，結(jié)果真實(shí)可靠，計(jì)算方便。通過(guò)TSP問(wèn)題求解出的最優(yōu)解對(duì)應(yīng)的序列，來(lái)求解具體每個(gè)零件的加工CNC序號(hào)、開始加工時(shí)間以及加工結(jié)束時(shí)間需要一定的計(jì)算過(guò)程。

參考文獻(xiàn)：

司守奎，孫兆亮.數(shù)學(xué)建模算法與應(yīng)用（第二版[M].北京：國(guó)防工業(yè)出版社，2015.