劉洪偉，胡 琪，徐 冉，王明潔

(1.北京物資學(xué)院 信息學(xué)院，北京101149；2.北京市東方德才學(xué)校，北京100038)

近年來，隨著人力資源成本持續(xù)攀升和人工智能水平高速發(fā)展，生產(chǎn)制造加工系統(tǒng)中智能加工代替人力加工越來越廣泛[1-2]。特別是在工業(yè)制造、機械加工、物料調(diào)度、倉庫物資儲存和物流產(chǎn)品的運輸與分類等眾多領(lǐng)域，存在越來越多的優(yōu)化調(diào)度和優(yōu)化控制問題[3]。一般智能加工系統(tǒng)由軌道式自動引導(dǎo)車(rail guide vehicle,RGV)、數(shù)控機床(CNC machine tools)、RGV軌道、上料傳送帶、下料傳送帶等附屬設(shè)備組成。RGV是一種在固定軌道上無人駕駛自由運行的智能車，也是智能加工系統(tǒng)的主要組成部分[4]。RGV為CNC機床加工作業(yè)進行物料調(diào)度搬運及輔助作業(yè)，其作業(yè)效率對智能加工系統(tǒng)的加工效率有直接影響。因此，對RGV系統(tǒng)合理調(diào)度能有效地提高智能加工系統(tǒng)的作業(yè)效率。

為提高車間產(chǎn)能，降低成本，企業(yè)逐步引入現(xiàn)代化的RGV物料搬運工具。國內(nèi)外學(xué)者對RGV系統(tǒng)的優(yōu)化調(diào)度和控制做了一些仿真研究。Dotoli等[5-6]采用Petri著色網(wǎng)框架研究了巷道RGV物料搬運系統(tǒng)的數(shù)學(xué)模型，建立了避免死鎖策略保護的RGV系統(tǒng)。Chen等[7]模擬仿真上下料操作的柔性生產(chǎn)制造，并闡述了智能生產(chǎn)系統(tǒng)的RGV調(diào)度和控制的具體運用。Lee等[8]給出生產(chǎn)制造加工系統(tǒng)中的RGV的5種派遣規(guī)則。吳長慶等[9]利用Petri雙重著色網(wǎng)，建立了最短路徑的RGV動態(tài)運行調(diào)度系統(tǒng)模型。楊少華等[10]對多RGV環(huán)軌協(xié)同作業(yè)進行了分析。吳焱明等[11]研究了環(huán)軌RGV系統(tǒng)的動態(tài)調(diào)度模擬問題。RGV調(diào)度與無質(zhì)量保證解的RGV派遣規(guī)則、路徑規(guī)劃不同，能夠給出每個RGV作業(yè)的細節(jié)[1]，包括上下料、清洗、移動時刻和位置。因此，在直線往復(fù)RGV系統(tǒng)中，給定了所有RGV的位置和時刻，也就確定了RGV的行進次序及路線[1]。

對于分段式、環(huán)形軌道式、直行軌道式的RGV調(diào)度問題，國內(nèi)外已經(jīng)作了一般性的研究。就現(xiàn)有的模型對RGV的調(diào)度和運輸系統(tǒng)的設(shè)計較為簡單，往往只是以RGV為單一研究對象。關(guān)于直線往復(fù)RGV調(diào)度問題的研究中，韓中庚等[3]在既定場合下給出RGV一般調(diào)度模型及產(chǎn)量估計；李國民等[12]在不確定性環(huán)境下提出了一種基于完全遍歷路徑規(guī)劃的RGV調(diào)度規(guī)則。由于RGV可沿軌道往復(fù)雙向行駛，并且可以訪問任意CNC機床，因此，RGV在執(zhí)行物料搬運任務(wù)時的行走路線有可能產(chǎn)生延遲，不能與CNC機床進行協(xié)調(diào)作業(yè)，這往往導(dǎo)致RGV系統(tǒng)成為智能加工系統(tǒng)的瓶頸。目前，針對這一問題的研究較少。在沒有給定時刻和位置的情況下，本文建立一個優(yōu)化調(diào)度模型，研究單RGV系統(tǒng)與CNC機床協(xié)調(diào)作業(yè)的調(diào)度問題，使得RGV在CNC機床加工前后等待時間最短。當(dāng)加工物料數(shù)目比較多時，該問題的求解非常耗時。根據(jù)RGV與CNC機床加工物料調(diào)度的特征，提出計算機模擬仿真算法對問題進行求解。為檢驗算法的有效性，利用不同系統(tǒng)參數(shù)對模型的可行性和有效性進行了驗證分析，并給出了最優(yōu)調(diào)度方案的實際運行結(jié)果和結(jié)論。

