基于TSP模擬退火的智能RGV動態(tài)調(diào)度問題

李夢琳 馬雯秋

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

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

一、問題重述

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

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

二、模型的建立與求解

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

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

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

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

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

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

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

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

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

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

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

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

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

最后針對此模型，作出如下評價：

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

參考文獻(xiàn)：

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