基于現(xiàn)代優(yōu)化算法對RGV動態(tài)調(diào)度問題的研究

王晨旭 漆映彤 盛瑋桐

摘 要：研究軌道式自動引導車（RGV）的動態(tài)調(diào)度問題對自動化倉庫領(lǐng)域以及物流系統(tǒng)具有重要的意義。本文重點考慮了兩道工序的物料加工作業(yè)情況，基于現(xiàn)代優(yōu)化算法建立了動態(tài)調(diào)度模型，給出了最優(yōu)的調(diào)度方案。針對兩道工序的物料加工作業(yè)情況，本文以基于現(xiàn)代優(yōu)化算法中的遺傳算法對其進行求解，并且在編碼過程中摒棄了常用的一維編碼，進行了二重結(jié)構(gòu)編碼，接著再結(jié)合數(shù)據(jù)進行了模型實用性和算法有效性的檢驗，得到此種情況下三組數(shù)據(jù)產(chǎn)出的成品個數(shù)分別為159，161，165，系統(tǒng)作業(yè)效率較高，結(jié)論為該模型較為合理。

關(guān)鍵詞：遺傳算法;RGV;動態(tài)調(diào)度

引言

智能加工系統(tǒng)是通過充分利用各種機械，運輸設(shè)備，計算機系統(tǒng)和綜合作業(yè)協(xié)調(diào)等技術(shù)手段，更精準，高效的完成加工物流的相關(guān)作業(yè)和內(nèi)容。軌道自動導引車RGV擁有價格低廉，靈活和方便的特點，它能方便地與各種數(shù)控機床，機器人等加工設(shè)備實現(xiàn)連接，進行作業(yè)，提高工作效率，因此被廣泛應(yīng)用于智能加工系統(tǒng)。在智能加工系統(tǒng)的運輸系統(tǒng)中，軌道式自動引導車RGV的效率是瓶頸，因此RGV的動態(tài)調(diào)度是關(guān)鍵。

1. 模型準備

RGV是一種無人駕駛、能在固定軌道上自由運行的智能車。它根據(jù)指令能自動控制移動方向和距離，并自帶一個機械手臂、兩只機械手爪和物料清洗槽，能夠完成上下料及清洗物料等作業(yè)任務(wù)。圖1為一個示意圖，它表示一個智能加工系統(tǒng)，且這個加工系統(tǒng)由8臺計算機數(shù)控機床、1輛軌道式自動引導車、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶等附屬設(shè)備組成。

根據(jù)經(jīng)驗，無論是幾臺CNC的協(xié)同運作，對其進行調(diào)度的核心是用時最短，也就是效率最高，還可以理解為走的路徑最短。因此此種情況便可以理解成存在一些約束條件的情況下，將一款產(chǎn)品從一個地方運輸?shù)搅硪粋€地方，而目標函數(shù)則可以看成所有的運送過程中最晚完成運送的時間。然后再用遺傳算法對此問題就行求解，最后將數(shù)據(jù)帶進模型進行檢驗，并求得此時的最優(yōu)調(diào)度策略以及系統(tǒng)的作業(yè)效率。

2 .RGV動態(tài)調(diào)度模型建立及求解

遺傳算法解決的關(guān)鍵步驟便是編碼，編碼不僅決定了個體基因的排列方式，決定了GA搜索的復雜程度和困難程度，也決定了最終求解的精度。

本文只考慮含有一個RGV小車的情況，由于兩道工序中的協(xié)作任務(wù)是成對出現(xiàn)的，常規(guī)的一維編碼（二進制編碼）便難以解決此問題，因此在這里可以使用二重編碼。如下所示：

即可以將1和3號CNC進行搭配，2和4號CNC進行搭配，6和7號CNC進行搭配，5和8號CNC進行搭配。

Step1：產(chǎn)生初始化的種群。

群體的初始化值一般隨機生成，初始值最好可以在解空間中均勻采樣;而對于非二進制的編碼程序還必須要思考所產(chǎn)生的染色體是否在可行域內(nèi)。

Step2：個體的目標函數(shù)和適應(yīng)度值的計算：目標函數(shù)為運送完一組出入貨任務(wù)所用的總時間。

Step3：選擇、交叉、變異。

首先選擇要用的算子以及選擇操作。常用的個體選擇概率的方法有按比例的適應(yīng)度分配以及基于排序的適應(yīng)度分配。

按比例的適應(yīng)度分配也可稱為蒙特卡洛算法，它通過利用各個個體適應(yīng)度的概率決定它后代遺留的可能性。若某個體為p，它的適應(yīng)度為fp ，那么被選中的幾率為：

顯然，若個體的選擇概率較大，則能夠被更多次的選中，而它的遺傳因子也將不斷在種群中擴大。

但是在基于排序的適應(yīng)度分配中，適應(yīng)度僅僅取決于一個個體在一個種群中的地位，并非實際目標值。

其次，進行交叉操作。對于常用的二進制編碼，我們可以使用均勻交叉，單點交叉以及多點交叉等方法。

最后，進行變異操作。常用的變異操作有二進制變異法、實值變異法。

對于上述模型本文采用matlab遺傳算法工具箱進行計算。再將相關(guān)數(shù)據(jù)代入模型進行檢驗，得到三組數(shù)據(jù)下分別產(chǎn)出的成品個數(shù)為159，161，165。得出結(jié)論為該模型實用性較強，算法較為有效。

結(jié)論：

與傳統(tǒng)的優(yōu)化算法不一樣，本文的算法是基于現(xiàn)代優(yōu)化算法而來的，這種啟發(fā)式算法可以大大節(jié)省運算的時間，并且可以將模型進行簡化，相比于一般的規(guī)劃類問題較為簡便。遺傳算法因其具有良好的全局搜索能力，可以快速地將將空間中的全體解搜索出，不會陷入局部出現(xiàn)死循環(huán)，且其使用概率機制進行迭代，具有隨機性，結(jié)論更加客觀可靠。

參考文獻：

[1]張劍秋.基于馬爾科夫排隊模型的流水車間調(diào)度問題研究[D].蘭州理工大學，2017.

[2]司守奎，張兆亮.數(shù)學建模算法與應(yīng)用[M].北京：國防工業(yè)出版社，2017.

[3]余有明，劉玉樹，閻光偉.遺傳算法的編碼理論與應(yīng)用[J].計算機工程與應(yīng)用，2006（03）：86-89.