動態循環分類法解決RGV調度問題

青島工程職業學院 邱勇進

對于一道工序的物料加工情況，我們首先根據RGV在各個CNC之間的移動時間，建立各CNC之間移動時間的圖。對于兩道工序的物料加工情況，針對工序一和工序二的配置比例及位置安排問題，我們仿照問題一提出了位置配比的原則，再針對不同的配置原則進行驗證，從中選出8種位置安排。對于有潛在故障的一道工序的物料加工情況，考慮到每個故障情況是相互獨立的，我們將所有錯誤依據是否影響循環周期分成兩種。對于有潛在故障的兩道工序的物料加工情況，選擇使用類似問題二的方法計算出物件總量。在討論故障時候，類似問題三，我們同樣分類對是否影響周期分開進行討論。

1 問題的提出

1.1 背景介紹

RGV，是有軌制導車輛（Rail Guided Vehicle）的英文縮寫 ，又叫有軌穿梭小車， RGV小車可用于各類高密度儲存方式的倉庫，小車通道可設計任意長，可提高整個倉庫儲存量，并且在操作時無需叉車駛入巷道，使其安全性會更高。在利用叉車無需進入巷道的優勢，配合小車在巷道中的快速運行，有效提高倉庫的運行效率。

一個智能加工系統的示意圖1，由8臺計算機數控機床（Computer Number Controller，CNC）、1輛軌道式自動引導車（Rail Guide Vehicle，RGV）、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶等附屬設備組成。RGV是一種無人駕駛、能在固定軌道上自由運行的智能車。它根據指令能自動控制移動方向和距離，并自帶一個機械手臂、兩只機械手爪和物料清洗槽，能夠完成上下料及清洗物料等作業任務。

圖1 智能加工系統示意圖

1.2 問題重述

一個由8臺數控機床和1個軌道式自動引導車的智能系統加工系統，針對如下幾種情況：（1）每個物件在每臺CNC上加工一次；（2）每個物件在不同兩件CNC上先后加工兩次；（3）CNC在加工過程中出現故障，故障時間介于10～20min。請建立相應的RGV動態調度模型和相應的求解算法，并利用表中系統作業參數的三組數據檢驗模型的實用性和算法的有效性。給出RGV的調度策略和系統的作業效率，并將具體的結果填入附件的表格中。

2 問題分析

2.1 情況一的分析

問題整體分為兩個階段：第一個階段為第一次上料，此時RGV可使用功能有且只有為CNC上料和移動。第二個階段為第二次及以后，RGV利用旋轉將上下料同時進行。在上下料過程完成后，RGV會對物件進行清洗并將其放在傳送帶上。這樣，一個物料的加工完成。在第一階段，我們有如下問題：（1）是否有必要在第一階段為所有CNC上料；（2）是否會出現循環工作情況；（3）是否有必要在循環階段讓所有CNC保持工作。

2.2 情況二的分析

問題二要求我們針對需要兩道工序加工的物料，配置CNC和RGV軌跡，保證8h內產出盡可能多的物件。我們將其分為兩大部分：（1）確定第一道工序和第二道工序的CNC配比；（2）確定RGV最佳移動軌跡。

2.3 情況一的故障問題分析

故障的CNC分布符合b（0.01，m），m為該CNC的啟動次數。則每一個CNC工作的概率為0.01。因為每一次CNC工作都可能出現故障，故應把單個CNC獨立出來進行討論。而有的CNC錯誤出現不會改變RGV運行軌跡，只是單純地浪費時間少產出了1個物件，這里需要著重討論的是會改變RGV運動軌跡的錯誤。

2.4 情況二的故障問題分析

類比問題二和問題三來解決問題四。只不過相比于問題三，問題四中的情況更為復雜，需要就不同工序發成錯誤再進行一次討論。

3 模型的建立與求解

3.1 模型建立

總體示意圖如圖2所示。

圖2 流程示意圖

局部循環示意圖如圖3所示。

圖3 循環示意圖

3.2 初步模型架構

初步模型參考貪心算法，考慮局部最優解和生產過程中生成的循環情況，我們在響應完成工序2加工的CNC時需要考慮以下三原則：（1）需要同時存在完成工序1的CNC，否則等待至完成工序1的CNC出現；（2）優先選擇距離最近的完成工序1的CNC；（3）若存在同樣近的完成工序1的CNC，優先使用編號為奇數的CNC。

通過此種原則，我們的每一步操作均為該操作的最優解。以此為依據我們提出了一種遞推模式的貪心算法。

我們采用時間軸的思想，采用時間為單位推進，判斷各個工作臺和RGV的狀態，RGV的動作會造成時間軸的變動，進而產生各種需要判斷處理的事件。通過提出的三原則，我們即可得到最優解，累加生成的成品物料個數。當時間軸推動到八個小時時，終止程序，我們就得到了最終產生的成品物料個數。

3.3 模型重建結果

通過使用上面模型編程計算，我們通過代入第一組數據發現程序輸出的數值并不合理，這是由于時間軸推動會造成時間的冗余，我們處理數據的即時化效果并不好。因此我們轉而尋找另外的編程思路。如圖4所示。

圖4 問題二最終流程圖

4 模型評價

4.1 模型的優點

假設的合理性：在查閱相關物理、數學模型文獻的基礎上做出了一系列科學的假設，抓大放小，有的放矢，忽略了對結果影響較小的因素，從而大大簡化了模型和算法，同時取得了很好的建模效果。

建模的科學性：模型建立的理論知識基于動態規劃、最小路程、遺傳算法等多門交叉學科，就建模的科學論證、知識儲備上，本模型以小窺大、由淺到深的對相關知識進行聯結整理。

建模的可推廣性：本模型基于1個RGV在8個CNC的移動問題，顯然可以拓展到n個CNC工作的問題。

4.2 模型的缺點

誤差的必然存在性：考慮到存在實際產品安裝匹配、操作使用以及模型的轉換取舍中，必然存在誤差，模型就誤差的減少上提出循環優化。但就誤差取舍的選擇問題上，還仍有參數改進的空間。

算法的適用性：本文模型中適用于RGV數量為1的工作問題，當RGV數量增加后，需要考慮碰撞問題。

算法的準確性：在問題四中，我們因計算過于龐大，選擇忽略了第一道工序中周期改變的情況，這樣在極端情況下（等待時間遠遠大于加工時間）可能出現誤差。