謝潔明，陳慶新，毛 寧，張惠煜

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

0 引言

車間設(shè)施布局規(guī)劃是制造系統(tǒng)設(shè)計(jì)的重要環(huán)節(jié)，合理的布局可以提高車間生產(chǎn)效率，降低10%～30%的生產(chǎn)運(yùn)營費(fèi)用[1]。傳統(tǒng)的車間布局不考慮物料儲(chǔ)運(yùn)系統(tǒng)的實(shí)際有限能力，如物料在各單元的上下料等待時(shí)間、在制品搬運(yùn)道路上的擁堵時(shí)間等，然而經(jīng)過資源配置階段后，智能車間的加工能力與物料儲(chǔ)運(yùn)能力已經(jīng)初步達(dá)到平衡的狀態(tài)，這時(shí)物料儲(chǔ)運(yùn)系統(tǒng)的布局結(jié)構(gòu)、各個(gè)制造單元的位置及相應(yīng)的上料與下料(Pick-up/Drop-off, P/D)口的位置等，不但影響負(fù)載/空載運(yùn)輸成本，還會(huì)產(chǎn)生等待運(yùn)輸成本。P/D口布局是一類特殊的布局問題，它在物料儲(chǔ)運(yùn)系統(tǒng)結(jié)構(gòu)、單元塊狀布局及機(jī)器詳細(xì)布局的基礎(chǔ)上，進(jìn)一步細(xì)化確定各單元P/D口的詳細(xì)位置，通過優(yōu)化的布局，降低因個(gè)性化定單的隨機(jī)到達(dá)而導(dǎo)致的車間物流強(qiáng)度在時(shí)間和空間上的不均衡分布，提高車間的物料運(yùn)輸和生產(chǎn)效率。本文研究考慮有限物料運(yùn)輸能力的智能車間單元P/D口布局優(yōu)化，物料儲(chǔ)運(yùn)系統(tǒng)的有限能力具體體現(xiàn)在：緩沖區(qū)內(nèi)儲(chǔ)位的有限數(shù)量、小車的有限運(yùn)載量、有限數(shù)量的小車、小車的有限運(yùn)行速度等。

設(shè)施規(guī)劃問題可以被描述成離散二次分配問題(Quadratic Assignment Problem, QAP)或混合整數(shù)規(guī)劃問題(Mixed Integer Programming, MIP)[2]，屬于NP難問題。隨著更加復(fù)雜的不等面積設(shè)施布局問題的出現(xiàn)，文獻(xiàn)[3]針對(duì)QAP模型提出一種基于遺傳算法的混合算法確定布局順序和設(shè)施大小，接著用一種新的布局策略確定設(shè)施位置，最后用線性規(guī)劃模型優(yōu)化方案；文獻(xiàn)[4]針對(duì)不等面積設(shè)施布局問題，以物料搬運(yùn)成本和設(shè)施的貼近度為目標(biāo)構(gòu)建了一個(gè)無重疊約束的優(yōu)化問題，采用基于Pareto優(yōu)化的局部搜索和基于小生境技術(shù)的全局搜索相結(jié)合的啟發(fā)式算法，得到了問題的Pareto最優(yōu)解。當(dāng)同時(shí)考慮了設(shè)施、P/D口、物流路徑的設(shè)施布局時(shí)，問題將變得更復(fù)雜，學(xué)者們開發(fā)了諸多啟發(fā)式算法嘗試解決這類問題，常常采用分階段的方法進(jìn)行布局。文獻(xiàn)[5]針對(duì)含P口和D口的不等面積矩形設(shè)施的布局問題，以最小化總物料搬運(yùn)成本為目標(biāo)，提出一種雙啟發(fā)式算法，首先按順序放置設(shè)施來構(gòu)造設(shè)施的位置，其次改進(jìn)了第一步的結(jié)果，結(jié)果表明該算法能在更短的時(shí)間內(nèi)獲得與以往研究相當(dāng)?shù)牟季仲|(zhì)量；文獻(xiàn)[6]基于考慮設(shè)施間的緊密關(guān)系、P/D口的位置以及設(shè)施的位置，提出一種兩階段的方法，在第一階段提出目標(biāo)規(guī)劃模型以計(jì)算設(shè)施的貼近度，第二階段則通過確定設(shè)施的布置、P/D口的位置最終得到一個(gè)有效的布局。除此之外，文獻(xiàn)[7]提出一種三階段的方法，在第一階段中，使用混合模擬退火算法生成布局，第二階段使用非參數(shù)數(shù)據(jù)包絡(luò)分析法(Data Envelopment Analysis, DEA)識(shí)別無效布局，在第三階段則利用DEA獲得布局的排名，最終得到優(yōu)化的布局。針對(duì)不等面積設(shè)施布局問題，文獻(xiàn)[8]提出珊瑚礁優(yōu)化(Coral Reef Optimization, CRO)算法，作為近年來提出的一種進(jìn)化型算法，其在求解不等面積設(shè)施規(guī)劃問題上展現(xiàn)了優(yōu)良的性能。對(duì)于以復(fù)雜系統(tǒng)中性能指標(biāo)為目標(biāo)的設(shè)施布局問題，文獻(xiàn)[9]采用仿真與遺傳算法相結(jié)合的方法求解，使用仿真計(jì)算生產(chǎn)周期與生產(chǎn)率等系統(tǒng)性能指標(biāo)，而遺傳算法用于優(yōu)化系統(tǒng)性能指標(biāo)，仿真優(yōu)化結(jié)果優(yōu)于傳統(tǒng)的優(yōu)化方法，但缺點(diǎn)是沒有考慮車間擁堵等性能指標(biāo)，也沒有考慮P/D口的位置。對(duì)較復(fù)雜的設(shè)施布局通常以同時(shí)布局或分階段布局的方法，文獻(xiàn)[10]針對(duì)單環(huán)自動(dòng)導(dǎo)引小車(Automated Guided Vehicle, AGV)系統(tǒng)，研究了在確定性需求情況下單元塊狀布局與P/D口同時(shí)優(yōu)化的問題。從近幾年的研究可以看到，有關(guān)群體智能算法[11-16]和基于元啟發(fā)式算法的混合算法[17-19]的研究仍是解決車間設(shè)施布置問題的熱點(diǎn)。以上多數(shù)文獻(xiàn)均基于通用算法和啟發(fā)式方法，針對(duì)特定問題結(jié)構(gòu)和特征，提出高度依賴問題特征的特殊算法，即所謂的一類問題一種算法，這提高了求解特定問題的效率。但針對(duì)算法尋優(yōu)過程中產(chǎn)生的不同布局方案，較少有文獻(xiàn)對(duì)其問題特征進(jìn)行評(píng)價(jià)，并基于評(píng)價(jià)來自適應(yīng)調(diào)整算法的優(yōu)化方向，而不同布局方案的評(píng)價(jià)結(jié)果可能改善算法的搜索方向，從而提高整個(gè)算法的效率。

