隨機批量物料搬運的制造系統(tǒng)AGV配置優(yōu)化

張惠煜，陳慶新，毛 寧

廣東工業(yè)大學 廣東省計算機集成制造重點實驗室，廣州 510006

定制型裝備制造企業(yè)生產(chǎn)系統(tǒng)屬于復雜的離散制造系統(tǒng)，具有隨機不確定性（訂單到達、工序工時以及返修等不確定因素）、生產(chǎn)周期長、拖期現(xiàn)象嚴重以及多品種大規(guī)模在制品等特點。由于生產(chǎn)車間物料搬運任務十分龐大，基于AGV（Automatic Guided Vehicle）的物料搬運系統(tǒng)（Material Handling System）成為生產(chǎn)車間至關重要的組成部分。AGV的數(shù)量對系統(tǒng)性能的優(yōu)化具有顯著的影響，然而這類設備的價格昂貴，在制造系統(tǒng)中如何以最低的成本優(yōu)化配置AGV 的類型及數(shù)量，以滿足系統(tǒng)產(chǎn)能及訂單交貨期的需求，是系統(tǒng)設計階段的關鍵問題[1-2]。本文考慮的AGV配置問題是一個具有雙重約束的隨機非線性整數(shù)規(guī)劃問題，然而這些約束（系統(tǒng)產(chǎn)能和訂單交貨期）無法用決策變量（AGV數(shù)量）的封閉形式表達。因此，建立一個有效的性能分析模型以獲得系統(tǒng)運行指標是求解AGV配置優(yōu)化問題的基礎。

AGV 的數(shù)量配置問題是AGV 系統(tǒng)設計及控制的主要問題之一，目前求解的主要方法可以分為兩類：解析方法（基于數(shù)學理論建立數(shù)學模型進行求解計算）和仿真方法（基于仿真平臺建立仿真模型進行實驗計算）。由于所涉及問題的復雜性，解析方法只能獲得問題的近似解，基于經(jīng)驗統(tǒng)計的仿真實驗可以應用于復雜系統(tǒng)獲得較為精確的結果，然而仿真實驗需要消耗大量的時間[3-4]。文獻[5]根據(jù)AGV行程需求是否已知將問題劃分為確定需求模型（行程需求已知）和隨機需求模型（需要估計AGV 的空載行程），并綜述不同的求解方法。對于隨機系統(tǒng)主要應用排隊理論進行求解，文獻[6]建立排隊模型計算AGV 的數(shù)量使AGV 的可用概率滿足工作站的需求，但這個模型在求解稀疏車流系統(tǒng)時往往高估了AGV的需求數(shù)量。文獻[7]根據(jù)G/G/c排隊模型計算AGV 在傳輸和請求之間的等待時間，以等待時間為約束設計算法優(yōu)化AGV 數(shù)量，該模型不考慮批量處理的情況。文獻[8]基于閉排隊網(wǎng)分析系統(tǒng)穩(wěn)態(tài)行為，并建立線性規(guī)劃模型估算AGV數(shù)量，然而閉排隊網(wǎng)模型是在系統(tǒng)總在制品數(shù)不變基礎上的。

本文研究的制造系統(tǒng)具有兩個特征：（1）隨機批量搬運，成批的物料運輸是一個批處理的過程，為減少AGV空車等待時間縮短生產(chǎn)周期，在AGV到達時若不能滿載也立即運往目的地，因此運輸?shù)呐烤哂须S機性。（2）同等并行AGV，相同類型的AGV具有相同的性能參數(shù)（如額定速率、額定容量等），因此多臺同類型的AGV是同等的，且并行地在各個車間之間執(zhí)行物料運輸任務。上述特征使得系統(tǒng)模型更為復雜，求解更為困難。

綜上所述，目前優(yōu)化AGV 配置的規(guī)劃模型并未考慮隨機批量處理的問題，而針對具有隨機批量處理特征且緩沖區(qū)容量有限的排隊網(wǎng)性能分析方法也尚未見報道。因此，本文針對定制型生產(chǎn)方式，考慮具有隨機批量搬運和同等并行AGV的制造系統(tǒng)，基于Markov過程的排隊網(wǎng)絡理論建立系統(tǒng)的性能分析模型，進而求解以最小化AGV 投資成本為目標，具有系統(tǒng)產(chǎn)出率和生產(chǎn)周期雙重約束的AGV配置優(yōu)化模型。

