智能RGV 動態調度問題的研究

蔣佳烜，朱天奇，李俊良，吳宇航

(1. 華北理工大學數學建模創新實驗室，河北 唐山 063210；2. 華北理工大學理學院，河北 唐山 063210；3. 華北理工大學 機械學院，河北 唐山 063210；4. 華北理工大學機械工程學院，河北 唐山市 063210；5. 華北理工大學，河北 唐山 063210)

0 引言

在傳統的自動生產線中，搬運裝置一般采用PLC 定時或檢測每個工位光電開關的狀態等簡單的順序步進控制調度策略。這種“靜態”調度的搬運設備需要在線等待在加工工件，并且不能及時適應不確定因素的影響，往往會造成物料傳輸鏈的阻塞，形成生產線物流瓶頸，制約生產線設備的利用率和生產率。因此急需設計一種智能加工系統，能夠在接到任務后作出最優處理方案，以此來提高生產線的工作效率[1]。

RGV 是一種無人駕駛、能在固定軌道上自由運行的智能車。它根據指令能自動控制移動方向和距離，并自帶一個機械手臂、兩只機械手爪和物料清洗槽，能夠完成上下料及清洗物料等作業任務，但不能智能選擇最優化方案，為了更好地解決以上問題，本文提出了以下三種情況，針對這三種情況建立模型來提高生產效率。

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

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

（3）CNC 在加工過程中可能發生故障（據統計：故障的發生概率約為1%）的情況，每次故障排除（人工處理，未完成的物料報廢）時間介于10～20 分鐘之間，故障排除后即刻加入作業序列。要求分別考慮一道工序和兩道工序的物料加工作業情況。

1 構建一道工序的物料加工作業的RGV 動態調度模型

首先用線性加權的方式將CNC 平均等候時間和RGV 所走路徑作為優化目標組合成一個新的評價函數，即多目標距離函數，并由此評價函數來衡量RGV 智能車的操作性能，最終選擇在滿足約束條件前提下的具有最小距離函數值得RGV 的路徑。

1.1 平均等候時間

等候時間，就是指從CNC 完成作業后發出需求信號到RGV 到達此發出需求信號的CNC 所經過的時間。而平均等候時間就是所有CNC 需要等候時間的平均值，這也是RGV 在調度策略中的重要指標[2]。等候時間包括CNC 發出需求信號后，RGV 處理其他CNC 的時間和RGV 從上一個CNC 到發出需求信號的CNC 過程中所需要的時間。可用如下表達式計算：

其中T 代表CNC 等待RGV 服務時間，TMT表示RGV 運行到發出需求信號的CNC 所需要的時間。TAT表示RGV 處理其他CNC 的時間。 T1表示RGV 移動一個單位所需要的時間， T2表示RGV 移動兩個單位所需要的時間， T3表示移動三個單位所需要的時間。 T4表示上下料所需時間， T5表示清洗所需要的時間。

1.2 用動態規劃算法求解RGV 所走路徑

設RGV 對CNC 進行一班次連續作業為T 個小時。現有n（n=8）個CNC 可供RGV 進行連續作業處理，這n 種物品的編號分別為1,2, … ,n。每個CNC 需要被處理的時間為t1,t2···,tn，每次RGV 對CNC處理所移動的單位長度為 s1, s2, ···,sn。每個CNC 被處理的次數為 xj（xj≥ 0且為整數， j∈ {1,2,…, n}）。求解如何選擇對CNC 進行處理，使RGV 移動的總距離S 達到最大。（其中T , t1, t2,… , tn和 s1, s2,…, sn均為整數）。

建立其模型為：

（1）劃分階段K：將8 個CNC 按1,2, … ,n排序，每個階段RGV 對一臺CNC 進行加工處理。

（2）確定決策變量： xk，對第k 個階段CNC 進行處理的總次數； Tk，對第k 個階段對CNC 進行作業操作耗費的總時間。

（3）建立狀態轉移方程：Tk=Tk-1+ tk· xk

（4）建立遞歸方程：

最后根據確定的優化目標，確定多目標距離函數公式為：

其中， wi即評價函數的參數，0≤ wi≤ 1且 w1+w2= 1； fw( i )為RGV 到達第i 個CNC 時CNC 需要等候的時間， fc( i )表示RGV 到達第i 個CNC 時所需要經過的路程。 fw*表示期望等候時間； fc*表示期望移動距離。

由于這兩個指標的量綱不同，為了量綱統一化，需要對對應的目標函數進行統一量綱處理，即在目標函數中引入期望等候時間、期望移動距離 fc*[3]。

1.3 基于排隊論的仿真模擬