車間布局優(yōu)化問題的目標(biāo)主要考慮最小化與總物料搬運(yùn)成本相關(guān)的函數(shù)，如總物流成本、總運(yùn)輸距離等。文獻(xiàn)[5]以最小化總物料儲(chǔ)運(yùn)成本(Total Material Handling Cost, TMHC)為目標(biāo)研究不等面積設(shè)施布局問題，其中每個(gè)設(shè)施只有一個(gè)P/D口且可以放置在設(shè)施邊界上或者邊界內(nèi)，TMHC定義為物流量與設(shè)施間P口與D口的直線距離的乘積；文獻(xiàn)[6]以最小化設(shè)施間產(chǎn)品距離和最小化無用空間為目標(biāo)對(duì)考慮P/D口的設(shè)施布局問題進(jìn)行優(yōu)化；文獻(xiàn)[20]以最小化總運(yùn)輸成本為目標(biāo)，對(duì)不等面積但形狀規(guī)則的塊狀布局問題進(jìn)行優(yōu)化，總運(yùn)輸成本是以設(shè)施間P口與D口的物流距離為權(quán)重的物流量加權(quán)和；文獻(xiàn)[21]提出一種螢火蟲算法，以使物料搬運(yùn)成本之和最小，同時(shí)又能滿足部門的縱橫比要求，計(jì)算結(jié)果表明提出的算法是魯棒的。以上文獻(xiàn)都是基于設(shè)施間加權(quán)距離進(jìn)行的設(shè)施布局，優(yōu)點(diǎn)是充分考慮了設(shè)施之間的物流關(guān)系，使之盡可能滿足設(shè)施之間的物流距離與物流強(qiáng)度分布的要求。但是，這些文獻(xiàn)只考慮了負(fù)載運(yùn)輸路程，而實(shí)際生產(chǎn)活動(dòng)中載具的負(fù)載路程也是一個(gè)不可忽視的因素；而且現(xiàn)有設(shè)施布局的研究較少全面地考慮物料儲(chǔ)運(yùn)系統(tǒng)的實(shí)際情況，如現(xiàn)實(shí)中由于物料儲(chǔ)運(yùn)系統(tǒng)的有限運(yùn)輸能力，在不確定性生產(chǎn)環(huán)境下車間物流強(qiáng)度在時(shí)空上呈現(xiàn)不均衡分布，常常導(dǎo)致AGV的擁堵和繞道，并且很可能占據(jù)相當(dāng)大的比重，此種情況下設(shè)施布局的結(jié)果可能與實(shí)際應(yīng)用相差較大，因此有必要在進(jìn)行設(shè)施布局時(shí)將物料儲(chǔ)運(yùn)系統(tǒng)的實(shí)際情況考慮進(jìn)去。