1問題描述及數(shù)學(xué)模型

本文研究的問題描述如下[4]，如圖1所示。該智能加工系統(tǒng)由1輛RGV、1條RGV直線軌道、K臺CNC機床、1條上料傳送帶、1條下料傳送帶等附屬設(shè)備組成。RGV根據(jù)系統(tǒng)指令能智能控制移動距離和方向，并自帶1個機械手臂、1個物料清洗槽，能夠完成上下料及清洗物料等作業(yè)任務(wù)。清洗槽每次只能清洗1個物料，機械手臂前端有2個機械手爪，可以通過機械手臂旋轉(zhuǎn)手爪先后各自抓取1個物料，完成上下料作業(yè)。CNC機床排列在直線軌道兩側(cè)，且前方安裝了一段物料傳送帶。右側(cè)為上料傳送帶，負責(zé)為CNC機床輸送未加工的物料；左側(cè)為下料傳送帶，負責(zé)將加工并清洗完成的物料送出系統(tǒng)。本文研究的單工序是指物料在CNC機床上的單次加工作業(yè)；調(diào)度問題的目標是使所有下料時刻之和最小，即使得CNC機床和RGV等待時間盡可能少。這樣可以保證在既定的時間里加工的物料盡可能多。

圖1智能加工系統(tǒng)示意圖Figure 1 Schematic diagram of intelligent processing system

1.1基本假設(shè)

為了便于問題的求解，明確問題的作業(yè)流程，本文有如下基本假設(shè)。

1)在上料傳送帶和下料傳送帶的兩側(cè)各安裝數(shù)量相同的CNC機床，等距排列，每臺CNC機床同一時刻只能加工1個物料。為了便于定位，記一側(cè)奇數(shù)編號CNC機床#1、#3、#5、 ···、另一側(cè)偶數(shù)編號CNC機床#2、#4、#6、 ···。

2)作業(yè)過程中RGV和CNC機床均不會發(fā)生故障。

3)RGV帶有智能控制功能，能夠接收和發(fā)送指令信號。

4)RGV根據(jù)指令能在直線軌道上移動、停止和等待，可連續(xù)移動k單位(即k+1臺相鄰CNC機床間的距離)。

5)RGV同一時間只能執(zhí)行移動、停止等待、上下料和清洗作業(yè)中的一項。

6)RGV勻速行駛。

1.2參數(shù)和決策變量

1.2.1參數(shù)

N為待加工的物料總個數(shù)；

K為加工物料的CNC機床個數(shù)，K為偶數(shù)；

Q為一個極大數(shù)，本文取Q=106；

Tp為物料在CNC機床上的加工時長；

Tw為加工作業(yè)后物料清洗的時長；

k、l為CNC機床位置，k,l=1,2,···,K;

i、j為物料加工順序，i,j=1,···,N；

Tk為第k個CNC機床上下料的時長，k=1,2,···,K；

Tkl為RGV從第k個CNC機床移動到第l個CNC機床所需的時長，k,l=1,2,···,K；

I j≥k為 示性參數(shù)，若j≥k，取1，否則取0。

1.2.2決策變量

x jk=1表 示物料j由第k個CNC機床加工，否則為0；