M/M/1/N/∝排隊模型表示CNC 向RGV 發出的需求指令為無限，各個CNC 發送指令相互獨立，指令發送規律服從泊松分布，CNC 發送指令平均速率為λ；單服務臺，隊長限制為N（即系統中最多允許有N 個CNC 在排隊），先到先服務，RGV 在為各CNC 服務的時間相互獨立，且服從負指數分布，RGV 上下料的平均速率為μ。

圖1 智能RGV 的工作流程 Fig.1 Intelligent RGV workflow

根據智能加工系統所給信息對相應的參數進行賦值：

CNC 發送指令的平均速率λ=0.1 個/分鐘

RGV 上下料的平均速率μ=1 臺/分鐘

最多等待服務CNC 臺數N=8 臺

仿真時間Total_time=480 分鐘

根據CNC 發送指令平均速率λ 和RGV 上下料的平均速率為μ 來確定每個CNC 從發送指令到接受上下料服務的時間間隔和上下料時間間隔。上下料間隔時間可以用負指數分布函數exprnd 來生成[4]。由于泊松過程的時間間隔也服從負指數分布，故亦可由此函數生成實現CNC 指令到達的時間間隔。根據該算法對RGV 動態調度進行仿真，得到以下兩個仿真曲線。

圖2 CNC 發送指令時間與RGV 提供服務時間的曲線圖 Fig.2 Curve diagram of CNC sending instruction time and RGV providing service time

圖3 CNC 等待上料時間與發出指令到接受服務時間的曲線圖 Fig.3 Curve diagram of CNC waiting for feeding time and sending instructions to receiving service time

通過仿真曲線可以看出建立的RGV 動態調度模型可以很好地指導RGV 完成上下料和清洗工作，在該模型的調度中，CNC 發送指令時間與RGV 提供服務時間高度吻合，說明CNC 從發出需求指令到接受RGV 服務不需要經歷很長的等待時間，在該調度模型中RGV 可以在接收指令后及時的提供服務，實現了對時間的準確把握，提高了工作效率。

2 構建兩道工序的物料加工作業的RGV 動態調度模型

2.1 CNC 最短流程時間組合

把Johnson算法用于一般的n/m/P/maxF（最長流程時間），目標函數是使最長流程時間最短[5]。maxF等于一批物料最長完工時間Cmax。設n個物料的加工順序為S={s1,s2,…,sn}，其中si為排在第i位加工的物料的代號。以csik表示物料si在機器Mk上的完工時間，tsik表示物料si在Mk上的加工時間，i=1,2,…,n；k=1,2,…,m，則csik按以下公式計算：

當ri=0, i=1,2, ···, n 時，最大流程時間為

當由（3）式得出csnm時， Fmax就求得了。

對于兩道工序的物料加工所需時間為T ，公式為T = t1+ t2，其中 ti為第i 道工序所需加工時間（ i=1,2）。對于兩道工序的問題，其中m=4，首先，把8 臺機器系統的每兩臺機器組成一組，產生4個兩臺機器問題的集合，然后利用Johnson 的兩臺機器算法改良成四臺機器的算法得到4 個加工順序，最后選擇其中最好的一個作為近似最優解。再將8 臺機器兩兩進行組合排列共有4!種可能，將這24種可能全部按Johnson 算法進行最大流程時間的求解，我們取這24 組解中，用時最短的一組排列組合。

2.2 RGV 動態調度優化設計

確定每一道工序在某一具體時間開始設備上加工，保證RGV 所移動距離最小并盡可能對更多的物料進行加工，所以，我們建立如下的目標函數：

式中，Ei為任務提前懲罰； Di為任務拖期懲罰。約束條件如下所述：

（1）完工時間約束：

式中， tEijmk為任務i ( i=1,2, ···) 的工序 j ( j=1,2)在設備組 m(m=1,2,3,4)內設備k 的結束加工時間。

（2）動態擾動約束：

式中 t′ij為調度方案中任務i 的第j 道工序的開工時間； tij為預調度方案中i的第j道工序的開工時間。

設備平衡約束：

式中， TPvjmk為物料v 的工序j 在設備組m 內設備k 的加工時間； Tavg為所有設備的平均加工時間；Xijmk為0-1 變量，1 表示任務i 在設備組m 中設備k 上先于任務j 加工。

（3）加工時間約束：

式中，Sijmkt 為任務i 的工序j 在設備組m 內設備k 的開始加工時間。SvjmkT為表示物料v 的工序j 在設備組m 內設備k 的加工準備時間。

3 CNC 發生故障時，別基于一道與兩道工序建立RGV 動態調度模型

3.1 序故障情況建立RGV 動態調度模型

