王亞良 錢其晶 曹海濤 金壽松

浙江工業(yè)大學機械工程學院，杭州，310014

0 引言

TOMPKINS等［1］指出企業(yè)物料搬運成本占制造成本的20%～50%。對企業(yè)物流系統(tǒng)研究領域重要程度的評價調查表明，車間布局設計位居第一位，其次是車間物流調度與績效評價、企業(yè)物流戰(zhàn)略、企業(yè)物流網絡重構及環(huán)境，合理的車間布局能降低10%～30%的制造成本［2?3］。

車間布局問題是NP?hard問題，隨著設施數量的增加，傳統(tǒng)的最優(yōu)化算法（如線性規(guī)劃、整數規(guī)劃和分支定界法等）尋求精確解的可行性很低，智能優(yōu)化算法能夠在有效時間內尋求問題的近似最優(yōu)解。LEE等［4］用遺傳算法解決多層車間布局問題。鄭永前等［5］用協同粒子群算法進行單元布局多目標優(yōu)化。牛占文等［6］應用遺傳算法對雙行車間進行多目標布局改善優(yōu)化，以物料搬運成本、設備單元移動成本、生產效率為優(yōu)化目標，建立的模型更加貼近實際生產狀況。為了避免動態(tài)環(huán)境下頻繁進行車間布局，降低車間運行成本，劉瓊等［7］建立了以車間物料搬運費用和面積費用最小化為目標的多目標魯棒性布局優(yōu)化模型，并用改進的蛙跳算法求解該模型。馬淑梅等［8］采用模糊理論描述產品的不確定性，在遺傳算法中引入局部自適應機制，對多行設備進行動態(tài)布局優(yōu)化。上述學者都采用將多個分目標加權轉化成為一個綜合目標的研究思路。李愛平等［9］建立了物流搬運費用、非物流關系以及面積利用率的車間多目標模型，并采用非支配排序遺傳算法（NSGA?Ⅱ）對模型進行求解。張屹等［10］利用差分元胞多目標遺傳算法（DECell）對多行車間布局進行優(yōu)化，并與其他算法進行了比較分析，取得了較好的結果。黃君政等［11］對多個計劃期內需求可預測的車間動態(tài)設備布局問題進行研究，采用NSGA?Ⅱ對建立的多行車間布局模型進行多目標優(yōu)化。左興權等［12］針對雙行設備布局既具有組合方面（設備排序）又含有連續(xù)方面（設備精確位置）的特點，將多目標免疫算法（MIA）和線型規(guī)劃方法結合起來，為獲取雙行設備布局非支配解集提供新方法。SARAS?WAT等［13］在傳統(tǒng)布局目標的基礎上，增加了平均在制品庫存量這個新目標，用模擬退火算法對塊布局問題進行多目標優(yōu)化。SEIFBARGHY等［14］考慮不同搬運設備對物料搬運的影響，提出一種用于動態(tài)設備布局的多目標水流算法。

求解車間布局模型大多采用遺傳算法［4,15］、粒子群算法［5,16］、差分進化算法［10］、混合算法［17］以及多目標轉化成單目標算法，但在求解布局多目標優(yōu)化特別是混合作業(yè)車間布局問題時還存在不足，其求解質量有待進一步提升。本文對混合作業(yè)車間布局的原型特征進行分析和研究，重點描述車間場地的制約性、混合生產方式的協同性、作業(yè)單元類型的多樣性、物流路徑及搬運費用的集約性及非物流關系等原型細節(jié)，建立混合作業(yè)車間多目標布局模型，并用提出的動態(tài)差分元胞多目標遺傳算法對其進行優(yōu)化。

1 多目標混合作業(yè)車間布局模型

1.1 多目標函數

布局時，假設車間和作業(yè)單元均為矩形結構，車間大小和作業(yè)單元大小均已知，混合作業(yè)車間布局如圖1所示。車間的長度為a，寬度為b；作業(yè)單元i的長度為Li，寬度為Wi；作業(yè)單元水平方向（沿x軸方向）的最小間距為hmin，垂直方向（沿y軸方向）的最小間距為vmin。

圖1 大型混合作業(yè)車間布局示意圖Fig.1 Schematic diagram of the large hybrid workshop layout

