盧義楨 李西興 朱傳軍 吳 銳

（①廣東工業(yè)大學(xué)管理學(xué)院，廣東 廣州 510000；②湖北工業(yè)大學(xué)現(xiàn)代制造質(zhì)量工程湖北省重點(diǎn)實(shí)驗室，湖北 武漢 430068）

車間設(shè)施布局問題是智能制造精益生產(chǎn)中面臨復(fù)雜問題之一，其實(shí)質(zhì)是一種非線性組合優(yōu)化問題，需要尋求合理高效的車間設(shè)施布局方案來提高車間空間利用率，降低車間物流成本，提高生產(chǎn)效率。車間設(shè)施布局是否合理對整個生產(chǎn)系統(tǒng)的總體性能有著重要的影響。

當(dāng)前車間布局優(yōu)化問題主要利用智能優(yōu)化算法進(jìn)行求解。國內(nèi)研究中，謝潔明等[1]提出了基于仿真的遺傳網(wǎng)格自適應(yīng)直接搜索算法（GMADS）用于求解具有單向?qū)蚵窂骄W(wǎng)絡(luò)、多重嵌套封閉環(huán)形物料儲運(yùn)系統(tǒng)的布局優(yōu)化問題。郭源源等[2]采用粒子群算法求解二維設(shè)施布局問題并將粒子群算法與SLP法進(jìn)行結(jié)合，提高了初始解的合理性和尋優(yōu)過程的高效性。陳勇等[3]為滿足低成本、高穩(wěn)健性的車間布局要求，設(shè)計了以單位面積布置成本、單位產(chǎn)品物流成本和布局熵為優(yōu)化目標(biāo)的車間布局優(yōu)化模型，提出了基于Pareto優(yōu)化的聚類并行多目標(biāo)遺傳算法。國外學(xué)者對應(yīng)用智能算法求解布局問題也有諸多研究，F(xiàn)rederico Galaxe Paes等[4]通過引入經(jīng)分解策略改進(jìn)后的遺傳算法解決不平等區(qū)域設(shè)施布局問題（UA-FLP）時，尋優(yōu)表現(xiàn)優(yōu)于普通遺傳算法。Jose Fernando Goncalves等[5]針對不平等區(qū)域設(shè)施布局問題提出了偏向性的隨機(jī)關(guān)鍵遺傳算法（BRKGA）確定設(shè)施布局方案。

在車間設(shè)施布局優(yōu)化研究中，多將車間不同作業(yè)單元間搬運(yùn)距離總和作為優(yōu)化目標(biāo)[6?7]，而沒有考慮到實(shí)際生產(chǎn)中不同作業(yè)單元之間物料搬運(yùn)方式可能存在差異的情況針對該問題，本文考慮不同作業(yè)單元之間物料搬運(yùn)方式不同的情況，以最小車間物流成本與最短車間搬運(yùn)時間為優(yōu)化目標(biāo)，采用自適應(yīng)遺傳模擬退火算法對車間設(shè)施布局問題進(jìn)行求解，并通過實(shí)例分析驗證了模型和算法的有效性。

1 問題描述

在制造車間中，零件按各自批量和工藝流程依次經(jīng)過不同的作業(yè)單元完成加工過程。在這個過程中，不同的車間設(shè)施布局方案會對物料搬運(yùn)過程的時間、成本等指標(biāo)產(chǎn)生影響，需要建立數(shù)學(xué)模型，通過運(yùn)算求解出一套較優(yōu)的布局方案以滿足降低生產(chǎn)成本、提高生產(chǎn)效率的要求。

1.1 問題假設(shè)

（1）假設(shè)各作業(yè)單元形狀均為標(biāo)準(zhǔn)矩形，長和寬均已知。

（2）假設(shè)各作業(yè)單元均為橫平豎直，作業(yè)單元的邊界分別平行于車間四周邊界。

（3）假設(shè)物料是從一個作業(yè)單元的幾何中心搬運(yùn)到下一個作業(yè)單元的幾何中心。