1.建立最小加工時間公式

m：CNC總數；

n：待加工物料總數；

si：排在第i個位置的物料，i=1,2,···,n；

S：物料排列集合，S=｛s1,s2,···,sn｝；

p(i,j)：物料i在第j臺CNC上的加工時間，相互獨立的隨機變量，i=1,2,···,n；j=1,2,···,8；

Bj：CNCj的連續可用時間，即CNCj從開始(或修復后重新)運轉到下次發生故障期間的運轉時間，隨機變量j=1,2,···,8；

Rj：CNCj的故障修復時間，隨機變量j=1,2,···8；

t(i,j)：物料i在CNCj上的開始加工時刻；

c(i,j)：物料i在CNCj上的完工時刻；

C(i)：物料i在最后一臺CNC上的加工完成時刻；

Cmax：所有物料加工的最大完成時刻；

EX：隨機變量X的期望值，例如，Ep(i,j)表示加工時間的期望值。

當僅考慮加工時間隨機時，對應于排列S的各個物料在每臺CNC上的完成時間描述如下：

目標是最小化最大完工時間，即

以最小化最大完工時間(ECmax)為目標的 SF-SSP 調度問題就是確定 n 個物料的加工順序使得ECmax最小，其最優結果記作ECm*a，即：

2.ECmax的求解算法

為合理地計算故障發生的期望時刻和相應的目標值 E Cmax，設計了兩類計算規則，用以計算不同CNC 工作方式下的故障發生時刻，并計算物料i (i=1,2, ···,n)在CNC j ( j=1,2, ···, 8)上的完工時間期望值[6]。假設一個物料正在CNC 上加工時CNC 出現故障，修好后，被故障中斷的物料的工序在原來已加工的基礎上繼續加工，其計算規則如下：

假定在初始時刻，所有CNC 可用，且物料可以加工，有：

（1）情況1：CNC 從加工第一個物料開始運轉，一直運轉到故障發生或所有物料結束，任意時刻都可能發生故障。CNCj 的故障時刻期望值為CNCj 的開始工作時刻期望值Et ( s1, j )（或上次故障修復的時刻）與CNC 連續可用時間期望值EBj之和物料在上的完工時間期望值計算如下：

“×”表示故障，“EA”表示故障的期望發生時刻，如圖所示，若故障發生在EA 時刻：

其中，如果

說明故障可以在CNC 正常閑置時間修好，因此這種故障不會影響生產。若故障發生在EB 時刻，則有

說明這種故障導致物料i 的第j 道工序的完成時間后延jR 。

（2）情況2：CNC 從加工第一個物料開始運轉，一直運轉到故障發生或所有物料結束，且CNC只有在加工過程中才可能發生故障。當 CNCj 的故障時間期望值存在于非加工時間區間上時，令故障時刻期望值等于，由此保證CNC 在非加工時間內不會出現故障，即不存在圖1 中EA 類故障時刻；當不屬于區間時，CNC 的故障時刻期望值計算規則同情況 1。物料在上的完工時間期望值計算方法如下：

3.2 針對兩道工序故障情況建立RGV 動態調度模型

兩道工序在一道工序的基礎上，增加了CNC 對物料進行不同的加工處理。在問題二已經解出了最優組合。

一道工序與兩道工序的共同點：當CNC 發生故障后，不論是當時物料在進行第一道工序還是第二道工序，發生故障后，物料都被報廢，都需要從第一道工序進行。因此CNC 出現故障對物料加工的順序與應用CNC 的順序發生改變，最終導致物料加工完成的數量減少。

一道工序與兩道工序的不同點：兩道工序加工時間長，且有最優組合方案，完成一個物料加工相比一道工序的CNC 少。所以，我們只要分別基于問題一二對一道工序與兩道工序的物料加工問題，考慮CNC 故障，并依據表一所給的數據，我們就能得出再進行作業操作時，CNC 出現故障，物料進行加工開始的時間與完工的時刻，從而得出我們需要的結果。

4 結論

進行基于排隊論的仿真模擬，仿真結果表明在該調度模型中CNC 從發出需求指令到接受RGV 服務不需要經歷很長的等待時間，RGV 可以在接收指令后及時的提供服務，實現了對時間的準確把握，提高了工作效率。

CNC 出現故障對物料加工的順序與應用CNC 的順序發生改變，最終導致物料加工完成的數量減少。考慮加工時間隨機性和對應于排列各個物料在每臺CNC 上的完成時間，計算故障發生的期望時刻和相應的目標值，結合前兩問的算法建立考慮CNC 可能故障的情況下的RGV 動態調度模型。進而針對RGV 所有情況的調度模型都建立完成。