1.1.1 物料搬運成本最小

大型混合作業(yè)車間生產的產品多、工藝路線復雜且交叉頻繁，須根據不同產品組合選擇合理的生產工藝路線以減少物料搬運成本：

式中，n為布局的作業(yè)單元數目；cij為綜合考慮物料大小、搬運工具和搬運載荷等因素的作業(yè)單元i到作業(yè)單元j的單位物料搬運成本；fij為作業(yè)單元i到作業(yè)單元j的總物料搬運件數；dij為作業(yè)單元i到作業(yè)單元j的物料搬運距離。

1.1.2 作業(yè)單元移動成本最小

針對不同的生產需求，部分作業(yè)單元將重排組合，其函數表達式為

式中，dio為作業(yè)單元i前后移動的曼哈頓距離（天車搬運為主）；mi為作業(yè)單元i的移動成本。

1.1.3 作業(yè)單元包絡矩形面積最小

作業(yè)單元包絡矩形面積函數表達式為式中，L為包絡所有作業(yè)單元矩形的長度；W為包絡所有作業(yè)單元矩形的寬度。

1.1.4 作業(yè)單元非物流關系最大化［4］

最大化優(yōu)化目標可以轉換成最小化優(yōu)化目標，故

其中，Z為一個較大的數，保證F4為正數即可；aij為作業(yè)單元間的非物流關系鄰接度，如表1所示；bij為作業(yè)單元間的非物流關系鄰接度因子，如表2所示；dij_max為兩個作業(yè)單元間的最大曼哈頓距離。

表1 作業(yè)單元間的非物流關系鄰接度值Tab.1 Non”logistic relationship between units

表2 作業(yè)單元間的非物流關系鄰接度因子Tab.2 Non”logistics relationship adjacency factor between units

因為第1個和第2個優(yōu)化目標單位一致，因此，上述4個目標可以最終轉化為3個優(yōu)化目標：

1.2 約束條件

多目標混合作業(yè)車間布局模型約束主要為間距約束、邊界約束和特定約束。間距約束要求任意兩作業(yè)單元之間保留一定的間距。邊界約束要求任何作業(yè)單元必須在車間內。對于某些特殊作業(yè)單元，布局時要考慮其特殊要求，即特定約束。

（1）間距約束。任意2個作業(yè)單元在水平方向（x方向）的間距應不小于hmin或在垂直方向（y方向）的間距應不小于vmin，則應滿足： ||xi-xj≥

（2）邊界約束。各個作業(yè)單元在車間布局時，不能超出車間，其邊界約束為

（3）特定約束。指混合作業(yè)車間中的特殊作業(yè)單元需滿足的一些特定條件，本文的布局實例中，噴漆單元作為特殊作業(yè)單元，須靠近通風處?？紤]現有硬件設施，在布局時對噴漆單元進行預置。噴漆單元的預定位置

式中，(xs,ys)為噴酒保單元預置位置的坐標。

1.3 作業(yè)單元間的距離

在車間布局中，常采用曼哈頓距離來表示作業(yè)單元與作業(yè)單元之間的物料搬運距離。當2個作業(yè)單元之間無其他障礙單元時，采用曼哈頓距離來表示2個作業(yè)單元之間的物料搬運距離比較符合實際情況，曼哈頓距離的計算公式如下：

當作業(yè)單元之間有其他作業(yè)單元擋道時，用曼哈頓距離來衡量單元之間的物料搬運距離，會使得優(yōu)化模型與實際情況的出入較大。為此，對曼哈頓距離進行修正。

如圖2所示，作業(yè)單元i與作業(yè)單元j之間存在著曼哈頓距離，作業(yè)單元k是物料搬運路線上的障礙物，障礙物的數學表達式如下：

圖2 作業(yè)單元之間有障礙情況Fig.2 Situation of obstacles between unit

為了繞開這些障礙物，在原先曼哈頓距離路線的基礎上提取出4條新路線，并選取距離最短的路線來代替原先的物料搬運路線，修正公式如下：

2 動態(tài)差分元胞多目標遺傳算法設計

差分進化算法有多種變異方式，其中，差分元胞多目標遺傳算法DECell的變異、交叉操作為