（4）假設(shè)物料搬運(yùn)的路徑平行于車間邊界的直線。

（5）假設(shè)不同作業(yè)單元之間物料搬運(yùn)速度不同且均已知。

基于以上假設(shè)，建立車間設(shè)施布局示意圖如圖1所示。

圖1 車間設(shè)施布局

在圖1中，X軸為車間的長度方向；Y軸為作業(yè)車間的寬度方向；mi為車間第i個作業(yè)單元，i=1,2,···,N（N為車間作業(yè)單元總數(shù)）；L為作業(yè)車間總長度；W為作業(yè)車間總寬度；li、wi分別為車間i作業(yè)單元的長度、寬度；xi、yi分別為i作業(yè)單元幾何中心點(diǎn)的橫坐標(biāo)、縱坐標(biāo)；sij為i作業(yè)單元與j作業(yè)單元邊界之間的凈間距[8]。

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

本文同時考慮車間物流成本最小與車間搬運(yùn)時間最短兩個目標(biāo)進(jìn)行建模，目標(biāo)函數(shù)表達(dá)式如下所示。

式中：G1為第一個優(yōu)化目標(biāo)車間物流成本；G2為第二個優(yōu)化目標(biāo)車間搬運(yùn)時間；Pij為i作業(yè)單元與j作業(yè)單元之間單次物料搬運(yùn)單位距離的費(fèi)用；Dij為i作業(yè)單元與j作業(yè)單元幾何中心點(diǎn)之間的曼哈頓距離；Fij為i作業(yè)單元與j作業(yè)單元之間物料搬運(yùn)頻率；Vij為i作業(yè)單元與j作業(yè)單元之間物料搬運(yùn)速度。當(dāng)i=j時，Pij、Fij、Vij=0。

采用歸一化因子u1、u2來統(tǒng)一量綱[9]，u1、u2的計算如式（3）、式（4）所示?？紤]到實(shí)際生產(chǎn)中對多個優(yōu)化目標(biāo)的側(cè)重不同，加入加權(quán)因子w1、w2，且滿足w1+w2=1(w1、w2∈(0,1))，最終得到目標(biāo)函數(shù)表達(dá)式如式（5）所示。

式中：G為加權(quán)后的目標(biāo)函數(shù)值；Dmax為兩作業(yè)單元間可能存在的最大曼哈頓距離，近似為車間的長和寬之和；v′ij為車間所有路徑上物料搬運(yùn)速度的平均值。

1.3 約束條件

在對車間不同作業(yè)單元的布局進(jìn)行建模優(yōu)化時，還需要結(jié)合實(shí)際情況建立約束條件，主要包括以下內(nèi)容。

（1）間距約束。不同作業(yè)單元之間需要保持一定的距離，即

（2）通道約束。各作業(yè)單元之間與車間墻壁之間需要保留一定的距離，即

（3）尺寸約束。同一行或同一列的所有作業(yè)單元在在X軸或Y軸方向上的布局不得超過車間的長度或?qū)挾?，?/p>

式中：s為 最小間距。

2 自適應(yīng)遺傳模擬退火算法

為了對上述模型進(jìn)行求解，提出一種自適應(yīng)遺傳模擬退火算法，即在傳統(tǒng)遺傳算法上對交叉變異算子采用自適應(yīng)調(diào)整策略；同時利用模擬退火算法的概率突跳性來降低過早收斂的可能性，進(jìn)一步增強(qiáng)算法求解性能并基于Metropolis準(zhǔn)則判斷是否接受新個體。算法流程如圖2所示。

圖2 算法計算流程

2.1 種群初始化

本文采用實(shí)數(shù)編碼的方式構(gòu)建個體的基因序列，編碼樣式為[m1,m2,m3,m4,···,mN]，代表的含義是自車間區(qū)域自左下角依次沿X軸正方向布置作業(yè)單元，當(dāng)布置的作業(yè)單元總長度超出車間長度時，沿Y軸正方向另起一行，從最左端繼續(xù)向右依次布置，例如個體編碼[2,7,3,10,1,4,5,···]的布局即圖3所示。

