基于動(dòng)態(tài)差分元胞多目標(biāo)遺傳算法的混合作業(yè)車間布局改善與優(yōu)化

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

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

0 引言

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

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

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

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

1.1 多目標(biāo)函數(shù)

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

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

1.1.1 物料搬運(yùn)成本最小

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

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

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

針對(duì)不同的生產(chǎn)需求，部分作業(yè)單元將重排組合，其函數(shù)表達(dá)式為

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

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

作業(yè)單元包絡(luò)矩形面積函數(shù)表達(dá)式為式中，L為包絡(luò)所有作業(yè)單元矩形的長(zhǎng)度；W為包絡(luò)所有作業(yè)單元矩形的寬度。

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

最大化優(yōu)化目標(biāo)可以轉(zhuǎn)換成最小化優(yōu)化目標(biāo)，故

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

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

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

因?yàn)榈?個(gè)和第2個(gè)優(yōu)化目標(biāo)單位一致，因此，上述4個(gè)目標(biāo)可以最終轉(zhuǎn)化為3個(gè)優(yōu)化目標(biāo)：

1.2 約束條件

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

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

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

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

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

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

在車間布局中，常采用曼哈頓距離來(lái)表示作業(yè)單元與作業(yè)單元之間的物料搬運(yùn)距離。當(dāng)2個(gè)作業(yè)單元之間無(wú)其他障礙單元時(shí)，采用曼哈頓距離來(lái)表示2個(gè)作業(yè)單元之間的物料搬運(yùn)距離比較符合實(shí)際情況，曼哈頓距離的計(jì)算公式如下：

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

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

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

為了繞開(kāi)這些障礙物，在原先曼哈頓距離路線的基礎(chǔ)上提取出4條新路線，并選取距離最短的路線來(lái)代替原先的物料搬運(yùn)路線，修正公式如下：

2 動(dòng)態(tài)差分元胞多目標(biāo)遺傳算法設(shè)計(jì)

差分進(jìn)化算法有多種變異方式，其中，差分元胞多目標(biāo)遺傳算法DECell的變異、交叉操作為

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

交叉操作后獲得的向量

式中，Ri[j]為個(gè)體i的第j維決策變量在交叉操作過(guò)程中產(chǎn)生［0,1］之間均勻分布的隨機(jī)數(shù)；CR為介于［0,1］間的交叉常量。

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

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

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

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

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

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

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

（2）選擇父本。基于秩與擁擠距離，從當(dāng)前個(gè)體的Moore型鄰居結(jié)構(gòu)中，通過(guò)二元錦標(biāo)賽選出當(dāng)前個(gè)體的2個(gè)父本。當(dāng)2個(gè)鄰居個(gè)體的秩不同時(shí)，選擇秩小的鄰居個(gè)體作為當(dāng)前個(gè)體的父本。當(dāng)2個(gè)鄰居個(gè)體的秩相同時(shí)，則選擇擁擠距離大的個(gè)體。

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

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

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

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

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

4.1 車間基本情況介紹

某吸塵器車間的總尺寸為160 m×60 m。車間內(nèi)有注塑區(qū)域、原材料配送區(qū)域、電機(jī)組裝區(qū)域、噴漆區(qū)域、絲印區(qū)域、烘干區(qū)域、手柄預(yù)裝區(qū)域、地刷預(yù)裝區(qū)域、塵杯預(yù)裝區(qū)域、半成品區(qū)域、總裝區(qū)域，共11個(gè)功能單元區(qū)域。作業(yè)單元的原始布局如圖4所示?，F(xiàn)對(duì)原有的布局方案進(jìn)行改善優(yōu)化。4號(hào)單元為噴漆單元，對(duì)其位置進(jìn)行固定。矩陣C、F分別表示作業(yè)單元之間的單位物料搬運(yùn)成本（以1個(gè)標(biāo)準(zhǔn)箱移動(dòng)1 m所產(chǎn)生的搬運(yùn)成本為基本單位）及物流量（單位：100標(biāo)準(zhǔn)箱）。作業(yè)單元之間的非物流鄰接度如表3所示，各個(gè)單元的其他信息如表4所示。根據(jù)車間實(shí)際情況，須滿足下列條件之一：作業(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 各個(gè)單元的其他信息Tab.4 Additional information for each unit

4.2 實(shí)例求解及結(jié)果分析

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

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

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

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

圖6 雙目標(biāo)Pareto前端Fig.6 Pareto front of two objectives

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

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

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

5 結(jié)論

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

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