本文針對(duì)具有單向?qū)蚵窂骄W(wǎng)絡(luò)、含多臺(tái)AGV、多重嵌套封閉環(huán)形的物料儲(chǔ)運(yùn)系統(tǒng)，提出基于仿真的遺傳網(wǎng)格自適應(yīng)直接搜索(Genetic Mesh Adaptive Direct Search, GMADS)算法，利用仿真信息和問題特征改善算法搜索方向，在智能車間運(yùn)行性能指標(biāo)的約束條件下，基于物流儲(chǔ)運(yùn)系統(tǒng)的有限能力，以最小化物料運(yùn)輸總成本為目標(biāo)，優(yōu)化車間單元P/D口位置布局。GMADS算法專注于局部最優(yōu)化，嵌入遺傳算法(Genetic Algorithm, GA)既避免了算法過早陷入局部最優(yōu)，又可以在當(dāng)前最優(yōu)解基礎(chǔ)上迭代出更優(yōu)的解。采用拉丁超幾何抽樣法(Latin Hypercube Sampling, LHS)均勻地產(chǎn)生若干具有代表性的可行解，選取其中質(zhì)量最好的作為初始解。本文還提出一種將GMADS每次迭代的新最優(yōu)解與AGV擁堵信息、車間工藝路徑等問題信息相結(jié)合的方法，使算法沿著具有問題特點(diǎn)的方向搜索，從而提高算法效率。為驗(yàn)證所提算法，本文針對(duì)典型單元流水式車間設(shè)計(jì)若干對(duì)比實(shí)驗(yàn)，基于Plant Simulation仿真平臺(tái)與MATLAB算法平臺(tái)建立無導(dǎo)數(shù)仿真優(yōu)化模型，通過仿真優(yōu)化實(shí)驗(yàn)驗(yàn)證了所提算法的有效性與優(yōu)越性，并通過實(shí)際案例說明其在智能車間布局問題具有應(yīng)用價(jià)值。

1 車間上料與下料口布局優(yōu)化模型

1.1 問題描述

在已知區(qū)塊布局和區(qū)塊內(nèi)單元布局的智能制造車間中，多臺(tái)物料運(yùn)輸AGV沿著多重嵌套封閉環(huán)形的單向通道移動(dòng)。已知物料的大工藝路線為單元流水式，即物料大致在車間區(qū)塊間以流水方式移動(dòng)(每個(gè)區(qū)塊包含若干并行的制造單元)，而各個(gè)單元根據(jù)生產(chǎn)實(shí)際選擇合適的生產(chǎn)組織方式。所有單元和路段都在車間的范圍內(nèi)，各個(gè)單元的位置彼此不重疊并且與路段不重疊，其至少有一個(gè)邊與某條路段平行。

單元P/D口布局是一類特殊的布局問題，通過車間的塊狀布局規(guī)劃確定了每個(gè)單元的具體位置與形狀后，在AGV路徑和單元邊界的約束條件下，進(jìn)一步細(xì)化確定每個(gè)單元上料與下料(P/D)口的詳細(xì)位置，如圖1所示。在AGV系統(tǒng)中，AGV往往沿著單元邊界移動(dòng)，因此每個(gè)單元P/D口的位置必須在其與路段接壤的邊上，雖然可以放置在許多不同的位置上，但是為了降低問題的復(fù)雜性，研究者們往往限制其可能的位置[22-23]。針對(duì)車間單元P/D口位置布局優(yōu)化問題，已知經(jīng)過單元內(nèi)的詳細(xì)布局階段，確定了各個(gè)單元的位置及其P/D口若干可選位置，為車間P/D口布局優(yōu)化提供候選方案。

在物料儲(chǔ)運(yùn)系統(tǒng)運(yùn)載能力有限的前提下，由于訂單工藝的差異，以及訂單到達(dá)的不確定性，使得車間物流強(qiáng)度隨時(shí)間持續(xù)變化，而且在各個(gè)路段分布不均衡。在一個(gè)不長(zhǎng)的時(shí)間段內(nèi)，當(dāng)物流強(qiáng)度從低到高變化時(shí)，就必然導(dǎo)致排隊(duì)擁堵與等待現(xiàn)象。因此，AGV的平均擁堵等待時(shí)間和每個(gè)單元P/D口的位置有著十分重要的關(guān)聯(lián)。為了提高車間物流的運(yùn)輸效率，本文以最小化平均運(yùn)輸總成本E{Q}為優(yōu)化目標(biāo)，包括AGV負(fù)載與空載運(yùn)行成本E{Q1}、AGV上料與下料的時(shí)間成本E{Q2}，以及AGV擁堵或繞道而產(chǎn)生的額外成本E{Q3}等。

minE{Q}=E{Q1}+E{Q2}+E{Q3}。

(1)

s.t.

E{Qi}≤ti，i=1,2,3;

(2)

Zk≤Pk，k=1,2,…,N。

(3)

其中，約束(2)為運(yùn)行過程性能指標(biāo)約束，ti表示性能指標(biāo)的上界值；約束(3)為單元P/D口位置約束，Zk表示單元k的P/D口位置向量，Pk表示單元k的可選位置集，N表示單元數(shù)。

與傳統(tǒng)的車間布局規(guī)劃問題最大的差異之處在于，這一優(yōu)化問題還將車間運(yùn)行性能指標(biāo)(如AGV的平均負(fù)載與空載運(yùn)輸時(shí)間)作為約束條件，以及將等待運(yùn)輸成本作為優(yōu)化目標(biāo)的一部分，屬于隨機(jī)整數(shù)非線性規(guī)劃模型。在考慮物料儲(chǔ)運(yùn)系統(tǒng)有限運(yùn)輸能力的車間單元P/D口布局優(yōu)化過程中，AGV的平均空載與負(fù)載運(yùn)輸成本、AGV上下料時(shí)間成本和擁堵繞道成本等主要性能無法用單元的上料與下料口位置坐標(biāo)等決策變量的封閉形式描述，這一現(xiàn)象為快速計(jì)算物料儲(chǔ)運(yùn)系統(tǒng)的性能指標(biāo)帶來了很大困難。本文通過建立車間單元P/D口布局的仿真黑箱模型，利用計(jì)算機(jī)仿真計(jì)算優(yōu)化模型中的性能指標(biāo)。