1 問題描述

如圖1所示，工件需要先后經(jīng)過粗加工車間和精加工車間進行加工，AGV 在兩個車間的半成品緩存區(qū)之間并行地往返運輸工件。AGV具有四種狀態(tài)：裝載（含“饑餓等待”）→負載行程→卸載（含“阻塞等待”）→空載返程。（1）裝載時的饑餓等待：AGV 到達半成品緩沖區(qū)Buffer2 裝載工件時，若 Buffer2 不為空，則 AGV 即使不能滿載也立即運往半成品緩存區(qū)Buffer3；若Buffer2 為空，則AGV 需要等待直至有1 個工件在粗加工車間完工并進入Buffer2，這種狀態(tài)稱為“饑餓”（Starvation）。（2）卸載時的阻塞等待：AGV到達半成品緩存區(qū)Buffer3卸載工件時，若Buffer3 已滿而AGV 尚不能完全卸載，則AGV 需要等待直至全部工件卸載完成才能空車返回，這種狀態(tài)稱為“阻塞”（Blocking）。由于阻塞、饑餓等因素的影響降低了AGV的效率。

圖1 AGV物料搬運的制造系統(tǒng)

本文考慮以系統(tǒng)產(chǎn)出率和生產(chǎn)周期為約束的制造系統(tǒng)中AGV 配置的優(yōu)化問題，其目標是優(yōu)化AGV 數(shù)量，從而最小化AGV投資成本，同時滿足系統(tǒng)產(chǎn)能及訂單交貨期的要求。

定義參數(shù)如下：

i：AGV類型，i=1,2,…,n；

ui：第i類AGV的采購單價；

xi：第i類AGV配置的數(shù)量；

X：AGV數(shù)量配置向量，X={xi}；

Q：AGV投資成本；

Θ：系統(tǒng)平均產(chǎn)出率，即單位時間系統(tǒng)輸出完成品的平均數(shù)量；

Γ：系統(tǒng)平均生產(chǎn)周期，即每個工件在系統(tǒng)中停留的平均時間；

E{·}：隨機函數(shù)的數(shù)學期望；

ξ：隨機元。

該優(yōu)化問題的數(shù)學模型如下：

式（1）表示優(yōu)化目標，即求解AGV優(yōu)化配置的向量X*，使得AGV 投資成本最??；式（2）表示平均產(chǎn)能約束，實際平均產(chǎn)出率不小于目標平均產(chǎn)出率Θmin；式（3）表示平均生產(chǎn)周期約束，實際平均生產(chǎn)周期不大于目標平均生產(chǎn)周期Γmax；式（4）表示X為非負整數(shù)型向量。由于E{Θ(X;ξ)}和E{Γ(X;ξ)}無法用明顯的數(shù)學函數(shù)式進行描述，無法應用傳統(tǒng)的非線性整數(shù)規(guī)劃方法求解。為此，針對問題的隨機性和非線性，本文提出一種基于排隊網(wǎng)求解系統(tǒng)性能指標的算法對該優(yōu)化模型進行求解。

2 系統(tǒng)性能分析方法

目前針對物料搬運系統(tǒng)性能分析的模型已有大量的研究成果，采用的建模方法包括整數(shù)規(guī)劃模型、網(wǎng)絡流模型、排隊論模型和Markov模型等，但這些建模方法各有不足[9]。文獻[10]根據(jù)文獻[9]提出的擴展馬爾可夫鏈模型建立考慮多運輸AGV堵塞特性系統(tǒng)的排隊網(wǎng)絡模型，但其建立的均為閉環(huán)排隊網(wǎng)模型（即系統(tǒng)在制品數(shù)量為常數(shù)，系統(tǒng)無實時輸入流、輸出流），而且物料運輸過程中不考慮批量處理的問題。文獻[11]針對物料搬運系統(tǒng)建立有限緩沖區(qū)開排隊網(wǎng)模型，但未考慮批量搬運情形。針對具有有限緩沖區(qū)、隨機批量搬運的問題，文獻[12]考慮服務速率與批量大小相關的狀態(tài)相關排隊模型并提出一種Unifying Method 分析其性能指標，但均為針對單個隊列的模型，并不能直接應用于具有復雜拓撲結構、隊列之間存在耦合關聯(lián)的網(wǎng)絡系統(tǒng)。