圖3 編碼示例對應(yīng)的車間布局圖

2.2 適應(yīng)度函數(shù)

本文中綜合優(yōu)化目標(biāo)是求最小值，設(shè)置適應(yīng)度函數(shù)fi為

式中：G為目標(biāo)函數(shù)；P為懲罰函數(shù)。懲罰函數(shù)定義為

2.3 選擇算子

為保證種群基因多樣性并且同時提高算法的收斂效率，本文選擇輪盤賭加部分精英保留的策略進(jìn)行選擇操作。輪盤賭策略中，個體i被選中的概率Pi為

式中：popsize為種群大??；fi為第i個個體的適應(yīng)度值。

采用輪盤賭的方式選出下一代種群中一半的個體后，采用部分精英保留策略選出另一半的個體，選出的所有個體組合成子代種群。

2.4 交叉算子

由于車間布局問題中個體基因型的代碼具有特殊含義，因此本文采用基于位置的交叉算子，其具體操作如圖4所示。

圖4 交叉過程

2.5 變異操作

在實(shí)數(shù)編碼下，基因序列上的每一個數(shù)字都具有特殊的含義，無法采用二進(jìn)制編碼下的各種變異方法。針對本問題，為了保證變異之后的個體仍具有意義，采用互換變異的方式進(jìn)行操作，如圖5所示。

圖5 變異過程

2.6 自適應(yīng)交叉、變異策略

遺傳算法中，交叉概率Pc和變異概率Pm是影響算法尋優(yōu)能力的重要參數(shù)，由于自適應(yīng)取值法對交叉、變異算子進(jìn)行非線性設(shè)計，使得交叉概率與變異概率隨種群中個體的適應(yīng)度值的變化而變化，能夠防止算法陷入過早收斂[10]，因此本文對Pc、Pm的取值采用自適應(yīng)取值法，取值計算過程如式（15）、式（16）所示。

式中：Pcmax與Pcmin分別為遺傳操作過程中交叉概率取值區(qū)間的上、下限，f′為進(jìn)行交叉操作兩個個體中較大者的適應(yīng)度值，favg為每代種群的平均適應(yīng)度值，fmax為當(dāng)前種群中的最大適應(yīng)度值，λ為常數(shù)。

式中：Pmmax、Pmmin為變異概率取值區(qū)間的上、下限，f為變異個體的適應(yīng)度值，favg為每代種群的平均適應(yīng)度值，fmax為當(dāng)前種群中的最大適應(yīng)度值。

2.7 嵌入模擬退火算法

在遺傳算法中嵌入模擬退火算法，借用模擬退火算法的概率突跳性增強(qiáng)算法全局尋優(yōu)的能力。設(shè)定初始溫度t作為模擬退火尋優(yōu)的起始點(diǎn)，設(shè)定終止溫度Tend作為模擬退火尋優(yōu)的終止點(diǎn)，在等溫狀態(tài)下交換個體前后一半基因并依據(jù)Metropolis準(zhǔn)則計算新個體被接受的概率，其計算公式如下

式中：Ps為新個體接受的概率；fi(t)為個體變換前的適應(yīng)度值；fj(t)為個體變化后的適應(yīng)度值；t為當(dāng)前溫度。依據(jù)式（14）更新當(dāng)前溫度，即

式中：λ為溫度衰減參數(shù)，用于控制退火速度，且取值大小滿足λ∈(0，1)。

3 計算實(shí)例

3.1 車間概述

FK公司是一家主要從事汽車零部件設(shè)計和制造的公司，該公司生產(chǎn)車間為30 m×25 m的矩形，車間內(nèi)有11套各式加工機(jī)床以及原材料、成品存放區(qū)。為方便描述，用序號表示各作業(yè)單元，各作業(yè)單元的尺寸數(shù)據(jù)見表1，車間的原始布局如圖6所示。