1.2 黑箱問題

由于隨機(jī)性因素的影響，在物料有限運(yùn)輸能力下，車間必然產(chǎn)生擁堵或繞道現(xiàn)象，且物流強(qiáng)度隨時(shí)間持續(xù)變化，而且在各個(gè)物流儲(chǔ)運(yùn)路段上分布得不均衡，基于穩(wěn)態(tài)的性能分析方法無法計(jì)算AGV負(fù)載與運(yùn)載成本、擁堵或繞道成本等車間性能指標(biāo)，本文采用計(jì)算機(jī)仿真的方法，把仿真模型當(dāng)作黑箱，通過輸入布局參數(shù)得到精確的車間性能指標(biāo)。仿真黑箱模型是把仿真模型內(nèi)部具體細(xì)節(jié)看作一個(gè)密閉的黑箱子，通過輸入信息后，計(jì)算機(jī)運(yùn)行仿真輸出仿真結(jié)果，其由模型控制、仿真模型和仿真統(tǒng)計(jì)三部分組成。模型控制負(fù)責(zé)控制仿真運(yùn)行過程，仿真模型負(fù)責(zé)調(diào)參和仿真，仿真統(tǒng)計(jì)則負(fù)責(zé)統(tǒng)計(jì)車間性能指標(biāo)及問題信息。利用車間仿真黑箱模型優(yōu)化P/D口位置的過程示意圖如圖2所示。

2 優(yōu)化算法

針對(duì)P/D口布局問題考慮了擁堵與繞道，但其目標(biāo)函數(shù)和約束條件無法用封閉的數(shù)學(xué)形式表示的情況，本文提出GMADS算法，該方法適用于求解目標(biāo)函數(shù)沒有導(dǎo)數(shù)信息的最小化問題，是一種局部搜索算法。在算法內(nèi)嵌入遺傳算法可以有效避免陷入局部最優(yōu)而又不影響其理論上的收斂性，而且該算法在搜索過程中利用問題信息提高其搜索效率，縮短優(yōu)化算法的搜索時(shí)間。

2.1 選擇初始解

針對(duì)特定問題選擇的初始解可以提高算法的搜索效率，本文根據(jù)單元流水式車間及多環(huán)嵌套的封閉通道路徑的問題特征，使用LHS法來獲得適應(yīng)問題特征的可行解。LHS法是一種常見的選擇輸入變量值的方法，文獻(xiàn)[24-27]對(duì)其進(jìn)行了詳細(xì)介紹，原理是將每個(gè)變量的取值區(qū)間拆分成n個(gè)相等的小區(qū)間，對(duì)每個(gè)變量來說，將整數(shù)1～n隨機(jī)地分配到每一個(gè)小區(qū)間，再通過計(jì)算得出每個(gè)變量的值。根據(jù)LHS法得到的解具有良好的散布均勻性及代表性[26-27]。通過LHS法獲取若干可行解進(jìn)行評(píng)估，獲得目標(biāo)函數(shù)值，選擇目標(biāo)函數(shù)值最小的解作為算法的初始解，稱為L(zhǎng)HS初始解。

2.2 GMADS算法

GMADS算法步驟如下：給定一個(gè)n維布局方案到目標(biāo)函數(shù)值的映射f：n∪{∞}，選定算法迭代起始點(diǎn)x0∈Ω，其中Ω為滿足變量約束的可行域，對(duì)于有變量約束的優(yōu)化問題，定義障礙函數(shù)fΩ(x)如下：

(4)

當(dāng)變量落到可行域之外時(shí)，布局方案不存在，目標(biāo)函數(shù)值設(shè)為∞。有Householder矩陣H=I-2vvT∈Rn×n，其中I為n×n維單位矩陣，ν∈n為隨機(jī)生成的n維單位向量。

步驟1初始化。

終止精度ε，迭代器k，網(wǎng)格大小參數(shù)δk，框大小參數(shù)Δk，Δk≥δk>0。

步驟2全局搜索。

(1)對(duì)于網(wǎng)格中的有限個(gè)可行解，使用嵌入遺傳算法搜索得到可行解t；

(2)若fΩ(t)

步驟3局部搜索。

(1)單位向量vk生成對(duì)應(yīng)的Householder矩陣，得到Hk=[h1h2…h(huán)n]；

(3)對(duì)于t∈Pk，若fΩ(t)

步驟4終止算法。

若Δk+1≥ε，則k←k+1，轉(zhuǎn)步驟2；否則終止算法。

2.3 嵌入遺傳算法

