杜一婷，馮夢若，李佳軍，方 睿

（汕頭大學(xué)數(shù)學(xué)系，廣東 汕頭 515063）

0 引 言

智能軌道式自動引導(dǎo)車（Rail Guide Vehicle，RGV）是現(xiàn)代自動化生產(chǎn)車間中的重要工具，其可連接不同數(shù)量，不同種類的計算機數(shù)控機床（Computer Number Controller，CNC）.隨著我國自動化行業(yè)的發(fā)展，智能RGV 逐漸應(yīng)用到大物流的輸送、調(diào)度問題.同時，智能加工系統(tǒng)中存在機器故障等情況，會對RGV 動態(tài)調(diào)度提出挑戰(zhàn).為提高物流系統(tǒng)效率，需要設(shè)置合理的“智能RGV 的動態(tài)調(diào)度策略”.本文根據(jù)2018 年全國大學(xué)生數(shù)學(xué)建模競賽B 題給定的智能加工系統(tǒng)作業(yè)情況以及作業(yè)參數(shù)，嘗試解決以下兩項任務(wù)：

任務(wù)1：對一般問題進行研究，給出RGV 動態(tài)調(diào)度模型和相應(yīng)的求解算法；

任務(wù)2：利用表1 中系統(tǒng)作業(yè)參數(shù)的3 組數(shù)據(jù)分別檢驗?zāi)Ｐ偷膶嵱眯院退惴ǖ挠行?，給出RGV 的調(diào)度策略和系統(tǒng)的作業(yè)效率，并將具體的結(jié)果填入附件.

其中智能加工系統(tǒng)作業(yè)3 種具體情況為：

（1）一道工序的物料加工作業(yè)情況，每臺CNC 安裝同樣的刀具，物料可以在任一臺CNC 上加工完成；

（2）兩道工序的物料加工作業(yè)情況，每個物料的第一和第二道工序分別由兩臺不同的CNC 依次加工完成；

（3）CNC 在加工過程中可能發(fā)生故障的情況，人工處理，且故障的發(fā)生概率約為1%，每次故障排除時間介于10-20 min 之間，故障排除后即刻加入作業(yè)序列，未完成的物料報廢.分別考慮一、二兩道工序的物料加工作業(yè)情況.

注：題目、參數(shù)和附件可到全國大學(xué)生數(shù)學(xué)建模競賽官方網(wǎng)站http：//www.mcm.edu.cn 下載

1 模型的假設(shè)

為了方便研究，在不改變題目要求的前提下，我們對模型作以下假設(shè)：

（1）假設(shè)每臺RGV 每次清洗作業(yè)和上下料作業(yè)的時間相同；

（2）每臺CNC 的加工效率相同且保持穩(wěn)定；

（3）假設(shè)RGV 先將生料放到CNC，完成上料工作后，再進行熟料的清洗工作；

（4）假設(shè)上下料傳送帶的連動或獨立運動對模型無影響；

（5）假設(shè)智能加工系統(tǒng)中的所有傳感器反應(yīng)時間很短，可忽略不計.

2 任務(wù)1的模型建立與求解

2.1 任務(wù)1的分析

首先需要考慮一道工序的物料加工作業(yè)，且CNC 沒有故障的情況，設(shè)該情況為情況1.

2.1.1 情況1 分析

在此情況中，每個物料只有一道加工工序，所以每臺CNC 安裝同樣的刀具.此時，物料可以在任意一臺CNC 上加工完成，即8 個CNC 是通用并行機，可視為是性質(zhì)相同的8 個固定點.每兩個不同點之間可以通過RGV 連接，為了提高調(diào)度效率，RGV 需要尋找最短路徑，所以該問題為最短路問題.

RGV 的路徑取決于RGV 和CNC 的狀態(tài)和位置，是動態(tài)的.所以可以用RGV 動態(tài)路徑的旅行時間代表其路徑長度，利用動態(tài)規(guī)劃的思想進行路徑選擇的決策，建立基于動態(tài)路徑的調(diào)度模型，并且利用MATLAB 編寫對應(yīng)程序.