人們所面臨的系統(tǒng)在制品數(shù)量為隨機變量且各緩沖區(qū)容量是有限的，因此采用有限緩沖區(qū)的開排隊網(wǎng)模型描述。有限緩沖區(qū)開排隊網(wǎng)模型在制造系統(tǒng)建模與分析中具有重要應用，與無限緩沖區(qū)的模型不同，堵塞和死鎖（Deadlock）的現(xiàn)象使得其不具有乘積形式的解（Product-Form Solution）[13]，因此求解難度更大。傳統(tǒng)的精確計算方法[13]雖然可以獲得精確解，但隨著系統(tǒng)規(guī)模的增大（如系統(tǒng)隊列數(shù)、緩存容量等）會導致狀態(tài)空間的“維數(shù)災”問題。為解決此問題，文獻[14]提出一種基于Markov過程的“狀態(tài)空間分解法”建立系統(tǒng)的性能分析模型，且仿真結果驗證了該方法近似結果的精確性和有效性。文獻[15]應用該分解方法以任務拒絕率為約束條件提出一種緩沖區(qū)容量配置的優(yōu)化方法。

針對傳統(tǒng)制造系統(tǒng)的狀態(tài)空間分解法將整個系統(tǒng)按照節(jié)點（緩存區(qū)+工作中心）分解為若干個子系統(tǒng)，每個子系統(tǒng)是相對獨立的，并通過建立連續(xù)時間馬爾可夫鏈（Continuous-Time Markov Chain，CTMC）[16]模型建立子系統(tǒng)之間的耦合關聯(lián)。在每個子系統(tǒng)中，按CTMC模型分別建立描述子系統(tǒng)的狀態(tài)空間，并根據(jù)“生滅過程”理論分析狀態(tài)轉移規(guī)律，構建一系列的穩(wěn)態(tài)平衡方程組，接著迭代求解獲得每種狀態(tài)的穩(wěn)態(tài)概率，最后依據(jù)這些狀態(tài)概率值計算系統(tǒng)的性能指標值。與傳統(tǒng)的精確法對比，這在很大程度上降低了系統(tǒng)狀態(tài)空間的規(guī)模，因此該方法能夠求解較大規(guī)模的系統(tǒng)模型?；趥鹘y(tǒng)狀態(tài)空間分解法的思路，本文將其拓展，應用于含隨機批處理、同等并行AGV的制造系統(tǒng)建立性能分析模型。

2.1 排隊網(wǎng)絡模型

建立如圖2所示的有限緩沖區(qū)開排隊網(wǎng)模型，其中方框表示有限容量的緩存區(qū)，圓圈表示工作中心，弧線表示工件流，箭頭表示工件流向。

圖2 制造系統(tǒng)排隊網(wǎng)示意模型

該模型滿足以下假設條件：

工件到達系統(tǒng)的隨機過程為泊松過程，每個工件的到達是獨立的，平均到達速率為λ。

系統(tǒng)排隊模型為“混合制（損失、阻塞）”[17]：工件到達系統(tǒng)時若緩存區(qū)B1已滿，則工件被拒絕；否則進入B1，若工作站W(wǎng)1正在加工，則其加入隊列排隊。

每個工作站包含一臺加工設備，服務時間（含設備準備時間）服從負指數(shù)分布，W1和W4的平均加工速率分別為μ1和μ4，每個工件的加工時間是獨立的，且加工過程一旦開始就不可中斷。

緩沖區(qū)B1、B2和B4的容量是有限的，最大容量分別為N1、N2和N4。

系統(tǒng)服務規(guī)則為“先到先服務（FCFS）”。

系統(tǒng)阻塞機制為“服務后阻塞（BAS）”。

不同類型的AGV 具有不同的行駛速率，且到達B2或B4的間隔時間是獨立的，服從負指數(shù)分布，類型iAGV 的平均到達速率為Vi；AGV 行駛的平均速率為2dVi，其中d為軌道長度（即兩個車間之間的距離）。