遺傳算法在原始種群上進(jìn)行遺傳操作，既有局部又有全局的隨機(jī)搜索能力，是一種“有限”的全局搜索算法，而MADS是一種局部搜索算法，在其內(nèi)部嵌入遺傳算法能使MADS算法尋找到局部區(qū)域內(nèi)最優(yōu)解，同時(shí)有效避免陷入局部最優(yōu)而且又能保留原有較好的基因。當(dāng)一次MADS迭代中局部搜索步驟未找到更好的可行解，經(jīng)過遺傳算法的迭代優(yōu)化可嘗試跳出局部最優(yōu)。由于MADS是在當(dāng)前解附近往各個(gè)方向搜索新解，而與當(dāng)前解所處位置無關(guān)，因此GMADS算法不影響其理論上的收斂性。嵌進(jìn)GMADS算法的遺傳算法有以下特點(diǎn)：①終止條件,只要產(chǎn)生了比當(dāng)前個(gè)體“更好”的新個(gè)體，便終止遺傳算法；②全局搜索,利用遺傳算子的全局搜索能力以避免MADS算法過快陷入局部最優(yōu)；③沿著特定的方向搜索,在GA搜索到新可行解的基礎(chǔ)上結(jié)合問題特征以及仿真信息進(jìn)行有方向的搜索，獲得可能具有問題特征的新可行解。

適應(yīng)度值為仿真獲得的目標(biāo)函數(shù)值的倒數(shù)，適應(yīng)度值越大，則解的質(zhì)量更好。遺傳算法以前一次迭代產(chǎn)生的新種群為初始種群，進(jìn)行選擇、交叉、變異等遺傳操作。由于當(dāng)前解是目前的最優(yōu)解，在遺傳操作中考慮當(dāng)前解可以加快找到新最優(yōu)解。采用部分映射交叉的交叉操作保證了個(gè)體仍在變量域內(nèi)。具體步驟如下：給定一個(gè)n維布局方案到目標(biāo)函數(shù)值的映射f：n∪{∞}，其中Ω為滿足變量約束的可行域。

步驟1初始化種群。

初始種群P，最大遺傳代數(shù)MAXGEN，交叉概率Pc，變異概率Pm。

步驟2搜索。

對(duì)于t∈P，若min(fΩ(t))

步驟3適應(yīng)度函數(shù)。

仿真得到適應(yīng)度值。

步驟4遺傳操作。

①選擇：輪盤賭選擇個(gè)體；②交叉：采用部分映射交叉分別對(duì)每對(duì)染色體進(jìn)行交叉操作；③變異：若找到新可行解，則Pm=0.5；否則Pm=0.05。

步驟4更新種群。

(1)進(jìn)行遺傳操作后的種群作為新種群P。

(2)若找到新可行解，則結(jié)束GA；否則返回步驟2。

2.4 利用問題信息

在離散車間的P/D口布局問題中，當(dāng)前解附近存在不合理布局的解時(shí)，不同的P/D口位置方案會(huì)改變車間物流強(qiáng)度分布及方向，甚至改變物料運(yùn)輸?shù)穆窂?，使得?dāng)前解附近難以找到其他更好的解。這種特點(diǎn)容易導(dǎo)致MADS陷入局部最優(yōu)，而且上述純粹的算法需要經(jīng)過多次迭代才能最終找出優(yōu)化的布局，這耗費(fèi)了過多算法時(shí)間。由于P/D口位置布局問題的特殊性，為了避免MADS算法過早陷入局部最優(yōu)，提高算法的搜索效率，可以充分利用問題本身豐富的信息來改善算法的優(yōu)化方向。

該仿真黑箱模型中有兩個(gè)方面的問題信息可輔助GMADS算法進(jìn)行優(yōu)化，一個(gè)是仿真獲取的關(guān)鍵信息，如表1所示。仿真黑箱模型包含了許多有用的信息，如AGV擁堵情況、關(guān)鍵道路的負(fù)荷情況、P/D口位置的集中程度等，特別是充分利用這類由于考慮了有限物料儲(chǔ)運(yùn)能力而導(dǎo)致AGV擁堵的信息有助于改善算法的優(yōu)化方向，使車間更合理地布局，從而更快地找到最優(yōu)解。另一個(gè)是問題特征。不同的問題有不同的問題特征，本文中問題特征指車間的生產(chǎn)組織方式、物流等特征，它具有明顯的問題屬性。對(duì)車間單元來說，各個(gè)單元布局方案都有優(yōu)先選擇或禁止選擇的值，這些值依賴車間工藝路線與路徑網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)等問題特征，具有明顯的問題屬性，滿足了各個(gè)單元的布局方案符合問題特征的要求。如在單元流水式車間中，工件沿A→B→C工藝路線加工，B單元D口應(yīng)離A單元P口更近，而B單元P口應(yīng)離A單元D口更近。這種約束對(duì)當(dāng)前解部分單元進(jìn)行調(diào)整使當(dāng)前解充分考慮問題特征，有助于改善算法的優(yōu)化方向，提高算法的效率。

表1 仿真黑箱的問題信息