再者，我們需要考慮兩道工序的物料加工作業(yè)，此時，若仍不考慮CNC 出現(xiàn)故障的情況，設(shè)該情況對應(yīng)情況2.若考慮CNC 在加工過程中可能發(fā)生故障，設(shè)該情況對應(yīng)情況3.

2.1.2 情況2，3 分析

在情況2、3 中，每個物料需要兩道加工工序，所以不同CNC 可能安裝不同刀具.基于情況1 的分析，需要在動態(tài)規(guī)劃中加入與工序相關(guān)的約束條件，并且將其具體體現(xiàn)在算法中.此時的物料調(diào)度步驟增多，不僅需要考慮RGV、CNC 的狀態(tài)以及位置，而且需考慮安裝兩種刀片的CNC 各有多少個，以及不同類型的CNC 的排布.通過分析表1 中的數(shù)據(jù)可得，RGV 的運行時間相對CNC 加工時間很短，所以不同類型CNC 的數(shù)量對系統(tǒng)效率的影響要遠大于CNC 分布的影響.

2.2 模型建立

2.2.1 基于動態(tài)路徑的調(diào)度模型

基于情況1 的分析，RGV 的旅行路徑是動態(tài)的，為尋找最短路徑，需建立基于動態(tài)路徑的調(diào)度模式.

2.2.1.1 固定起點的最短路問題

應(yīng)用到任務(wù)問題中，RGV 在固定8 個CNC 任務(wù)點之間尋找運動的最短路徑，且此過程在8 h 班次中，不斷重復(fù)迭代更新最短路徑，具有周期性.

RGV 在智能加工系統(tǒng)開始工作后，能在直線軌道上移動或停止等待；以兩臺相鄰CNC 的距離為1 個單位，RGV 可連續(xù)移動1 個單位、2 個單位和3 個單位.RGV 給兩臺CNC 放置生料的順序類型，可分為從奇數(shù)側(cè)到偶數(shù)側(cè)、奇數(shù)側(cè)到奇數(shù)側(cè)及偶數(shù)側(cè)到偶數(shù)側(cè)，如圖1 所示.

圖1 RGV 工作路徑的類型及物料需求點CNC

一般情況下，物料輸入智能加工系統(tǒng)的狀態(tài)服從均勻分布.設(shè)系統(tǒng)停止工作時，得到成料量為n，單位為一臺CNC 加工的量，對應(yīng)加工物料的序號.在系統(tǒng)工作的過程中，RGV 的運輸要滿足8 臺CNC 的上料和下料的需求，因此，在存在服務(wù)質(zhì)量和可行性約束且消耗最少的能量的情況下，RGV 的工作量為2n.

定義 P 為 RGV 上料，D 為 RGV 下料，其中 P＝{1，2，…，n}，D＝{n＋1，n＋2，…，2n}.當(dāng)RGV 放置第i（1≤i≤n）個物料時，它與RGV 給CNC 進行第i＋n 個下料工作相關(guān)聯(lián).此時RGV 的路徑問題，由一個有向的圖G＝（V，E）描述，V 中的頂點i 表示RGV 上料或下料工作的需求點，其中e＝（i，j）表示兩個工作之間的可能處理順序，即工作j 是否可以在工作i 之后立即處理.為保證系統(tǒng)作業(yè)的開始和結(jié)束，還增加了兩個虛擬的工作任務(wù)，分別為 0 和 2n＋1，表示 RGV 的起始位置和結(jié)束位置.因此定義 V′＝P∪D＝{1，2，…，2n}，則V＝{0}∪V′∪{2n＋1}，對應(yīng)的i，j∈V，k＝1，2，…，2n＋1.

2.2.1.2 RGV 判斷過程

在假設(shè)條件的基礎(chǔ)下，RGV 動態(tài)調(diào)度需要在RGV 對某些時間狀態(tài)做出判斷后開始，判斷出到某臺CNC 進行工作的過程總時間最小，則到相應(yīng)CNC 進行作業(yè).RGV 判斷過程涉及的時間變量如表1 所示.

表1 RGV 判斷時間段