不同類型的AGV 具有不同的裝載容量，第i類AGV的最大裝載容量為Ci。

AGV的調(diào)度規(guī)則如下：

每臺AGV 按照特定的軌道在B2或B4之間往返，即AGV之間相互獨立，沒有“堵車”現(xiàn)象發(fā)生。

AGV在B2裝載時服從FCFS規(guī)則，當AGV到達B2時，若B2中存在至少一個工件，AGV 裝載并立即前往B4，否則等待。

AGV在B4裝載時服從FCFS規(guī)則，若B4容量達到上限，則等待直至全部卸載并返回B2。

2.2 節(jié)點分解模型

AGV搬運批量的大小是與它的前緩存區(qū)(B2)中當前工件數(shù)有關的隨機變量。建立如圖3 所示的節(jié)點分解模型，節(jié)點1為不與AGV直接相關的節(jié)點，是傳統(tǒng)的“單個到達、單個離開”的模型；在B2后添加一個加工時間為0的虛擬工作站W(wǎng)2構成節(jié)點2，具有“單個到達、批量離開”的特征；將AGV的批處理過程視為加工速率為V的批量處理工作站V3，即節(jié)點3，具有“批量到達、批量離開”的特征；節(jié)點4 工件轉移的特征為“批量到達、單個離開”。

圖3 節(jié)點分解的排隊網(wǎng)模型

通過構造各個節(jié)點的狀態(tài)空間，從而建立狀態(tài)轉移平衡方程，并分析V3節(jié)點的狀態(tài)轉移建立節(jié)點2 和節(jié)點4之間的耦合關聯(lián)。

2.3 狀態(tài)轉移分析

文獻[18]證明對于k臺同等的（相同的運行速度、容量）AGV，可當量為一臺具有k倍運行速度的AGV進行分析。為簡化描述，以單臺AGV為例，建立節(jié)點3狀態(tài)空間如下：

其中，w3表示AGV運載的工件數(shù)量。b3表示AGV的狀態(tài)：b3=-1 為AGV處于“饑餓等待”狀態(tài)（此時w3=0）；b3=0 為 AGV 處于“空載返程”狀態(tài)（此時w3=0）；b3=1 為AGV 處于“負載行程”狀態(tài)（此時1 ≤w3≤C）；b3=2 為 AGV 處于“阻塞等待”狀態(tài)（此時 1 ≤w3≤C）。該節(jié)點狀態(tài)空間及狀態(tài)之間的轉移如圖4所示。

圖4 節(jié)點3的狀態(tài)轉移示意圖

根據(jù)系統(tǒng)的 Markov 性，當 AGV 到達B2時，B2中具有n個工件的概率均為P2(n),0 ≤n≤N2，而P2(n)是與AGV狀態(tài)無關的變量。因此，AGV從空載返程的狀態(tài)S3(0,0) 轉變?yōu)轲囸I等待狀態(tài)S3(0,-1) 或者負載行程 狀態(tài)S3{(w3,1),1 ≤w3≤C} 的 概率 分 別為P3(0)load、P3(w3)load，其中：

因此AGV 狀態(tài)的轉移速率分別為VP3(0)load、VP3(w3)load。

當AGV 在B2處于饑餓等待狀態(tài)時，AGV 將轉變?yōu)樨撦d行程狀態(tài)直至W1中加工完成的一個工件到達B2（有效到達率為，將在下一節(jié)分析），因此AGV 由狀態(tài)S3(0,-1)轉變?yōu)闋顟B(tài)S3(1,1)的轉移速率為。

當 AGV 到達B4時，AGV 能否卸貨取決于 AGV 當前裝載量w3和B4的當前剩余容量k。當k≥w3時，AGV 能完全卸載，因此由負載行程狀態(tài)S3{(w3,1),1 ≤w3≤C} 轉變?yōu)榭蛰d返程狀態(tài)S3(0,0) 的轉移速率為當k ＜w時，尚有w-k個工件未能33卸載，AGV 由狀態(tài)S3(w3,1) 轉變到阻塞等待狀態(tài)S3(w3-k,2)的速率為VPb4(w3)。其中Pb4(k)為B4當前剩余容量為k的概率。