taj表 示物料j的上料開始時刻；

tdj表示物料j的下料開始時刻。

1.3數(shù)學(xué)模型

給定一組物料加工序列，在確定物料搬運目的CNC機床后，就可以確定決策變量的值。此時單智能RGV直線往復(fù)調(diào)度問題的數(shù)學(xué)模型構(gòu)建如下。

式(1)為直線往復(fù)單智能RGV調(diào)度問題的目標函數(shù)，以所有下料時刻之和最小為指標，使得CNC機床和RGV等待時間盡可能少；式(2)給出了上料順序約束；式(3)保證第j個物料一定是由某個CNC機床加工；式(4)保證第j個物料下料時刻不早于該物料加工完成時刻；式(5)保證同一個CNC機床上前后物料加工順序的時間約束：后加工的物料上料時刻必須在前面物料加工下料之后；式(6)表示相鄰2個物料開始加工時刻之間的空余時間，右邊第1項表示第j-1個物料在第j臺CNC機床上下料時刻，第2項表示RGV移動的時長(此項為二次項)，當(dāng)物料需要被清洗時，第3項表示清洗時間；式(7)是決策變量的非負約束。

由于x jk是0-1整數(shù)決策變量，且式(6)右端不等式包含二次項，此模型是一個非線性混合整數(shù)規(guī)劃模型，可以采用Gurobi等商用軟件在較短時間對較小規(guī)模模型進行精確求解。但Gurobi對規(guī)模較大的模型求解時，經(jīng)常會出現(xiàn)內(nèi)存不足、計算時間過長等現(xiàn)象，因此，有必要設(shè)計有效的新算法，使模型能夠在較短時間內(nèi)得到滿意解。

2計算機仿真建模算法設(shè)計

基于排序規(guī)則、指派規(guī)則[2]和計算機仿真模擬建模等方法是調(diào)度理論中算法設(shè)計常用且有效的技術(shù)手段。由于直線往復(fù)單智能RGV調(diào)度在規(guī)模較大時存在調(diào)度周期性，本文利用RGV調(diào)度周期性的特點進行計算機仿真模擬建模求解，既能提高模型求解速度，又能保證解的質(zhì)量。

變量和事件是計算機仿真模擬建模中最重要的元素。在模擬中一般有3種常用的變量類型：時間變量、計數(shù)變量和系統(tǒng)狀態(tài)變量[13]。只要出現(xiàn)1個事件，上述變量就要改變或更新，并且收集感興趣的數(shù)據(jù)作為輸出。

1)時間變量。當(dāng)前時刻記為t，上料開始時刻記為ta，下料開始時刻記為td；tai為第i個物料的上料時刻，tdj為第j個物料的下料時刻。

2)計數(shù)變量。t時刻為止上料個數(shù)記為i,下料個數(shù)記為j。

3)系統(tǒng)狀態(tài)變量。系統(tǒng)中t時刻正在加工的物料個數(shù)記為n，上料加1，下料減1。

由于加工初期只有上料和移動，當(dāng)?shù)?個加工作業(yè)結(jié)束后才有上下料、RGV移動和物料清洗。本文采用等待時間最長的先到先服務(wù)規(guī)則進行仿真。圖2為加工系統(tǒng)調(diào)度的計算機模擬離散事件仿真的詳細步驟。

圖2直線往復(fù)單智能RGV協(xié)調(diào)CNC機床加工作業(yè)流程圖Figure 2 Flow chart of one intelligent RGV coordinated CNC machine tools based on linear reciprocating

1)初始化數(shù)據(jù)。首先初始化時間變量(t=0,ta=0,td=∞)，計數(shù)變量(i=0，j=0)，系統(tǒng)狀態(tài)變量為(n≥K)；設(shè)置CNC機床的個數(shù)K及事件列表(tai,tdj)，并讀取其他參數(shù)。

