基于貪心算法的RGV動(dòng)態(tài)調(diào)度研究

姜嘉沁　吳思琪　陳天祺

摘 要：本文主要研究智能 RGV 的動(dòng)態(tài)調(diào)度策略的問(wèn)題，針對(duì)一道工序情況下的 RGV 動(dòng)態(tài)調(diào)度進(jìn)行了分析。首先，利用繪制時(shí)間坐標(biāo)軸的方式，清晰刻畫每個(gè)時(shí)刻 RGV 和 CNC 的工作狀態(tài)，找出變量之間的相互關(guān)系;其次利用該函數(shù)關(guān)系，采用貪心算法，應(yīng)用 MATLAB軟件將已知數(shù)據(jù)代入模型進(jìn)行檢驗(yàn)。最后利用數(shù)據(jù)檢驗(yàn)結(jié)果可知，嚴(yán)格按照系統(tǒng)流程進(jìn)行操作時(shí)，該調(diào)度模式已經(jīng)達(dá)到較為高效的狀態(tài)。

關(guān)鍵詞：RGV 動(dòng)態(tài)調(diào)度;貪心算法;時(shí)間坐標(biāo)軸

引言

隨著我國(guó)科學(xué)技術(shù)的發(fā)展，現(xiàn)代化物流正在不斷發(fā)展和壯大，居民對(duì)高效的物流系統(tǒng)的要求越來(lái)越高，相繼而來(lái)發(fā)展的就是自動(dòng)化立體倉(cāng)庫(kù)。由于自動(dòng)化物流系統(tǒng)的高速發(fā)展，傳統(tǒng)物流系統(tǒng)存在的弊端就暴露出來(lái)，RGV 也就應(yīng)運(yùn)而生，它無(wú)需耗費(fèi)大量人力，大大提高了工作效率。

1. 模型建立

由于 RGV 的變化情況繁瑣復(fù)雜但存在一定的規(guī)律性，故選擇采取繪制如下

時(shí)間軸的方法，較為清晰地分析出各個(gè)變量之間的相關(guān)關(guān)系，其中，CNC1#～8#表示 CNC 上料時(shí)間。

上圖中各個(gè)點(diǎn)表示 RGV 給 CNC1#～8#上料對(duì)應(yīng)的時(shí)間，根據(jù)上述的示意圖推導(dǎo)出如下關(guān)系：

（1）假設(shè)當(dāng) RGV 開始為 CNC1#進(jìn)行上料作業(yè)為 0 時(shí)刻，則刨去初始特殊情況，接下來(lái)每臺(tái) CNC 開始上料時(shí)刻隨著周期的變化存在一定的規(guī)律特征，故可根據(jù)之間的相關(guān)關(guān)系列出 8 臺(tái) CNC 開始上料的時(shí)間函數(shù)式如下：

（2）根據(jù)上述時(shí)間示意圖，與第一次 CNC1#加工產(chǎn)生熟料相比較，每經(jīng)過(guò)tc+t3時(shí)間，CNC1#會(huì)生成一單位熟料，而其余 7 臺(tái) CNC 的產(chǎn)量和 CNC1#的關(guān)系只存在兩種狀態(tài)，一種等于 x1，另一種等于 x1-1，故 CNC1#加工生產(chǎn)量可表示為：

2. 求解算法

貪心算法是采用逐步求解最優(yōu)解的方法，它是指在問(wèn)題求解的過(guò)程中，不考慮整體最優(yōu)情況，而是采取每步最優(yōu)策略，得到在當(dāng)前階段下的局部最優(yōu)解。上述模型的建立即是建立在貪心算法的基礎(chǔ)上，每一個(gè)階段智能選擇最優(yōu)路徑，在本模型中，RGV 則是嚴(yán)格按照順序依次對(duì) CNC 進(jìn)行作業(yè)。

對(duì)于一道工序的物料加工情況分析，RGV的動(dòng)態(tài)調(diào)動(dòng)運(yùn)行模式為按照其接收信號(hào)的順序?qū)ο鄳?yīng)的 CNC 進(jìn)行上下物料作業(yè)和熟料的清洗工作。此時(shí)，我們假設(shè)固定軌道上有四臺(tái) RGV 智能車，當(dāng)系統(tǒng)啟動(dòng)時(shí)，四臺(tái)智能車將同時(shí)運(yùn)作，分別負(fù)責(zé)其相鄰兩臺(tái)CNC 的上下物料及清洗工作。

由于在每?jī)膳_(tái)的 CNC 設(shè)備之間都有一臺(tái) RGV 單獨(dú)負(fù)責(zé)其相關(guān)的加工相關(guān)作業(yè)，故而此時(shí)的產(chǎn)出量必然為一道工序加工作業(yè)下的最大物料產(chǎn)量。運(yùn)用繪制時(shí)間軸的方式分析后可得每一臺(tái) CNC 的加工產(chǎn)量滿足以下關(guān)系式：

在前文的求解過(guò)程之中已經(jīng)求得 x1的關(guān)系式，故而選取 x1作為檢驗(yàn)?zāi)Ｐ褪欠褚呀?jīng)達(dá)到最優(yōu)的代表量。有如下關(guān)系：

故而可看出此模型已經(jīng)達(dá)到最優(yōu)化。

結(jié)論：

通過(guò)本文研究發(fā)現(xiàn) RGV 在運(yùn)行過(guò)程中會(huì)對(duì)首先發(fā)出信號(hào)的 CNC 進(jìn)行裝配，因?yàn)檫@一點(diǎn)所以 RGV 會(huì)產(chǎn)生忽略近處 CNC ，而跑去遠(yuǎn)處 CNC 進(jìn)行加工的情況，所以本文采取最小路徑、就近原則等條件對(duì) RGV 的調(diào)度進(jìn)行優(yōu)化，達(dá)到產(chǎn)出最大化的目的。

參考文獻(xiàn)：

[1]M， H， AlSUWANEI. 算法設(shè)計(jì)技巧與分析[M]. 北京：電子工業(yè)出版社， 2004.

[2]陳敏瑩. 基于動(dòng)態(tài)規(guī)劃的微弱目標(biāo)檢測(cè)前跟蹤算法研究[D]. 西安：西安電子科技大學(xué)， 2013.