當AGV 在B4處于阻塞等待狀態(tài)時，AGV 上有w3個工件尚未卸載，隨著在W4上完工的工件離開系統(tǒng)（有效加工速率為4），AGV 上未卸載工件逐漸減少直至全部卸載w3=0 并空載返回B2，即由狀態(tài)S3(w3,2)轉變?yōu)镾3(0,0)的轉移速率為。

AGV的整個運行過程是一個“生滅過程”[16]，在每個循環(huán)中依次經(jīng)歷四種狀態(tài)。系統(tǒng)穩(wěn)態(tài)時，AGV 處于負載行程狀態(tài)或空載返程狀態(tài)的平均時間為T0=T1=V-1，處于饑餓等待狀態(tài)或阻塞等待狀態(tài)的平均等待時間為Ti=V-1×PS3(i)/PS3(0),i=-1,2，其中PS3(b3)為AGV處于各個狀態(tài)S3(w3,b3)的穩(wěn)態(tài)概率。

AGV 在節(jié)點2 和節(jié)點4 裝載和卸載的過程可視為一個交錯更新過程[16]，且只在AGV 到達的更新時間點發(fā)生。對于AGV 單元前節(jié)點（節(jié)點2），AGV 由離開直至首次到達的間隔時間T2-2=T1+T2+T0內(nèi)，經(jīng)歷負載行程S3{(w3,1),1 ≤w3≤C}、卸載（阻塞等待）S3{(w3,2),1 ≤w3≤C}、空載返程S3(0,0)三個階段；對于AGV單元后節(jié)點（節(jié)點4），AGV由離開直至首次到達的間隔時間T4-4=T0+T-1+T2內(nèi)，經(jīng)歷空載返程S3(0,0)、裝載（饑餓等待）S3(0,-1)、負載行程S3{(w3,1),1 ≤w3≤C}三個階段。

根據(jù)系統(tǒng)Markov 過程的“生滅過程”理論，對每個狀態(tài)可列出對應的一個狀態(tài)轉移平衡方程，因此各節(jié)點可列出與其狀態(tài)總數(shù)一致的狀態(tài)轉移平衡方程組。以狀態(tài)S3(0,0)為例，輸入的狀態(tài)為S3(w3,1)和S3(1,2)，對應的轉移速率分別為輸出的速率為因此，根據(jù)輸入與輸出狀態(tài)轉移平衡可以建立如下方程組：

同理，節(jié)點3共有2(C+1)個狀態(tài)，針對其他狀態(tài)建立的轉移平衡方程組如下：

對于節(jié)點m=1,2,3,4，由其狀態(tài)轉移平衡方程組中未知變量（即各狀態(tài)穩(wěn)態(tài)概率）PSm(wm,bm)的系數(shù)可構成大型稀疏矩陣πm,因此只要求解齊次線性方程組πm xm=0就可獲得各狀態(tài)的穩(wěn)態(tài)概率值。本文應用Gauss-Seidel迭代法[13]迭代求解各節(jié)點方程組πm xm=0，由于節(jié)點間的耦合關聯(lián)，當前節(jié)點的轉移速率參數(shù)可由其關聯(lián)節(jié)點在上一次迭代的結果計算得出。在迭代過程收斂后，最終可獲得系統(tǒng)各狀態(tài)的穩(wěn)態(tài)概率值PSm(wm,bm)，據(jù)此可計算系統(tǒng)性能指標值：平均產(chǎn)出率和生產(chǎn)周期。

3 AGV配置優(yōu)化算法

優(yōu)化問題是一個隨機非線性整數(shù)規(guī)劃問題，而且約束函數(shù)無法用一個封閉的數(shù)學方程式表達，因此在滿足預設系統(tǒng)產(chǎn)能（輸出率）和產(chǎn)品交貨期（生產(chǎn)周期）的情況下，采用嵌入排隊網(wǎng)模型的禁忌搜索算法優(yōu)化AGV的配置方案，其算法流程圖如圖5所示。

步驟1初始化

采用二進制編碼，由變量松弛法獲取初值。

步驟2解空間搜索

圖5 禁忌搜索算法流程圖