利用問題信息改善算法的方向步驟如下：給定一個(gè)當(dāng)前最優(yōu)解X0={X01,X02,…,X0n}，記A={a1,a2,…,ar}為不需改變布局的單元集合，B={b1,b2,…,bs}為有固定布局的單元集合，C={c1,c2,…,ct}為由于路段擁堵、P/D口集中的路段而需要改變布局的單元，其中r+s+t=n；記lbi為單元bi的布局集合，lci為單元ci符合問題特征的可選布局集合，N為利用問題信息產(chǎn)生的新可行解數(shù)量，Xk為問題信息可行解，k≠0。

步驟1初始化。

X←?，N←0。

步驟2對(duì)于Xk，有Xk←X0。

(1)若Xki∈A，則不需改變布局；

(2)若Xki∈B，則Xki←lbi；

(3)若Xki∈C，則隨機(jī)選取lci的值，使Xki←lci；

(4)對(duì)于Xk，有可行解集合X，使得X←X∪Xk；

步驟3若|X|=N，則新可行解t″←min(fΩ(X))，否則返回步驟2。

在S步或P步找到新的最優(yōu)解后，結(jié)合新解的仿真信息和問題特征產(chǎn)生新可行解。這類可行解滿足車間布局、工藝路線等車間生產(chǎn)特點(diǎn)。對(duì)這些新可行解進(jìn)行仿真評(píng)估，從最優(yōu)解與新可行解中選取最優(yōu)的解進(jìn)入下次迭代。此步驟加入了仿真信息和問題特征，改變了MADS原來不依賴于問題特征的搜索方向，從而可能更快收斂并獲得更好的解。雖然仿真過程中處理問題信息延長(zhǎng)了單次評(píng)估的時(shí)間，但用比較小的時(shí)間代價(jià)獲得了問題的關(guān)鍵信息，減少了算法優(yōu)化過程中評(píng)估性能指標(biāo)的次數(shù)，極大地縮短了優(yōu)化算法的總耗時(shí)。利用問題信息改善算法優(yōu)化方向的GMADS算法流程圖如圖3所示。

3 算例驗(yàn)證與結(jié)果分析

3.1 算例設(shè)計(jì)

本節(jié)以典型的單元流水式車間為測(cè)試案例，單元流水車間內(nèi)包含若干塊狀區(qū)域，每個(gè)塊狀區(qū)域代表某道加工工序，每道工序有若干并行加工單元，各單元分別有一個(gè)P口和D口。這種情況下，一個(gè)車間布局方案由一串字符串組成，每個(gè)字符代表對(duì)應(yīng)單元的布局方案。各個(gè)單元P/D口的布局方案有2～12種不等，采用十六進(jìn)制編碼給每種P/D口布局編號(hào)1,2,3,…,9,A,B,C。根據(jù)各單元所處位置道路的情況，各單元有若干種可選的布局編號(hào)。針對(duì)該單元流水式車間設(shè)計(jì)一系列實(shí)驗(yàn)，考慮車間塊狀數(shù)分別為4塊和5塊、各個(gè)塊內(nèi)的單元數(shù)分別為(2,3,4,4)和(3,3,3,3)、(3,2,2,4,3)和(3,3,3,2,4)的情況，測(cè)試算法的性能，驗(yàn)證所提算法在解決車間單元P/D口位置布局問題中利用問題信息對(duì)提高算法效率的有效性及在性能與效率上的優(yōu)越性。

3.2 對(duì)比算法的選取

本文選取GA和GMADS算法作為對(duì)比算法，分別進(jìn)行無利用問題信息(GA-Ⅰ和GMADS-Ⅰ)和有利用問題信息(GA-Ⅱ和GMADS-Ⅱ)的實(shí)驗(yàn)。為了驗(yàn)證所提算法在時(shí)間和優(yōu)度上的優(yōu)勢(shì)，增加GA-Ⅲ算法實(shí)驗(yàn)，其終止條件為仿真總次數(shù)達(dá)到GMADS-Ⅱ的次數(shù)，對(duì)比當(dāng)GA與GMADS算法時(shí)間接近時(shí)兩者解的質(zhì)量。對(duì)比算法的內(nèi)容和說明、算法參數(shù)設(shè)置和對(duì)比算法的關(guān)系矩陣表分別如表2～表4所示。此外，為增加結(jié)果優(yōu)勢(shì)的可信度，還選取了3種文獻(xiàn)中常見的經(jīng)典算法[17-19]進(jìn)行對(duì)比。

表2 對(duì)比算法

表3 算法參數(shù)設(shè)置

表4 對(duì)比算法關(guān)系矩陣圖

3.3 結(jié)果及分析

根據(jù)參數(shù)配置和對(duì)比算法，總共進(jìn)行128次算法實(shí)驗(yàn)。實(shí)驗(yàn)在MATLAB R2018b上進(jìn)行編程實(shí)現(xiàn)，在Plant Simulation 12.1上建立仿真黑箱模型，PC配置為Intel(R)Core(TM)i7-8700 CPU @ 3.20 GHz，16.0 GB RAM。算法均支持并行仿真評(píng)估布局方案，可同時(shí)評(píng)估最多8個(gè)布局方案，每個(gè)方案仿真180天。通過TCP/IP協(xié)議實(shí)現(xiàn)MATLAB與Plant Simulation的數(shù)據(jù)傳輸，包括P/D口布局參數(shù)、目標(biāo)函數(shù)值及其他數(shù)據(jù)等。實(shí)驗(yàn)結(jié)果如表5所示，分別表示在各參數(shù)配置下，按照8個(gè)對(duì)比算法進(jìn)行實(shí)驗(yàn)獲得的平均總運(yùn)輸成本、算法運(yùn)行時(shí)間、單次仿真平均用時(shí)與仿真評(píng)估次數(shù)。為了直觀地反映實(shí)驗(yàn)結(jié)果，將實(shí)驗(yàn)結(jié)果繪制成如圖4所示的折線圖，其中GMADS-Ⅰ、GMADS-Ⅱ分別用G-I、G-Ⅱ表示。