式中，vi[j]為父本向量xr1經過變異后得到的變異向量；xr1[j]、xr2[j]、xr3[j]為 3個第 j維決策變量的父本向量；r1、r2、r3為三個父本的索引位置；F為縮放因子；N為種群規(guī)模；d為解空間的維數。

交叉操作后獲得的向量

式中，Ri[j]為個體i的第j維決策變量在交叉操作過程中產生［0,1］之間均勻分布的隨機數；CR為介于［0,1］間的交叉常量。

連續(xù)型車間布局模型中，布局的解有無窮多個，一旦某個解占優(yōu)，則算法容易陷入局部最優(yōu)。當算法獲得的所有解陷入局部最優(yōu)時，xr2［j］-xr3［j］趨于零。式（13）的變異方式不利于算法跳出局部最優(yōu)［18?19］，導致算法無法進一步獲得更好的布局方案，故當|xr2［j］-xr3［j］|小于某個值時，采用新的變異操作：

其中，R（1）為［0,1］之間均勻分布的隨機數；S為變異步長，S=z（xr1[j]-u-xr1[j]-l）；xr1[j]-u、xr1[j]-l分別為父本向量xr1第j維決策變量的最大值與最小值；z為控制變異步長大小的系數，z較小，算法不易跳出局部最優(yōu)；z較大，算法的收斂精度就差，這里取z=0.01。由于算法采用動態(tài)方式進行變異操作，故將這種變異方式稱為動態(tài)變異。

將式（12）和式（14）結合，得到最終的變異方式（基于動態(tài)變異策略的變異）：

其中，t用來控制何時采用動態(tài)變異。采用動態(tài)變異的目的是使算法跳出局部最優(yōu)。當作業(yè)單元間的坐標差小于0.5 m時，采用動態(tài)變異。將基于動態(tài)變異策略的變異引入到DECell中，得到動態(tài)差分元胞多目標遺傳算法（DDECell）。

3 基于DDECell的車間布局優(yōu)化主要步驟

算法的主要流程如圖3所示，主要步驟如下：

（1）隨機生成初始種群。采用實數制編碼生成初始種群。將編碼設計為［（U1，U2，…，Un），（x1，x2，…，xn），（y1，y2，…，yn）］，其中，Un表示第n個作業(yè)單元，（xn，yn）為第n個作業(yè)單元的坐標。（U1，U2，…，Un）是n個作業(yè)單元的一個全排列。

（2）選擇父本?；谥扰c擁擠距離，從當前個體的Moore型鄰居結構中，通過二元錦標賽選出當前個體的2個父本。當2個鄰居個體的秩不同時，選擇秩小的鄰居個體作為當前個體的父本。當2個鄰居個體的秩相同時，則選擇擁擠距離大的個體。

（3）變異交叉。對作業(yè)單元編號（U1，U2，…，Un）執(zhí)行換位變異，即隨機選擇2個作業(yè)單元編號的序號，并進行互換。對（x1，x2，…，xn）、（y1，y2，…，yn）進行差分變異交叉操作。x、y坐標的變異交叉操作偽代碼為

（4）子代評估。計算子代的目標函數值，如果子代支配當前個體，或子代與當前個體互不支配，但子代的擁擠距離大于當前個體的擁擠距離，則將子代替換當前個體，同時將這個子代加入外部文檔。一旦非支配個體的數量超出了外部文檔的規(guī)模，則將擁擠距離最小的個體刪除。

（5）種群更新。重復步驟（2）～（4），完成網格中所有個體的進化操作。在每一代進化結束后，從外部文檔中選一些個體代替相同數量的二維環(huán)形網格中的個體。繼續(xù)進化，直至滿足進化的終止條件。

圖3 DDECell算法流程Fig.3 Flow chart of DDECell algorithm

4 混合作業(yè)車間布局實例

4.1 車間基本情況介紹