RGV 判斷后，要得到移動到哪一臺CNC 的時間最短，即最短路徑，然后再進行調(diào)度作業(yè)，不斷針對路徑進行循環(huán)判斷，直到智能加工系統(tǒng)工作時間結(jié)束.實際過程中可能存在的一種情況，如圖2 所示，即CNC4#的加工完成時間比CNC6#長，RGV 移動到CNC4#，但在去CNC4#的過程中，經(jīng)過CNC6#之前，若此時CNC6#也給RGV 發(fā)出需求訊號.

圖2 判斷的特殊情況

那么若此時依然移動到CNC4#，將會浪費時間資源，減少成料產(chǎn)出.所以RGV先決定給CNC6#作業(yè)，此外RGV 給不同編號的CNC 上下料的時間也不同，也會產(chǎn)生影響.因此，當(dāng)設(shè)定RGV 決策時，要判斷三者之和的最小值，即

2.2.1.3 分治法確定成料產(chǎn)出量及上下料作業(yè)時間點

動態(tài)規(guī)劃基本上是一種完全枚舉算法，嘗試通過分治法以使需要進行的計算量最小化.這種方法在找到最終答案之前解決了一系列的子問題，并確定每一個子問題的最優(yōu)解以及每個子問題對于最終目標(biāo)問題的貢獻.在每一次迭代過程中，其所確定的子問題最優(yōu)解均大于以往求解的子問題的解，從而為了求解當(dāng)前的子問題，需使用求解以往所有子問題獲得的信息.

根據(jù)文獻[1]的研究結(jié)果，我們將每個迭代過程的最短時間分為5 個時間段，綜合判斷后得到一個迭代過程的最短時間，再迭代n 次，得到所用時間最短，成料產(chǎn)出最大的作業(yè)方案.

（1）初始狀態(tài)：T1＝0

（2）迭代方程：minTi＝Σ（Td＋Tl＋Tz）min＋Tj＋Tq，i＝1，2，…，n.

（3）最優(yōu)值方程：ΣTi≤8×60×60.

系統(tǒng)的初始狀態(tài)：RGV 位于CNC1#、2#前，不論先為哪臺投放物料，初始時間總為0；每一次迭代過后，RGV 得到最短時間minTi，迭代n 次；由于系統(tǒng)一個班次的工作時間為8 h，而我們在建模過程中所用的時間單位為s，所以有最優(yōu)值方程.

2.2.1.4 確定RGV 為CNC 加工的方向順序

根據(jù)文獻[2]的研究結(jié)果，我們可以結(jié)合有向圖G，給出設(shè)置RGV 路徑移動方向順序的模型.最優(yōu)RGV 路徑問題的求解過程可以表述為下列公式中定義的混合整數(shù)規(guī)劃.此部分建立了一個RGV 最優(yōu)路徑問題的數(shù)學(xué)模型.

主要參數(shù)和符號被定義如下：

P 是任務(wù)集，P＝{1，2，…，n}，n≤8；

D 是任務(wù)集，D＝{n＋1，n＋2，…，2n}；

V′＝P∪D，V＝{0}∪V′∪{2n＋1}；

ti表示 RGV 到上下料需求點的旅行時間，i∈V{2n＋1}，t0＝0；

Sij表示在上下料點i，j 之間的RGV 行駛距離；

Tij是在上下料點i，j 之間的RGV 行駛時間；

xij表示上下料需求i 是否在j 之前處理0，1 變量；

bi表示第i 個任務(wù)的初始時間；

wi表示RGV 完成某臺CNC 上料或下料后的負(fù)載物料單位，i∈P，w0＝0.

約束條件：

目標(biāo)函數(shù)表示RGV 的總時間成本最小值，也是wi和xij的雙線性函數(shù)，RGV 最優(yōu)路徑（i，j）∈E 與一個耗能成本cij（wij）及一段行駛時間Tij相關(guān)聯(lián).RGV 負(fù)載的物料最多為3 個種類，即RGV 抓取的未加工的生料、從CNC 中取回的已加工的熟料和清洗后的成料.

當(dāng)RGV 判斷出在當(dāng)前位置沿路徑（i，j）移動到下一個CNC 進行作業(yè)的最優(yōu)路徑時，我們可以利用牛頓法則，求得總時間成本cij（wij），即