表5 對(duì)比算法的實(shí)例性能指標(biāo)值

結(jié)合圖4a和圖4b可以看出，對(duì)比算法收斂過快，容易陷入局部最優(yōu)，且獲得的解質(zhì)量不高，即使GA-Ⅱ利用了問題信息也無法使其跳出局部最優(yōu)，反而使算法收斂變慢而且解的質(zhì)量沒有改善甚至變差。同樣沒有利用問題信息，GMADS-Ⅰ的算法時(shí)間相比GA-Ⅰ、SA算法明顯變長(zhǎng)，解的質(zhì)量明顯提高，這是因?yàn)镚MADS-Ⅰ算法有效避免了陷入局部最優(yōu)并且提高了解的質(zhì)量，而由于變量域太大，導(dǎo)致算法的時(shí)間代價(jià)過大。GMADS-Ⅱ利用了問題信息，限制了變量域范圍，不僅相對(duì)GA算法提高了質(zhì)量，還加快了算法的收斂速度，說明算法時(shí)間在一定程度上受問題信息的影響。同樣利用了問題信息，GMADS-Ⅱ算法總耗時(shí)比GA-Ⅱ長(zhǎng)，是由于GA-Ⅱ算法總耗時(shí)受算法終止條件影響，GA-Ⅲ修改了算法終止條件，使之算法耗時(shí)大致相同，結(jié)果說明在近似的算法運(yùn)行時(shí)間內(nèi)GA由于陷入了局部最優(yōu)，其解的質(zhì)量無法達(dá)到GMADS算法的水平。

在仿真過程中，計(jì)算擁堵率、負(fù)荷率等問題關(guān)鍵信息占用了計(jì)算資源而產(chǎn)生了額外時(shí)間，但由于不同布局方案的仿真耗時(shí)稍有差異，因此如圖4c所示，利用了問題信息的仿真實(shí)驗(yàn)平均用時(shí)與不利用問題信息的實(shí)驗(yàn)相比無顯著差別，但前者大大縮短了算法時(shí)間。結(jié)果表明，利用問題信息能夠用比較小的時(shí)間代價(jià)來獲得問題的關(guān)鍵信息，減少了算法在優(yōu)化過程中評(píng)估性能指標(biāo)的次數(shù)，極大地提高算法的效率。綜上分析，本文所提的利用問題信息的GMADS-Ⅱ算法在時(shí)間和優(yōu)度上均有著明顯的優(yōu)勢(shì)。

上述分析比較了同一參數(shù)配置下各算法的性能，驗(yàn)證了所提算法的有效性與優(yōu)越性，但由于不同參數(shù)配置下的實(shí)驗(yàn)結(jié)果相差較大，難以評(píng)價(jià)同一算法在不同實(shí)驗(yàn)參數(shù)配置下的性能穩(wěn)定性，為了從整體上統(tǒng)一評(píng)價(jià)各個(gè)算法在P/D口位置布局問題上的性能，繪制了算法性能指數(shù)散點(diǎn)圖。如圖5所示，分別以平均總運(yùn)輸成本和算法時(shí)間為橫、縱坐標(biāo)，以每一個(gè)參數(shù)配置下5個(gè)算法實(shí)驗(yàn)結(jié)果的上、下界為標(biāo)準(zhǔn)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)分，并且從低到高繪制在算法性能指數(shù)散點(diǎn)圖上，可以直觀地對(duì)比評(píng)價(jià)每個(gè)算法的性能及其穩(wěn)定性。平均總運(yùn)輸成本越高，則評(píng)分越高，在散點(diǎn)圖上越遠(yuǎn)離原點(diǎn)，算法時(shí)間亦然。

整體上看，GMADS算法獲得的解質(zhì)量高于其他對(duì)比算法，而且對(duì)于同一類算法，利用了問題信息的算法更快獲得解的同時(shí)保持解的質(zhì)量。值得注意的是，不管是否利用問題信息，GA解的質(zhì)量與算法時(shí)間變化不大，這是因?yàn)镚A容易陷入局部最優(yōu)且速度極快，利用問題信息對(duì)其收斂速度影響有限。圖5再一次驗(yàn)證了GMADS-Ⅱ算法在速度與優(yōu)度上的優(yōu)越性，并且在解決含多環(huán)嵌套封閉環(huán)形的P/D口布局問題上具有穩(wěn)定性。

4 案例分析