圖6 車間原始布局

根據(jù)產(chǎn)品的工藝流程以及不同作業(yè)單元間物料搬運(yùn)方式的差異，作業(yè)單元間的單位費(fèi)用如表2所示，作業(yè)單元間的搬運(yùn)頻率如表3所示，作業(yè)單元間的搬運(yùn)速度如表4所示。

3.2 優(yōu)化過程及相關(guān)參數(shù)設(shè)定

設(shè)定最小間隔參數(shù)s為1 m。由表2、表3、表4的數(shù)據(jù)，計算出歸一化因子u1=4.905×10?6、u2=5.646×10?5。根據(jù)對優(yōu)化目標(biāo)的側(cè)重不同，設(shè)定權(quán)重因子w1=0.6，w2=0.4。種群數(shù)量設(shè)定為50，迭代次數(shù)gen為500代，保證算法充分進(jìn)行尋優(yōu)搜索。為驗證不同算法的設(shè)計以及不同參數(shù)的選取對算法尋優(yōu)的影響，引入4種不同的方案進(jìn)行對比，具體如表5所示。

表2 作業(yè)單元間的單位費(fèi)用 元/m

表3 作業(yè)單元間的搬運(yùn)頻率 次/天

表4 作業(yè)單元間的搬運(yùn)速度 m/s

表5 算法參數(shù)設(shè)定對比

3.3 優(yōu)化結(jié)果及分析

在MATLAB軟件上運(yùn)行各套算法對車間布局問題進(jìn)行求解，運(yùn)行結(jié)果如圖7所示。從圖7可以看出，各算法在迭代一定代數(shù)之后停止了波動，達(dá)到收斂。經(jīng)計算，方案1至方案3求解得到的最優(yōu)目標(biāo)函數(shù)值分別為0.180、0.175、0.169，本文提出的自適應(yīng)的遺傳模擬退火算法求解得到的最優(yōu)目標(biāo)函數(shù)值為0.158，比普通遺傳算法尋優(yōu)結(jié)果更優(yōu)秀，由本文算法求解得到的最優(yōu)個體為[5,13,10,1,11,4,3,6,2,8,9,7,12]，其車間作業(yè)單元布局如圖8所示，各作業(yè)單元的位置坐標(biāo)如表6所示。

表6 優(yōu)化后作業(yè)單元位置坐標(biāo)

圖7 算法優(yōu)化過程迭代圖

圖8 優(yōu)化后車間作業(yè)單元布局

為了評估優(yōu)化效果，將原布局與優(yōu)化后的布局下的搬運(yùn)費(fèi)用及搬運(yùn)時間進(jìn)行對比，如表7所示，對比發(fā)現(xiàn)優(yōu)化效果顯著。

表7 優(yōu)化前后對比

4 結(jié)語

針對車間設(shè)施布局優(yōu)化問題，本文以最低車間物流成本與最短車間搬運(yùn)時間為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，采用自適應(yīng)遺傳模擬退火算法對問題進(jìn)行求解，并通過4種參數(shù)設(shè)定方案對比驗證了自適應(yīng)策略的算法的優(yōu)越性。給出了FK公司的車間設(shè)施布局優(yōu)化案例，結(jié)果表明，經(jīng)遺傳模擬退火算法優(yōu)化后得到的車間布局方案，相較于原始布局方案，其車間物流成本降低了9.98%，車間搬運(yùn)時間縮短了20.8%，證明該算法有較強(qiáng)的尋優(yōu)能力，可以為企業(yè)車間生產(chǎn)制造減少浪費(fèi)，提高效率。

在后續(xù)工作中，還需要繼續(xù)結(jié)合其他算法的思路對算法進(jìn)行改進(jìn)，同時車間布局?jǐn)?shù)學(xué)模型的復(fù)雜度需結(jié)合實(shí)際情況作進(jìn)一步的完善。