經(jīng)過約束條件的篩選計算，得出一次循環(huán)中耗時耗能最小的路徑.

2.3 RGV實時路徑仿真算法

對于智能RGV 動態(tài)調(diào)度問題.存在許多智能高級算法，例如遺傳算法和模擬退火算法.但是對于這些算法，RGV 運動路徑隨機性太強，且算法中參數(shù)的設(shè)計很大程度上取決于經(jīng)驗，準(zhǔn)確率常常不夠高.對此我們選擇用MATLAB 軟件編寫符合實際的模擬仿真算法，提高算法對該問題的適用程度.

假設(shè)智能加工系統(tǒng)的運行狀態(tài)穩(wěn)定且CNC 無故障，在此情況下得出物料最大產(chǎn)出以及最優(yōu)路徑.為了能讓RGV 動態(tài)調(diào)度過程更切合實際生產(chǎn)過程，對RGV 設(shè)置滯留時間懲罰系數(shù).

RGV 一共有四個位置可供選擇，{1，2，3，4}.每一個位置的操作對象只有兩個.令RGV 的位置為a，當(dāng)a＝1 時，RGV 可以操作的對象為CNC1，CNC2；

當(dāng)a＝2 時，RGV 可以操作的對象為CNC3，CNC4；

當(dāng)a＝3 時，RGV 可以操作的對象為CNC5，CNC6；

當(dāng)a＝4 時，RGV 可以操作的對象為CNC7，CNC8.

將RGV 位置以及操作對象作為變量，則一共有八種方案.可以考慮窮舉法.令操作對象為c，c 為八行一列的向量，c 中元素的值域取值為{0，1}，c 里面的元素最多有一個1.元素為1 的那一列的編號，代表的是RGV 操作對象的CNC 編號.例如c＝［0 1 0 0 0 0 0 0］，表示RGV 將要對CNC2 進行操作.綜上所述，RGV 位置以及操作對象，只有以下八種方案.

當(dāng) a＝1 時：c＝［1 0 0 0 0 0 0 0］或［0 1 0 0 0 0 0 0］

當(dāng) a＝2 時：c＝［0 0 1 0 0 0 0 0］或［0 0 0 1 0 0 0 0］

當(dāng) a＝3 時：c＝［0 0 0 0 1 0 0 0］或［0 0 0 0 0 1 0 0］

當(dāng) a＝4 時：c＝［0 0 0 0 0 0 1 0］或［0 0 0 0 0 0 0 1］

算法的主要參數(shù)和符號被定義并列在表2 中，以便于參考.算法步驟：

表2 算法中的變量與符號

Step1：RGV 判斷通過路徑所需的時間以及CNC 的工作狀態(tài).首先，RGV 根據(jù)當(dāng)前位置到下一個物料投放的每個CNC 之間的路徑距離長短和每一臺CNC 是否處于加工狀態(tài)，以確定通過路徑的最短時間.

Step2：每一次移動需要服從的調(diào)度要求：符合調(diào)度的要求：

Step3：RGV 做出調(diào)度決策后，立即移動到下一個上下料需求點.

Step4：RGV 上下料操作完成前后記錄耗費的總時間，更新CNC 的狀態(tài)、物料的裝載、更新已使用的總時間ΣminTi.

Step5：循環(huán)條件ΣTi≤8×60×60；若總時間超過8 h，則停止循環(huán)，輸出物料最大產(chǎn)出以及最優(yōu)路徑；反之，則繼續(xù)循環(huán)判斷，重復(fù)Step1-4.

2.4 基于空閑時間插入法的故障擾動模型

基于不考慮故障時的情況3，在生成預(yù)調(diào)度時，根據(jù)故障特征——以1%的幾率隨機產(chǎn)生，插入空閑時間——10 到20 min，故障間隔時間一般服從離散隨機分布，根據(jù)文獻[3]研究結(jié)果，設(shè)其為泊松分布：

則加工工件n 時發(fā)生故障的概率為

發(fā)生故障的工件n 需要插入的額外時間為

其中，

2.4.1 故障擾動下的RGV 動態(tài)調(diào)度算法

