智能RGV 動態(tài)調(diào)度問題的研究

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

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

0 引言

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

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

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

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

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

1 構(gòu)建一道工序的物料加工作業(yè)的RGV 動態(tài)調(diào)度模型

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

1.1 平均等候時間

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

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

1.2 用動態(tài)規(guī)劃算法求解RGV 所走路徑

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

建立其模型為：

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

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

（3）建立狀態(tài)轉(zhuǎn)移方程：Tk=Tk-1+ tk· xk

（4）建立遞歸方程：

最后根據(jù)確定的優(yōu)化目標，確定多目標距離函數(shù)公式為：

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

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

1.3 基于排隊論的仿真模擬

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

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

根據(jù)智能加工系統(tǒng)所給信息對相應的參數(shù)進行賦值：

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

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

最多等待服務CNC 臺數(shù)N=8 臺

仿真時間Total_time=480 分鐘

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

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

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

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

2 構(gòu)建兩道工序的物料加工作業(yè)的RGV 動態(tài)調(diào)度模型

2.1 CNC 最短流程時間組合

把Johnson算法用于一般的n/m/P/maxF（最長流程時間），目標函數(shù)是使最長流程時間最短[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 臺機器系統(tǒng)的每兩臺機器組成一組，產(chǎn)生4個兩臺機器問題的集合，然后利用Johnson 的兩臺機器算法改良成四臺機器的算法得到4 個加工順序，最后選擇其中最好的一個作為近似最優(yōu)解。再將8 臺機器兩兩進行組合排列共有4!種可能，將這24種可能全部按Johnson 算法進行最大流程時間的求解，我們?nèi)∵@24 組解中，用時最短的一組排列組合。

2.2 RGV 動態(tài)調(diào)度優(yōu)化設計

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

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

（1）完工時間約束：

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

（2）動態(tài)擾動約束：

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

設備平衡約束：

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

（3）加工時間約束：

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

3 CNC 發(fā)生故障時，別基于一道與兩道工序建立RGV 動態(tài)調(diào)度模型

3.1 序故障情況建立RGV 動態(tài)調(diào)度模型

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

m：CNC總數(shù)；

n：待加工物料總數(shù)；

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的連續(xù)可用時間，即CNCj從開始(或修復后重新)運轉(zhuǎn)到下次發(fā)生故障期間的運轉(zhuǎn)時間，隨機變量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 調(diào)度問題就是確定 n 個物料的加工順序使得ECmax最小，其最優(yōu)結(jié)果記作ECm*a，即：

2.ECmax的求解算法

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

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

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

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

其中，如果

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

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

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

3.2 針對兩道工序故障情況建立RGV 動態(tài)調(diào)度模型

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

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

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

4 結(jié)論

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

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