本章以某離散制造企業(yè)中一個(gè)流水式生產(chǎn)車間為研究案例，該生產(chǎn)車間有5個(gè)功能區(qū)塊，對(duì)應(yīng)為鍛造、壓鑄、粗加工、精加工和裝配調(diào)試等5道工序，圖6中分別用①～⑤標(biāo)記。每個(gè)區(qū)塊內(nèi)由多個(gè)含機(jī)器人的柔性制造單元所組成，車間內(nèi)的物料大致沿著相同的方向由AGV在單元間進(jìn)行運(yùn)輸。由于AGV運(yùn)輸能力有限以及生產(chǎn)過程的隨機(jī)性，AGV頻繁發(fā)生擁堵，導(dǎo)致AGV系統(tǒng)效率較低，利用所提GMADS-Ⅱ算法對(duì)車間內(nèi)各單元的P/D口位置進(jìn)行優(yōu)化，以提高物料儲(chǔ)運(yùn)系統(tǒng)的運(yùn)輸效率。實(shí)際智能車間的系統(tǒng)參數(shù)如表6所示。

表6 實(shí)際智能車間的系統(tǒng)參數(shù)

系統(tǒng)參數(shù)參數(shù)值P/D口最大容量2各區(qū)塊單元數(shù)(4,3,2,2,2)各工序中單元加工速率(240 s,180 s,120 s,120 s,120 s)托盤數(shù)量15AGV速度2 m/sAGV數(shù)量5AGV上下料時(shí)間10 sAGV容量1

如圖7所示為利用GMADS-Ⅱ算法在優(yōu)化研究案例過程中的每次迭代的歷史最優(yōu)目標(biāo)函數(shù)值曲線，可以知道平均運(yùn)輸總成本為13.11 h/d。優(yōu)化過程中目標(biāo)函數(shù)值迅速下降，這是因?yàn)槔昧酥悄苘囬g的問題信息使算法快速地搜索到更好的解，提高了解的質(zhì)量。利用所提算法得到該案例的目標(biāo)函數(shù)值、仿真優(yōu)化耗時(shí)、單次仿真平均時(shí)長(zhǎng)、仿真評(píng)估次數(shù)等指標(biāo)如表7所示，圖8為本案例優(yōu)化后的智能車間單元P/D口位置方案。

表7 研究案例的優(yōu)化結(jié)果

指標(biāo)結(jié)果平均運(yùn)輸總成本/(h/d)13.11仿真優(yōu)化耗時(shí)/h28.33單次仿真平均時(shí)長(zhǎng)/min16.8仿真評(píng)估次數(shù)/次98

下面以生產(chǎn)實(shí)際中的單元流水式智能車間單元P/D口的布局優(yōu)化問題為應(yīng)用場(chǎng)景，驗(yàn)證所提算法在實(shí)踐中的應(yīng)用，凸顯其實(shí)際應(yīng)用價(jià)值。由于系統(tǒng)性能指標(biāo)采用仿真方法計(jì)算，雖然使得優(yōu)化算法的用時(shí)較長(zhǎng)，但獲得了較為精確的結(jié)果。

5 結(jié)束語

本文針對(duì)多環(huán)嵌套封閉環(huán)形路徑、多工序的單元流水式智能車間單元P/D口的位置布局問題，建立整數(shù)非線性規(guī)劃模型?；诜抡婧谙淠Ｐ?，采用嵌入遺傳算法的MADS無導(dǎo)數(shù)優(yōu)化算法求解，結(jié)合智能車間的問題特征，優(yōu)化P/D口位置布局。以一典型的單元流水式車間為例，設(shè)計(jì)若干組仿真優(yōu)化實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果說明利用問題特征信息，用比較小的時(shí)間代價(jià)來獲得問題的關(guān)鍵信息，能夠極大地縮短優(yōu)化算法的搜索時(shí)間，提高解的質(zhì)量，從而驗(yàn)證了算法的有效性和優(yōu)越性。最后結(jié)合實(shí)際智能車間單元P/D口的布局優(yōu)化問題說明其具有實(shí)際應(yīng)用價(jià)值。

車間生產(chǎn)組織方式只在黑箱內(nèi)體現(xiàn)，不影響MADS優(yōu)化算法的求解，因此本方法也適用于作業(yè)車間的單元上下料口布局優(yōu)化，但是也有其局限性。由于作業(yè)車間產(chǎn)品工序多且繁雜，導(dǎo)致其問題特征比較復(fù)雜，這給結(jié)合問題信息改善搜索方向帶來了困難。使用仿真實(shí)驗(yàn)方法評(píng)估目標(biāo)函數(shù)值，精確性高但速度慢、效率低，為了提高優(yōu)化速度，后續(xù)研究將在優(yōu)化算法中采用排隊(duì)網(wǎng)建模和近似求解物料儲(chǔ)運(yùn)系統(tǒng)的性能指標(biāo)，并將優(yōu)化結(jié)果作為仿真優(yōu)化的初始解，進(jìn)行優(yōu)化后得到精確的解。本文的研究成果可用于解決在有限物料儲(chǔ)運(yùn)能力條件下的車間P/D口隨機(jī)布局優(yōu)化問題，有助于離散定制生產(chǎn)型智能車間和單元的布局優(yōu)化建模與求解，為我國智能制造系統(tǒng)的設(shè)計(jì)與規(guī)劃理論提供有效的方法。