基于情況1，2 中的求解算法，該空閑時間插入的算法步驟為：

Step1：首先確定處于工作狀態(tài)的CNC，若CNC 處于工作狀態(tài)則進入Step2；

Step2：在“RGV 位置及狀態(tài)判斷”函數(shù)中考慮故障情況，從而影響可供RGV 決策集；

Step3：在迭代中對8 個CNC 設(shè)置故障擾動；

Step4：確定出現(xiàn)故障的CNC 編號；

Step5：將故障處理時間插入更新機制.

2.5 模型結(jié)果

2.5.1 一道工序的智能調(diào)度模型結(jié)果

一道工序的物料加工作業(yè)情況，每臺CNC 安裝同樣的刀具，物料可以在任一臺CNC 上加工完成.

我們建立的模型的動態(tài)調(diào)度模型基本適用于情況1，因此，基于動態(tài)路徑規(guī)劃及TSP 的動態(tài)調(diào)度模型，以及最短路徑算法，用已給數(shù)據(jù)設(shè)置對應(yīng)的參數(shù)，用MATLAB編寫程序，得到RGV 為CNC 上下料作業(yè)的編號順序，即最優(yōu)的動態(tài)路徑.運行結(jié)果顯示，對不同組數(shù)據(jù)的最優(yōu)動態(tài)路徑相同，如圖3 所示.

圖3 CNC 加工系統(tǒng)只有一道工序的最優(yōu)路徑

即最優(yōu)路徑是RGV 為CNC 進行上下料工作的編號先后順序為CNC#1、CNC#2、CNC#3、CNC#4、CNC#5、CNC#6、CNC#7、CNC#8.并且在此調(diào)度方案下每班次8 h結(jié)束時，得到最多的成料產(chǎn)出.分別給出3 組實驗中最優(yōu)路徑循環(huán)的相關(guān)數(shù)據(jù)，如表3，4，5 所示.

表3 第1 組數(shù)據(jù)：成料產(chǎn)出n＝365

表4 第2 組數(shù)據(jù)：成料產(chǎn)出n＝342

表5 第3 組數(shù)據(jù)：成料產(chǎn)出n＝375

2.5.2 兩道工序的智能調(diào)度模型的結(jié)果

針對兩道工序的物料加工作業(yè)情況，每個物料的第一和第二道工序分別由兩臺不同的CNC 依次加工完成.在情況1 的基礎(chǔ)上，RGV 增加2 種不同的狀態(tài)，即是否載有第一道工序加工完成的物料.由于物料調(diào)度復(fù)雜提高，建立優(yōu)化的RGV 動態(tài)調(diào)度算法，在該算法中，主要通過優(yōu)化RGV、CNC 的狀態(tài).

表6 不同情況的RGV 狀態(tài)對比

首先，我們要確認(rèn)安裝兩種不同刀具的CNC 數(shù)量分配比例，根據(jù)CNC 加工完成一個兩道工序的物料過程中第一和第二道工序所需的時間，進行對比.對比效率＝1/CNC加工時間，得到表7 的分配比例.

表7 每組數(shù)據(jù)的刀具分配比例

由表7 可得，我們發(fā)現(xiàn)每個配比均為非整數(shù)的，由整數(shù)規(guī)劃中的分支定界法可得，每個比例可能的整數(shù)解有兩種.我們先假設(shè)其比例效果與CNC 的位置分布無關(guān)，僅與CNC 刀具配比數(shù)量有關(guān).但經(jīng)驗證，發(fā)現(xiàn)預(yù)測是有偏差的，若忽略CNC 位置分布進行調(diào)度，那么加工完成的物料數(shù)將會減少.

設(shè)RGV 狀態(tài)為二進制變量，當(dāng)RGV 狀態(tài)為0 時，表示沒有載有第一道工序加工完成的物料，此時應(yīng)調(diào)度到裝有TP1的CNC 處；當(dāng)RGV 狀態(tài)為1 時，表示載有第一道工序加工完成的物料，此時應(yīng)調(diào)度到裝有TP2的CNC 處；基于CNC 僅加工一道工序的模型，我們將針對每一種刀具的分配比例TP1：TP2進行迭代計算，得到結(jié)果如表8所示.

