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

1 問題重述

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

1.1 物料只需一道工序加工作業的情況：物料可以在任一臺CNC 上加工完成；

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

2 問題分析

針對情況一，想要生產更多的熟料，問題等同于求解如何使生料最快變成熟料，而RGV想要把生料變成熟料需要經歷的時間有：RGV的移動時間、RGV的上下料時間、清洗時間。以遞歸貪婪算法為核心，首先建立RGV運動模型以及RGV決策模型，確定RGV的運動以及狀態；再利用遞歸貪婪算法模型求解得到RGV局部最優路徑。

針對情況二，首先確定加工第一道工序和加工第二道工序的CNC的臺數，把問題抽象為排隊論模型，將加工第一道工序和加工第二道工序的CNC臺數合理分配給各組數據；其次在遞歸貪婪算法的基礎上建立RGV動態模型。通過窮舉法進行模型檢驗。

3 模型建立與求解

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

機器其實和人一樣也是要運動、思考（決策）、感知，機器通過信號接收器感知外部環境，機器的決策機構（諸如：嵌入式電腦）判定決定下一步做什么，然后發送指令命令諸如：電機等執行電器執行命令使機器運動起來。也就是說，建立 RGV 的調度模型，就是討論 RGV 的運動、決策問題，建立數學模型來描述、仿真 RGV 的運動與決策。

物料只需一道工序加工且物料可以在任一臺 CNC 上加工完成，我們可以以貪心算法為思想，追求 RGV 每一步的作業在當時都是最優解，也就是說總是做出局部最優，并很可能找到最優解。確定待解決問題的最優子結構，我們提出了生料最快變成熟料，RGV 想要把生料變成熟料從 CNC 發出信號算起需要經歷這些時間：等待 RGV 移動的時間、RGV 的上下料時間。

算法仿真步驟：

Step1：初始化參數，設定 RGV 的位置，CNC 的發出信號時間；

Step2：CNC 發出信號：CNC 下一次發出信號時間小于當前時間，若小于 CNC 向RGV 向發送信號；

Step3：判斷決策：若無 CNC 發出信號則原地等待，若有一個或多個 CNC 向 RGV發送信號，計算 RGV 到每個發出信號CNC 的權重；

張世貴認為，在推動實施鄉村振興戰略的過程中，可以在立足我國鄉村發展實踐、綜合分析我國鄉村振興戰略的宏觀環境與微觀環境的基礎上，借鑒他山之石，通過學習發達國家解決“三農”問題的經驗，拓寬我國的鄉村振興之路。

Step4：執行命令：RGV 向權重最低的 CNC 的移動后，連續執行移動、上下料、清洗（如 CNC 非空）作業；

Step5：記錄新加料的 CNC 下次發出信號的時間；

Step6：更新時間：總時間 T 為上一次更新時間加上權重，判斷 T 是否大于 8 小時，若大于則完成作業，否則會到 step2。

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

3.2 情況二：工序位置的最佳排列——元胞自動機模型

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

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

圖1 熟料數量和時間的關系圖

將 RGV 看成元胞，本文構建的元胞自動機模型行為和規則如下：

（1）當 CNC 發出信號時才考慮是否前進，否則不前進；

（2）當 VGR 本身沒有經過第一道工序的生料時，只考慮往發出信號的加工第一道工序的 CNC 行進，當 VGR 本身有經過第一道工序的生料時，只考慮往發出信號的加工第二道工序的CNC 行進，否則原地等待。

（3）統計元胞從所有加工第一道工序的 CNC 走到所有加工第二道工序的 CNC 的總時間；

（4）元胞的重置規則：當統計完時間后，重新對 CNC 的刀具進行新的排列，元胞回到初始位置，然后進行新一輪的統計時間；

（5）結束條件：當 CNC 的刀具無法再有新的排列時結束；

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

表1 刀具分布情況表