2)上料。在加工初期加工前K個物料時還沒有形成周期，只涉及上料和RGV移動；K個物料之后才涉及上下料、RGV移動以及物料清洗。對于這一過程，通過i與n、K的比較來實現(xiàn)。i＜K表示加工初期，n＜K說明存在CNC機床空閑或等待。為ta進行賦值并令n=n+1，同時考慮為不同CNC機床上料的用時及RGV的移動用時。

3)下料。這一過程的識別主要通過n≥K來實現(xiàn)。這部分處理無特殊情況，主要注意CNC機床上下料的用時、RGV的移動以及物料清洗。下料時刻通過對CNC機床加工結(jié)束時刻與RGV空閑時刻比較得出。

4)收集數(shù)據(jù)。設(shè)置加工作業(yè)總時長為T，收集每個加工物料的上下料始末時刻、CNC機床加工始末時刻、物料清洗始末時刻、RGV的移動始末時刻及等待始末時刻。

上料及下料部分的計數(shù)變量、時間變量和系統(tǒng)狀態(tài)變量的更新計算，特別是事件列表(tai,tdj)的更新是該流程圖的核心。

3算例實驗

為了檢驗?zāi)Ｐ颓蠼庑Ч?，本文對?shù)學(xué)模型和計算機仿真模擬算法在不同參數(shù)下的結(jié)果進行了對比。參數(shù)設(shè)置及詳細說明如表1所示[4]。

表1智能加工系統(tǒng)作業(yè)參數(shù)表Table 1 Parameter table of intelligent machining system

基于本文數(shù)學(xué)模型，利用Matlab 2014a，調(diào)用Gurobi軟件包進行編程，對表1中的3組參數(shù)進行小規(guī)模物料加工求解，均得到全局最優(yōu)解。當(dāng)加工物料規(guī)模比較大時，耗時非常長。以第1組參數(shù)為例，當(dāng)系統(tǒng)中有8個CNC機床，加工18個物料時，進行10次求解，平均耗時446.62 s；加工32個物料時，平均求解耗時近1 h，這在實際生產(chǎn)過程中是不可接受的。對計算的結(jié)果進行比較發(fā)現(xiàn)，加工32個物料的前18個解與加工18個物料的解完全相同，若以第1～16的解作為初始解，則求解第17～32的解耗時與求解第1～16個解的耗時基本相同。以此類推，可以求解中等規(guī)模的問題。而對于大規(guī)模問題的求解，采用上述階段賦初值的策略仍然費時費力。

采用本文設(shè)計的計算機仿真模擬算法，并利用Matlab 2014a進行算法實現(xiàn)，對3組參數(shù)進行與上述數(shù)學(xué)模型相應(yīng)規(guī)模的計算，發(fā)現(xiàn)計算結(jié)果完全相同，并且耗時非常短。圖3～5是RGV分別與6個、8個、10個CNC機床在第1組參數(shù)設(shè)置下協(xié)調(diào)作業(yè)生產(chǎn)調(diào)度狀態(tài)圖。為了直觀分析，只截取顯示了0～3 000 s的RGV與CNC機床協(xié)調(diào)作業(yè)圖。每個圖中的圖(a)為RGV分別為每個CNC機床服務(wù)狀態(tài)示意圖，圖中的星號表示物料上料開始及結(jié)束時刻，圓圈表示物料下料開始及結(jié)束時刻，若二者重合，表示物料上下料時刻重合。三角圖標表示清洗結(jié)束時刻，虛線表示RGV移動及等待時間區(qū)間。圖(b)中的每個線段表明相應(yīng)CNC機床的加工作業(yè)時間區(qū)間，星號之間的間斷為CNC機床空閑時間區(qū)間。圖(c)為RGV的4種狀態(tài)：上下料、移動、清洗和等待。從圖3～5中可以看出，500 s以后加工系統(tǒng)的RGV調(diào)度就出現(xiàn)了周期特性。每個圖的RGV和CNC機床工作效率并不一樣：圖3中的每個周期RGV均存在著較長的空閑等待(188 s)，而CNC機床不存在超長等待(超長等待是指除上下料等待之外的空閑等待)；圖4中每個周期RGV空閑等待的時間相對少得多(46 s)，CNC機床不存在超長等待(0 s)；圖5中每個周期RGV不存在空閑等待，但CNC機床存在超長等待(96 s)。

