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

王晨旭 漆映彤 盛瑋桐

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

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

引言

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

1. 模型準(zhǔn)備

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

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

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

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

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

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

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

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

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

Step3：選擇、交叉、變異。

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

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

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

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

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

最后，進(jìn)行變異操作。常用的變異操作有二進(jìn)制變異法、實(shí)值變異法。

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

結(jié)論：

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

參考文獻(xiàn)：

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

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

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