表8 CNC 僅加工兩道工序的刀具配比及加工完成的物料數(shù)

2.5.3 基于空閑時間插入法的故障擾動模型的結(jié)果

經(jīng)過MATLAB 求解，得到調(diào)度策略和8 h 內(nèi)的系統(tǒng)作業(yè)效率，其結(jié)果部分如表9、10 所示.

表9 第1 組數(shù)據(jù)：一道工序有故障

表10 第1 組數(shù)據(jù)：兩道工序有故障

3 任務(wù)二：仿真檢驗

3.1 任務(wù)2的分析

任務(wù)2 要求用表1 的三組數(shù)據(jù)檢驗任務(wù)1 中模型的實用性以及算法的有效性.為了達到此目標(biāo)，我們可以構(gòu)建可視化仿真模型.我們通過Tecnomatix Plant Simulation 生產(chǎn)加工仿真軟件構(gòu)建了智能RGV 動態(tài)調(diào)度可視化仿真驗證模型.該軟件具有豐富且實用的處理功能，可以方便的選擇系統(tǒng)零件、設(shè)置參數(shù)以及搭建路徑.我們可以將仿真得到的結(jié)果與建立動態(tài)路徑調(diào)度模型的結(jié)果進行比較，以檢驗?zāi)Ｐ偷膶嵱眯院退惴ǖ挠行?基于仿真結(jié)果和模型結(jié)果，給出調(diào)度策略和系統(tǒng)的作業(yè)效率.最后把模型驗證的具體結(jié)果分別填入EXCEL 表中.

3.2 TPS可視化仿真

為了驗證模型的實用性和算法的有效性，根據(jù)文獻[4]的仿真方法，我們用Tecnomatix Plant Simulation 仿真軟件（以下簡稱“TPS”）輸入的三組數(shù)據(jù)進行模擬仿真，導(dǎo)出相關(guān)數(shù)據(jù)，與算法計算結(jié)果比較，從而達到驗證的目的，如圖4（a）所示.

選擇TPS 作為模型驗證的仿真軟件主要的原因是：TPS 具有模型所需要的所有對應(yīng)實物的對象，比如有模擬RGV 的“小車”，“裝配”模擬CNC 加工臺等，這樣就不需要自己創(chuàng)建對象，使得模擬出來的數(shù)據(jù)更加符合實際.并且TPS 生產(chǎn)加工仿真系統(tǒng)中自帶可設(shè)置CNC 故障率，這給我們的仿真驗證模型帶來了極大的便利，設(shè)置CNC 故障率為1%，即仿真模型中CNC 組件可用性為99%，如圖4（b）所示.

在原始智能加工系統(tǒng)的TPS 模擬仿真模型基礎(chǔ)上，設(shè)物料輸入服從均勻分布.并且對任務(wù)1 中的每種情況進行設(shè)置.經(jīng)過比對，仿真模型結(jié)果與我們算法得到的結(jié)果相同.這說明我們建立的模型具有實用性，我們建立的算法也是有效的.因此，我們可以根據(jù)所建立的模型作為實際調(diào)度策略的應(yīng)用，系統(tǒng)的工作效率由成料產(chǎn)出除以每班次的時間得出.

圖4

4 總結(jié)

本文通過建立了不同情況下的動態(tài)調(diào)度模型，完整解決了任務(wù)1 和任務(wù)2.我們利用圖論和規(guī)劃論的內(nèi)容，將復(fù)雜的實際問題轉(zhuǎn)化為數(shù)學(xué)模型，并利用仿真算法精準(zhǔn)地模擬了RGV 的決策過程、旅行過程和作業(yè)過程.在模型逐漸復(fù)雜化的情況下，對原有模型添加約束條件，使得其能更好地模擬實際問題.通過增加狀態(tài)變量，縮小RGV 決策集等方法優(yōu)化了算法.基于得到的算法，可以編寫對應(yīng)的程序，從而得到RGV 的調(diào)度策略和系統(tǒng)的作業(yè)效率.最終的模型和算法實用性較強，可以應(yīng)用于實際的動態(tài)調(diào)度中.