許金坡 林天祥 鄭毅偉 劉立豐 廈門大學(xué)嘉庚學(xué)院 福建 漳州 363105

1 問題重述

問題：RGV 是一種無(wú)人駕駛、能在固定軌道上自由運(yùn)行的智能車。它根據(jù)指令能自動(dòng)控制移動(dòng)方向和距離，并自帶一個(gè)機(jī)械手臂、兩只機(jī)械手爪和物料清洗槽，能夠完成上下料及清洗物料等作業(yè)任務(wù)。針對(duì)下面兩種具體情況，分別完成 RGV 動(dòng)態(tài)調(diào)度模型和相應(yīng)的模型求解、驗(yàn)證的任務(wù)：

1.1 物料只需一道工序加工作業(yè)的情況：物料可以在任一臺(tái)CNC 上加工完成；

1.2 物料需兩道工序的加工作業(yè)的情況：每個(gè)物料的第一和第二道工序分別由兩臺(tái)不同的 CNC 依次加工完成。

2 問題分析

針對(duì)情況一，想要生產(chǎn)更多的熟料，問題等同于求解如何使生料最快變成熟料，而RGV想要把生料變成熟料需要經(jīng)歷的時(shí)間有：RGV的移動(dòng)時(shí)間、RGV的上下料時(shí)間、清洗時(shí)間。以遞歸貪婪算法為核心，首先建立RGV運(yùn)動(dòng)模型以及RGV決策模型，確定RGV的運(yùn)動(dòng)以及狀態(tài)；再利用遞歸貪婪算法模型求解得到RGV局部最優(yōu)路徑。

針對(duì)情況二，首先確定加工第一道工序和加工第二道工序的CNC的臺(tái)數(shù)，把問題抽象為排隊(duì)論模型，將加工第一道工序和加工第二道工序的CNC臺(tái)數(shù)合理分配給各組數(shù)據(jù)；其次在遞歸貪婪算法的基礎(chǔ)上建立RGV動(dòng)態(tài)模型。通過窮舉法進(jìn)行模型檢驗(yàn)。

3 模型建立與求解

3.1 問題一：RGV 決策模型——遞歸貪婪算法

機(jī)器其實(shí)和人一樣也是要運(yùn)動(dòng)、思考（決策）、感知，機(jī)器通過信號(hào)接收器感知外部環(huán)境，機(jī)器的決策機(jī)構(gòu)（諸如：嵌入式電腦）判定決定下一步做什么，然后發(fā)送指令命令諸如：電機(jī)等執(zhí)行電器執(zhí)行命令使機(jī)器運(yùn)動(dòng)起來(lái)。也就是說(shuō)，建立 RGV 的調(diào)度模型，就是討論 RGV 的運(yùn)動(dòng)、決策問題，建立數(shù)學(xué)模型來(lái)描述、仿真 RGV 的運(yùn)動(dòng)與決策。

物料只需一道工序加工且物料可以在任一臺(tái) CNC 上加工完成，我們可以以貪心算法為思想，追求 RGV 每一步的作業(yè)在當(dāng)時(shí)都是最優(yōu)解，也就是說(shuō)總是做出局部最優(yōu)，并很可能找到最優(yōu)解。確定待解決問題的最優(yōu)子結(jié)構(gòu)，我們提出了生料最快變成熟料，RGV 想要把生料變成熟料從 CNC 發(fā)出信號(hào)算起需要經(jīng)歷這些時(shí)間：等待 RGV 移動(dòng)的時(shí)間、RGV 的上下料時(shí)間。

算法仿真步驟：

Step1：初始化參數(shù)，設(shè)定 RGV 的位置，CNC 的發(fā)出信號(hào)時(shí)間；

Step2：CNC 發(fā)出信號(hào)：CNC 下一次發(fā)出信號(hào)時(shí)間小于當(dāng)前時(shí)間，若小于 CNC 向RGV 向發(fā)送信號(hào)；

Step3：判斷決策：若無(wú) CNC 發(fā)出信號(hào)則原地等待，若有一個(gè)或多個(gè) CNC 向 RGV發(fā)送信號(hào)，計(jì)算 RGV 到每個(gè)發(fā)出信號(hào)CNC 的權(quán)重；