步驟2.1采用隨機選擇兩個編碼的位轉變?yōu)橄喾粗档臄_動策略，產(chǎn)生新解。

步驟2.2調(diào)用排隊網(wǎng)模型求解系統(tǒng)性能指標值，判斷是否滿足約束條件，若滿足，則進入步驟2.3；否則返回步驟2.1。

步驟2.3通過擾動策略產(chǎn)生多個不同的解，并從中選擇最優(yōu)的解，一旦該操作所得的解被選擇，禁止其執(zhí)行動作的相關操作。

步驟2.4檢索是否破禁：當該被禁操作處于被禁準則，但其值所得的目標函數(shù)優(yōu)于歷史最優(yōu)解，則接受該動作執(zhí)行破禁操作，并更新最優(yōu)解記錄。

步驟3終止判斷

判斷是否滿足終止準則（最高擾動次數(shù)），若滿足，則當前解為最終解；否則返回步驟2.1。

4 算例分析

對于算例求解的操作系統(tǒng)環(huán)境為Microsoft Win10，硬件環(huán)境為CPU 3.30 GHz，4.00 GB RAM，對于解析算法的求解采用Matlab R2018a軟件平臺編程實現(xiàn)。

4.1 仿真實驗

如圖6 所示為在Tecnomatix Plant Simulation 8.2上建立的仿真模型示例。基于離散事件仿真理論，在大樣本的條件下，構造統(tǒng)計估計量（系統(tǒng)平均產(chǎn)出率和平均生產(chǎn)周期）并計算采集的數(shù)據(jù)樣本。仿真實驗每次運行1 000天（仿真時間），并在95%的置信度下進行50次獨立重復實驗，最終計算系統(tǒng)性能指標的均值。

4.2 實驗算例及結果分析

為驗證本文提出近似解法的有效性，并分析AGV配置參數(shù)對系統(tǒng)性能指標的影響及規(guī)律，本文設計實驗方案進行求解，并將結果與仿真實驗進行對比分析。

設計自變量（影響因素）如下：小車到達速率V；小車容量C；小車數(shù)量n。

設計因變量（實驗指標）如下：系統(tǒng)產(chǎn)出率Θ；系統(tǒng)生產(chǎn)周期Γ。

圍繞實驗目標問題，針對不同因素設計3組單因素實驗和1 組雙因素實驗，具體參數(shù)如表1 所示。各組實驗算例求解結果如表2 所示，其中“Δ/%”為近似結果相對仿真結果的偏差百分比。與仿真結果對比，本文改進的狀態(tài)空間分解法對于計算系統(tǒng)平均產(chǎn)出率的偏差率均在±3%內(nèi)，計算系統(tǒng)平均生產(chǎn)周期的偏差率均在±6%內(nèi)，并且每次計算所需的時間遠遠小于仿真所需耗時。因此，可以看出本文近似方法對于系統(tǒng)性能的分析和計算具有良好的適應性。

表1 實驗方案的系統(tǒng)參數(shù)

圖6 系統(tǒng)仿真模型示例

表2 算例求解結果

如圖7 所示為各組實驗中因變量隨自變量的變化規(guī)律曲線，由實驗結果可以看出：（A）單獨增加AGV 的運載速率，系統(tǒng)平均產(chǎn)出率略有提高，而系統(tǒng)平均生產(chǎn)周期則有明顯的縮短；（B）單獨增加AGV 的運載容量，系統(tǒng)平均產(chǎn)出率略有提高，而系統(tǒng)平均生產(chǎn)周期也有略微的縮短；（C）增加同等并行AGV 的數(shù)量，系統(tǒng)平均產(chǎn)出率略有提高，而系統(tǒng)平均生產(chǎn)周期則有明顯的縮短；（D）保持AGV的當量運載能力（=AGV運載速率×AGV運載容量）不變的情況下，隨著AGV運載速率的提高和AGV運載容量的降低，系統(tǒng)平均產(chǎn)出率有明顯的提高，而系統(tǒng)平均生產(chǎn)周期也有明顯的縮短。

圖7 因變量隨自變量變化規(guī)律

