魏殿恩　邵翰喬　靳瑾

摘? ?要：隨著工業(yè)發(fā)展對智能化需求的日益增長，RGV小車在運輸及倉儲方面的應(yīng)用也越來越廣泛，如何以最優(yōu)路徑調(diào)度成為了當(dāng)前需要解決的重要問題。本文針對無故障的一道工序加工情況，選取一道工序加工情況中的一個生產(chǎn)周期為研究對象，將RGV工作系統(tǒng)抽象為路徑網(wǎng)絡(luò)，并利用圖論中最短路徑的知識求得一道工序物料加工的最優(yōu)路徑。

關(guān)鍵詞：RGV動態(tài)調(diào)度? 圖論? 最優(yōu)路徑

中圖分類號：TP18? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼：A? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1674-098X（2019）10（c）-0079-02

一個智能加工系統(tǒng)是由8臺計算機(jī)數(shù)控機(jī)床、1輛軌道式自動引導(dǎo)車、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶等附屬設(shè)備組成的。RGV，即軌道式導(dǎo)引小車，國內(nèi)一般稱為穿梭小車或者穿梭車，是一種在車間或者自動化立體倉庫中沿著軌道運行的物料運送工具[1]。該小車是一種無人駕駛、能在固定軌道上自由運行的智能車。它根據(jù)指令能自動控制移動方向和距離，并自帶一個機(jī)械手臂兩只機(jī)械手爪和物料清洗槽，能夠完成上下料及清洗物料等作業(yè)任務(wù)。

1? 動態(tài)調(diào)度

將系統(tǒng)中固定在軌道兩側(cè)的CNC抽象為路徑網(wǎng)絡(luò)中的節(jié)點，其中將RGV軌道式引導(dǎo)小車簡化為一個質(zhì)點。根據(jù)先來先服務(wù)的調(diào)度準(zhǔn)則[1]，將第一輪上料順序理想簡化作為先上料后下料的順序。將8臺CNC上下料一次完整的過程看作為一個周期。為了使RGV的效率最高，擬定關(guān)于RGV一個周期內(nèi)運作時間t的函數(shù)如下所示。

已知RGV小車為奇數(shù)序號和偶數(shù)序號的CNC上下料一次的時間為定值，那么為了使一個周期內(nèi)RGV上下料所用的時間G（t）取得最小值，則需RGV在移動的過程中的時間取得最小值。

2? 圖論組合優(yōu)化

設(shè)軌道的路徑網(wǎng)絡(luò)通過表示。其中V為非空點集合;i表示節(jié)點;;W為權(quán)重系數(shù)集合，對每個節(jié)點都賦有一個耗費值Wi，對圖中的每條路徑Eij均賦予權(quán)重Wij。圖中無循環(huán)和多重弧存在，且圖中除了1、2;3、4;5、6;7、8節(jié)點不能互通，每一個節(jié)點均能經(jīng)過其他任意節(jié)點。其示意圖如圖1所示。

在此令表示任意節(jié)點m到節(jié)點n的所有路徑的集合，用Ls表示路徑的總耗費為各弧和各節(jié)點的耗費的總和，Ls的計算表達(dá)式如下。

當(dāng)W為隨機(jī)變量時，Ls也是一個隨機(jī)變量。最短路徑的問題即找到耗費Ls最少的路徑[2]，同時這也是一個組合優(yōu)化問題，即：

若使Ls最小，要求出目標(biāo)函數(shù)的最優(yōu)解，每個周期內(nèi)的流程如圖2所示。

3? 模型求解

根據(jù)上述模型，利用智能算法，求解出的最優(yōu)路徑為：

假設(shè)在連續(xù)8h工作過程中，CNC加工沒有出現(xiàn)障礙。建立上下料時間與各個過程的時間的函數(shù)關(guān)系。RGV加工系統(tǒng)作業(yè)過程中所耗費的時間為，其中表示RGV移動i個單位所消耗的時間，t4表示CNC加工完成一個一道工序所需的時間，t7、t8分別表示RGV為奇數(shù)編號和偶數(shù)編號的CNC完成一次上下料所需時間，t9表示清洗的時間。

在上述最優(yōu)路徑的一個周期中，建立的函數(shù)關(guān)系式如下。

（1）當(dāng)RGV按照模擬得出的最優(yōu)路徑進(jìn)行工作，依次上料并將1號CNC換料并清洗完畢時，所需時間大于等于8號CNC加工完成時間的函數(shù)關(guān)系如下所示。

（2）當(dāng)RGV按照模擬得出的最優(yōu)路徑進(jìn)行依次上料并將1號CNC換料并清洗完畢時，所需時間大于8號CNC加工完成時間，此時對于Tuλ沒有影響，而對Tdλ+1則會產(chǎn)生影響。影響后的Tdλ+1如下所示：

4? 結(jié)語

本文以RGV小車工作效率最高為目標(biāo)，使用動態(tài)調(diào)度模型得到了最優(yōu)的路徑。其中用到的最短路徑模型，國內(nèi)外許多文章都對路徑網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)節(jié)點重要性和量度進(jìn)行了論述。這類模型使用非常廣泛，可以推廣到現(xiàn)實生活中，在通信網(wǎng)絡(luò)和最小路徑規(guī)劃方面都有廣泛的應(yīng)用。模型中分析問題、解決問題用到的一些獨特的方法，對其他數(shù)學(xué)問題仍然適用。

參考文獻(xiàn)

[1] 申鴻燁，于維海.進(jìn)程先來先服務(wù)調(diào)度算法的動態(tài)演示研究[J].現(xiàn)代計算機(jī)：專業(yè)版，2017（22）：3-5.

[2] 張水艦，劉學(xué)軍，楊洋.動態(tài)隨機(jī)最短路徑算法研究[J].物理學(xué)報，2012，61（16）：1-10.