張世貴認(rèn)為，在推動(dòng)實(shí)施鄉(xiāng)村振興戰(zhàn)略的過程中，可以在立足我國(guó)鄉(xiāng)村發(fā)展實(shí)踐、綜合分析我國(guó)鄉(xiāng)村振興戰(zhàn)略的宏觀環(huán)境與微觀環(huán)境的基礎(chǔ)上，借鑒他山之石，通過學(xué)習(xí)發(fā)達(dá)國(guó)家解決“三農(nóng)”問題的經(jīng)驗(yàn)，拓寬我國(guó)的鄉(xiāng)村振興之路。

Step4：執(zhí)行命令：RGV 向權(quán)重最低的 CNC 的移動(dòng)后，連續(xù)執(zhí)行移動(dòng)、上下料、清洗（如 CNC 非空）作業(yè)；

Step5：記錄新加料的 CNC 下次發(fā)出信號(hào)的時(shí)間；

Step6：更新時(shí)間：總時(shí)間 T 為上一次更新時(shí)間加上權(quán)重，判斷 T 是否大于 8 小時(shí)，若大于則完成作業(yè)，否則會(huì)到 step2。

根據(jù)上述算法利用 MatLab 仿真，求得在三組不同參數(shù)下得到該系統(tǒng)的完成情況如圖1。

3.2 情況二：工序位置的最佳排列——元胞自動(dòng)機(jī)模型

從總體結(jié)果來(lái)看，有有可能出現(xiàn)第一道工序完成了，但由于排隊(duì)完成第二道工序，所以最理想的情況是完成第一道工序就立馬可以完成第二道工序，以此思路建立，從而確定兩類刀具的數(shù)量。在確定數(shù)量后，就要考刀具位置分布，不同的分布的會(huì)影響到上下料、RGV移動(dòng)時(shí)間，進(jìn)而影響到加工效率，由此建立模型，最后求出每臺(tái)CNC刀具類型。

元胞自動(dòng)機(jī)本質(zhì)上是一種理想的離散動(dòng)力學(xué)系統(tǒng)模型，其元胞在空間和時(shí)間上是離散有限的，元胞的狀態(tài)也是有限的。元胞是元胞自動(dòng)機(jī)的基本單元。它具有記憶狀態(tài)的功能，其狀態(tài)由自身狀態(tài)和鄰近元胞的狀態(tài)決定。如果某元胞自動(dòng)機(jī)是有邊界的，則需要考慮元胞缺少規(guī)則所需要的鄰居的情況。元胞自動(dòng)機(jī)在空間上劃分為一維，二維，三維元胞自動(dòng)機(jī)，概率上分為概率機(jī)、非概率機(jī)。

圖1 熟料數(shù)量和時(shí)間的關(guān)系圖

將 RGV 看成元胞，本文構(gòu)建的元胞自動(dòng)機(jī)模型行為和規(guī)則如下：

（1）當(dāng) CNC 發(fā)出信號(hào)時(shí)才考慮是否前進(jìn)，否則不前進(jìn)；

（2）當(dāng) VGR 本身沒有經(jīng)過第一道工序的生料時(shí)，只考慮往發(fā)出信號(hào)的加工第一道工序的 CNC 行進(jìn)，當(dāng) VGR 本身有經(jīng)過第一道工序的生料時(shí)，只考慮往發(fā)出信號(hào)的加工第二道工序的CNC 行進(jìn)，否則原地等待。

（3）統(tǒng)計(jì)元胞從所有加工第一道工序的 CNC 走到所有加工第二道工序的 CNC 的總時(shí)間；

（4）元胞的重置規(guī)則：當(dāng)統(tǒng)計(jì)完時(shí)間后，重新對(duì) CNC 的刀具進(jìn)行新的排列，元胞回到初始位置，然后進(jìn)行新一輪的統(tǒng)計(jì)時(shí)間；

（5）結(jié)束條件：當(dāng) CNC 的刀具無(wú)法再有新的排列時(shí)結(jié)束；

（6）結(jié)果：根據(jù)在刀具數(shù)量固定的時(shí)候，找出所有加工第一道工序的 CNC 走到所有加工第二道工序的 CNC 的總時(shí)間最少的時(shí)候 CNC 的刀具排布情況。

表1 刀具分布情況表