利用表1提供的3組參數(shù)數(shù)據(jù)，在RGV協(xié)調(diào)不同數(shù)量的CNC機床加工作業(yè)8小時(28 800 s)的情況下，系統(tǒng)加工完成物料個數(shù)及RGV、CNC機床周期穩(wěn)定后的等待時長數(shù)據(jù)匯總?cè)绫?所示。韓中庚等[3]利用表1中提供的3組參數(shù)，在RGV與8個CNC機床單工序協(xié)調(diào)作業(yè)8 h加工完成的物料個數(shù)分別為383、359、392，與本文模型RGV協(xié)同相同數(shù)量的CNC機床作業(yè)下求解出來的結(jié)果相同。這說明本文建立的模型是有效的。另外，從表2中的匯總數(shù)據(jù)不難發(fā)現(xiàn)，第1組參數(shù)RGV與10個CNC機床協(xié)調(diào)作業(yè)，加工物料數(shù)量最多；第2組參數(shù)RGV與8個CNC機床協(xié)調(diào)作業(yè)，加工物料數(shù)量最多；第3組參數(shù)RGV與10個CNC機床協(xié)調(diào)作業(yè)，加工物料數(shù)量最多。所以，RGV和CNC機床相互配合，即RGV不存在等待，而CNC機床等待時間盡可能少，加工系統(tǒng)的工作效率更高。

圖3單RGV與6個CNC機床協(xié)調(diào)作業(yè)狀態(tài)示意圖Figure 3 Diagram of coordinated operation between RGV and 6 CNC machine tools

圖4單RGV及8個CNC機床協(xié)調(diào)工作狀態(tài)示意圖Figure 4 Diagram of coordinated operation between RGV and 8 CNC machine tools

圖5單RGV及10個CNC機床協(xié)調(diào)工作狀態(tài)示意圖Figure 5 Diagram of coordinated operation between RGV and 10 CNC machine tools

表2表1參數(shù)下RGV協(xié)調(diào)CNC機床產(chǎn)出狀態(tài)匯總1)Table 2 Summary on RGV coordination CNC under parameters in Table 1

4結(jié)論

在直線布局的智能加工系統(tǒng)中，負責(zé)物料搬運直線往復(fù)的RGV與負責(zé)加工的CNC機床協(xié)調(diào)作業(yè)非常重要。RGV調(diào)度策略及協(xié)調(diào)恰當(dāng)數(shù)量的CNC機床對智能加工系統(tǒng)的加工效率有直接影響。本文首先介紹了問題的實際背景和系統(tǒng)的作業(yè)流程?？紤]到智能RGV與加工設(shè)備CNC機床協(xié)調(diào)作業(yè)的特點，建立了以RGV與CNC機床協(xié)調(diào)作業(yè)完成物料下料時刻之和最小為目標的非線性整數(shù)規(guī)劃模型。根據(jù)RGV與CNC機床物料加工調(diào)度特征，提出計算機仿真算法并對問題進行了求解。在RGV不存在等待、CNC機床等待盡可能少，即在RGV和CNC機床相互配合的情況下，最優(yōu)調(diào)度方案的工作效率最高。為了檢驗算法的有效性，利用文獻[4]提供的3組參數(shù)對模型的實用性和有效性進行了驗證，并給出了最優(yōu)調(diào)度方案的實際運行結(jié)果。本文為RGV與CNC機床協(xié)調(diào)作業(yè)策略研究提供了一定的參考，對工業(yè)加工生產(chǎn)具有一定的借鑒意義。