某吸塵器車間的總尺寸為160 m×60 m。車間內有注塑區(qū)域、原材料配送區(qū)域、電機組裝區(qū)域、噴漆區(qū)域、絲印區(qū)域、烘干區(qū)域、手柄預裝區(qū)域、地刷預裝區(qū)域、塵杯預裝區(qū)域、半成品區(qū)域、總裝區(qū)域，共11個功能單元區(qū)域。作業(yè)單元的原始布局如圖4所示?，F對原有的布局方案進行改善優(yōu)化。4號單元為噴漆單元，對其位置進行固定。矩陣C、F分別表示作業(yè)單元之間的單位物料搬運成本（以1個標準箱移動1 m所產生的搬運成本為基本單位）及物流量（單位：100標準箱）。作業(yè)單元之間的非物流鄰接度如表3所示，各個單元的其他信息如表4所示。根據車間實際情況，須滿足下列條件之一：作業(yè)單元之間水平距離hmin=2.5 m，垂直距離vmin=2.5 m。

圖4 作業(yè)單元原始布局Fig.4 Original layout of the unit

表3 作業(yè)單元之間的非物流鄰接度Tab.3 Non-logistic relationship between units

表4 各個單元的其他信息Tab.4 Additional information for each unit

4.2 實例求解及結果分析

采用DECell和DDECell對車間布局進行優(yōu)化。兩種算法的參數設置如下：種群數量為100，外部文檔儲存容量為100，最大進化代數為2 500。為了較好地平衡算法全局探索與局部開發(fā)能力［20］，取縮放因子F=0.6，交叉常量CR=0.6。兩種算法分別獨自運行15次。

由于該優(yōu)化問題是NP hard問題，故很難找到最優(yōu)解集。為了展示方便，分別從DECell和DDECell獲得的非支配解中，根據秩與擁擠距離提取50個支配解。圖5描述了這些非支配解及原始布局對應的Pareto前端，由圖可知，DECell獲得解比較密集，DDECell獲得的解的多樣性要好于DECell。

圖5 兩種算法獲得的非支配解的Pareto前端Fig.5 Non”dominant Pareto obtained by the two algorithms

圖6給出了優(yōu)化問題的雙目標Pareto前端，由圖可知，DDECell獲得的Pareto前端要比DECell的前端更靠近經兩個坐標軸，這表明DDECell的收斂性要好于DECell。

圖6 雙目標Pareto前端Fig.6 Pareto front of two objectives

由圖5和圖6可知，采用動態(tài)變異的差分元胞算法在多樣性和收斂性上都要優(yōu)于差分元胞算法，這證明了動態(tài)變異的有效性。從DDECell算法獲得的50個非支配解中，提取的3個優(yōu)化目標都優(yōu)于原始布局的解（S標示的解）。車間布局實例是一個多目標優(yōu)化問題，即3個分目標是無法同時達到最優(yōu)的。由圖6a可知，作業(yè)單元的包絡面積f2比較大；由圖6b可以看到，S的成本f1和非物流關系f3都比較好。圖7所示為S對應的布局方案，可以發(fā)現原材料配送區(qū)域2、電機組裝區(qū)域3、半成品區(qū)域10離總裝區(qū)域11都很近，這有利于吸塵器的總裝。4號噴漆單元與5號絲印單元離6號烘干區(qū)域較近，這兼顧到了這些單元間的工藝聯系，體現了非物流關系的最大化。表5給出了S對應解的具體信息。通過表5可知，經優(yōu)化后，新的布局方案的3個分目標都優(yōu)于原始布局。

圖7 S對應的作業(yè)單元布局Fig.7 Layout of optimal solution S

表5 S對應的作業(yè)單元布局Tab.5 Unit layout of optimal solution S

5 結論

（1）提出了一種基于動態(tài)差分元胞多目標遺傳算法的混合作業(yè)單元布局改善優(yōu)化新方法。在構建布局模型時，考慮實際的生產情況（特殊單元的特定處理、作業(yè)單元的移動成本、物料搬運路徑等），對原有布局進行優(yōu)化。

（2）在滿足約束條件的前提下，作業(yè)單元可以隨機布置在車間的任何一個位置，這增加了算法尋優(yōu)的難度，同時也容易使算法陷入局部最優(yōu)，降低算法的搜索效率。在差分元胞多目標遺傳算法中引入動態(tài)變異策略，有助于算法跳出局部最優(yōu)，尋找更優(yōu)的布局方案。