對于AGV 配置參數(shù)的單因素實驗（A）～（C），增加AGV 的運載速率或數(shù)量，則在制品運輸環(huán)節(jié)的服務速率增大，即在制品的運輸時間減少，因此系統(tǒng)產(chǎn)出率增大，而生產(chǎn)周期減少。增加AGV的運載容量，可能增加AGV 每次運輸?shù)脑谥破窋?shù)量，減少每個在制品的平均運輸時間，但是這也可能會提高AGV 在卸載在制品時“阻塞等待”的概率，因此運載容量的變化對系統(tǒng)性能的影響并不顯著。對于AGV運載速率和運載容量的雙因素實驗（D），當量運載能力不變時，提高AGV 速率并減少運載容量，增大了AGV 在運輸過程中保持滿載的概率，AGV 每次運輸?shù)臅r間縮短，從而AGV 的實際運載能力會有提高，因此系統(tǒng)產(chǎn)出率得以提高，同時縮短了生產(chǎn)周期。

綜上所述，合理地配置AGV的數(shù)量等參數(shù)，可以有效地提高系統(tǒng)產(chǎn)出率并且縮短生產(chǎn)周期。

4.3 優(yōu)化案例

以圖1所示的某裝備制造企業(yè)生產(chǎn)系統(tǒng)為例，為了在兩個車間之間配置AGV 執(zhí)行物料運輸任務，需要確定AGV配置的最優(yōu)方案。兩個車間的距離為d=100 m，如表3 所示，有三種類型的AGV 可供選擇。系統(tǒng)產(chǎn)能及訂單交貨期的約束為：系統(tǒng)產(chǎn)出率不低于Θmin=0.95個/min，而生產(chǎn)周期不超過Γmax=18 min。根據(jù)主生產(chǎn)計劃的任務投放速率為λ=1.0個/min，兩個車間的平均加工速率分別為μ1=1.1個/min 和μ4=1.2個/min。

表3 三類AGV的性能參數(shù)

根據(jù)嵌入排隊網(wǎng)模型的禁忌搜索算法求得算例優(yōu)化的結果如表4 所示，其中標記“*”的方案為最優(yōu)配置方案。由于問題規(guī)模較小，可以通過枚舉搜索的方法獲得全局最優(yōu)解，即逐一增加每類AGV的數(shù)量，計算系統(tǒng)性能指標值并判斷是否滿足約束條件，最后從所有可行解中選擇成本最低的為最優(yōu)解，求解過程的系統(tǒng)性能參數(shù)變化曲線如圖8 所示。由表4 和圖8 的結果可以看出，禁忌搜索算法獲得的最優(yōu)解與枚舉搜索獲得的全局最優(yōu)解一致，驗證了禁忌搜索方法的有效性?；谙到y(tǒng)產(chǎn)出率和生產(chǎn)周期的約束，以最小化AGV 投資成本為目標，配置4臺類型II的AGV為該目標下的最優(yōu)配置方案，以滿足系統(tǒng)產(chǎn)能及訂單交貨期的要求。另外，表4中與仿真結果的相對偏差率進一步驗證了改進狀態(tài)空間分解法的有效性及精確性。由此可以看出本文所提出的求解系統(tǒng)性能指標值及AGV配置優(yōu)化算法的合理性及有效性，這種方法可以推廣到較大規(guī)模的系統(tǒng)分析及資源優(yōu)化配置中。

表4 算例優(yōu)化結果

圖8 優(yōu)化過程中系統(tǒng)性能的變化曲線

5 結束語

本文建立了隨機非線性整數(shù)規(guī)劃模型，描述了智能車間物料搬運系統(tǒng)的AGV數(shù)量配置問題。針對具有隨機批量搬運的生產(chǎn)系統(tǒng)，建立有限緩沖區(qū)開排隊網(wǎng)模型，并拓展狀態(tài)空間分解法計算系統(tǒng)性能指標值，最后將其嵌入禁忌搜索算法，求解AGV配置優(yōu)化問題。

通過算例求解及結果分析，與仿真結果對比，拓展的狀態(tài)空間分解法計算系統(tǒng)性能指標值具有較高的精確度，基于該方法求解性能指標值的優(yōu)化算法可以獲得合理的AGV配置最優(yōu)方案。因此這種方法可以應用于求解較大規(guī)模的系統(tǒng)資源優(yōu)化配置問題。