張惠煜，陳慶新，毛 寧

廣東工業(yè)大學(xué) 廣東省計(jì)算機(jī)集成制造重點(diǎn)實(shí)驗(yàn)室，廣州 510006

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

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

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

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

1 問(wèn)題描述

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

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

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

定義參數(shù)如下：

i：AGV類(lèi)型，i=1,2,…,n；

ui：第i類(lèi)AGV的采購(gòu)單價(jià)；

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

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

Q：AGV投資成本；

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

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

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

ξ：隨機(jī)元。

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

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

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

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

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

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

2.1 排隊(duì)網(wǎng)絡(luò)模型

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

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

該模型滿(mǎn)足以下假設(shè)條件：

工件到達(dá)系統(tǒng)的隨機(jī)過(guò)程為泊松過(guò)程，每個(gè)工件的到達(dá)是獨(dú)立的，平均到達(dá)速率為λ。

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

每個(gè)工作站包含一臺(tái)加工設(shè)備，服務(wù)時(shí)間（含設(shè)備準(zhǔn)備時(shí)間）服從負(fù)指數(shù)分布，W1和W4的平均加工速率分別為μ1和μ4，每個(gè)工件的加工時(shí)間是獨(dú)立的，且加工過(guò)程一旦開(kāi)始就不可中斷。

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

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

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

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

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

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

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

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

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

2.2 節(jié)點(diǎn)分解模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟1初始化

采用二進(jìn)制編碼，由變量松弛法獲取初值。

步驟2解空間搜索

圖5 禁忌搜索算法流程圖

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

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

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

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

步驟3終止判斷

判斷是否滿(mǎn)足終止準(zhǔn)則（最高擾動(dòng)次數(shù)），若滿(mǎn)足，則當(dāng)前解為最終解；否則返回步驟2.1。

4 算例分析

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

4.1 仿真實(shí)驗(yàn)

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

4.2 實(shí)驗(yàn)算例及結(jié)果分析

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

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

設(shè)計(jì)因變量（實(shí)驗(yàn)指標(biāo)）如下：系統(tǒng)產(chǎn)出率Θ；系統(tǒng)生產(chǎn)周期Γ。

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

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

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

表2 算例求解結(jié)果

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

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

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

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

4.3 優(yōu)化案例

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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