基于動態差分元胞多目標遺傳算法的混合作業車間布局改善與優化

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

浙江工業大學機械工程學院，杭州，310014

0 引言

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

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

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

1 多目標混合作業車間布局模型

1.1 多目標函數

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

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

1.1.1 物料搬運成本最小

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

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

1.1.2 作業單元移動成本最小

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

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

1.1.3 作業單元包絡矩形面積最小

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

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

最大化優化目標可以轉換成最小化優化目標，故

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

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

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

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

1.2 約束條件

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

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

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

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

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

1.3 作業單元間的距離

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

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

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

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

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

2 動態差分元胞多目標遺傳算法設計

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

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

交叉操作后獲得的向量

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

連續型車間布局模型中，布局的解有無窮多個，一旦某個解占優，則算法容易陷入局部最優。當算法獲得的所有解陷入局部最優時，xr2［j］-xr3［j］趨于零。式（13）的變異方式不利于算法跳出局部最優［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較小，算法不易跳出局部最優；z較大，算法的收斂精度就差，這里取z=0.01。由于算法采用動態方式進行變異操作，故將這種變異方式稱為動態變異。

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

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

3 基于DDECell的車間布局優化主要步驟

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

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

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

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

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

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

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

4 混合作業車間布局實例

4.1 車間基本情況介紹

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

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

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

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

4.2 實例求解及結果分析

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

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

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

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

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

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

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

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

5 結論

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

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