張萍萍，鄭飂默，王詩宇

(1.中國科學(xué)院大學(xué)，北京 100039；2.中國科學(xué)院沈陽計(jì)算技術(shù)研究所 高檔數(shù)控國家工程研究中心， 沈陽 110168；3.沈陽高精數(shù)控技術(shù)有限公司，沈陽 110168)

0 引言

企業(yè)在構(gòu)建制造系統(tǒng)初期階段，設(shè)備布局是首要解決的問題之一。研究表明，合理的設(shè)備布局至少可以節(jié)約10%～30%的物料運(yùn)輸費(fèi)用[1]。在動(dòng)態(tài)多變的市場環(huán)境下，靜態(tài)布局(SFL)[2-3]方法已經(jīng)無法滿足生產(chǎn)需求。如果采用中斷生產(chǎn)重新進(jìn)行設(shè)備布局來滿足生產(chǎn)需求，會(huì)對企業(yè)造成較大的損失。如何使布局在動(dòng)態(tài)多變的需求下，表現(xiàn)出良好的柔性和魯棒性，是企業(yè)能否持續(xù)發(fā)展的關(guān)鍵之一。

用戶需求的動(dòng)態(tài)性,導(dǎo)致傳統(tǒng)的靜態(tài)布局無法滿足在連續(xù)的生產(chǎn)過程中后期的生產(chǎn)計(jì)劃；同時(shí)又因?yàn)橹圃煜到y(tǒng)的復(fù)雜性，不可能在設(shè)備布局無法滿足生產(chǎn)計(jì)劃時(shí)，調(diào)整設(shè)備位置或重新布局。因此在制造系統(tǒng)設(shè)計(jì)初期提供一種布局方案，這種布局方案在動(dòng)態(tài)的需求下，也能很好的滿足生產(chǎn)任務(wù)，“不變應(yīng)萬變”，即魯棒性設(shè)備布局。

1987年，Meir Rosenblatt等[4]首次將魯棒性概念引入到制造業(yè)設(shè)備布局領(lǐng)域，使設(shè)備布局對動(dòng)態(tài)的生產(chǎn)任務(wù)表現(xiàn)出良好的性能。魯棒性布局是指存在一種布局方案能滿足各階段不同的生產(chǎn)需求，對于其中某個(gè)特定階段，它不一定是最優(yōu)方案，但對整個(gè)生產(chǎn)周期卻是最優(yōu)的布局方案。Ghorbanali Moslemipour等[5]針對魯棒性布局問題進(jìn)行了綜述，詳細(xì)總結(jié)了以往文獻(xiàn)中所采用的優(yōu)化模型及求解算法。劉瓊等[6]則針對設(shè)施面積不等的作業(yè)車間作為研究對象，以最小化物流搬運(yùn)費(fèi)用和面積費(fèi)用為優(yōu)化目標(biāo)，建立魯棒性布局模型，并提出一種改進(jìn)的蛙跳算法對其進(jìn)行求解。李愛平等[7]考慮到物流搬運(yùn)系統(tǒng)的設(shè)計(jì)對魯棒性布局的影響，提出設(shè)備魯棒性布局方案及物料搬運(yùn)系統(tǒng)協(xié)同優(yōu)化方法。目前魯棒性布局的研究中采用的優(yōu)化算法大都是采用加權(quán)系數(shù)將多目標(biāo)單一化，但是由于加權(quán)系數(shù)的值對結(jié)果的影響較大，因此采用基于Pareto最優(yōu)前沿的方法在多目標(biāo)空間內(nèi)直接求解，不再需要將多個(gè)目標(biāo)進(jìn)行單一化處理。在基于Pareto尋優(yōu)的多目標(biāo)優(yōu)化算法[8]中，DEB在2002年提出的帶精英策略的非支配排序遺傳算法(Non-dominated Genetic Algorithm II,NSGA-II)是一種有效的算法，已被國內(nèi)外廣泛用來求解多目標(biāo)優(yōu)化問題。

根據(jù)上述研究現(xiàn)狀，針對魯棒性設(shè)備布局問題的多目標(biāo)多約束的特點(diǎn)，以物料搬運(yùn)費(fèi)用、非物流關(guān)系和面積費(fèi)用為優(yōu)化目標(biāo)建立布局模型，并利用改過的NSGA-II算法對其求得Pareto解集，用戶根據(jù)實(shí)際情況擇優(yōu)選取布局方案。最后，通過實(shí)例驗(yàn)證模型和算法的有效性。

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

1.1 問題描述

魯棒性布局問題是連續(xù)P個(gè)生產(chǎn)計(jì)劃期最穩(wěn)定的布局方案。根據(jù)產(chǎn)品的工藝路線和各個(gè)子計(jì)劃期設(shè)備間的物流矩陣等約束條件的變化，分析整個(gè)生產(chǎn)周期，引入魯棒性指標(biāo)，最后合理確定車間設(shè)備的具體位置。

以已知的n臺(tái)設(shè)備為研究對象，以最小化車間物料搬運(yùn)費(fèi)用、非物流關(guān)系和面積費(fèi)用為優(yōu)化目標(biāo)，建立多目標(biāo)魯棒性布局模型。

假設(shè)條件：①設(shè)備均為矩形結(jié)構(gòu)，且長寬已知；② P個(gè)階段的生產(chǎn)計(jì)劃已定；③各產(chǎn)品的工藝路線已定；④同行設(shè)備的中心點(diǎn)位于同一條水平線上；⑤設(shè)備間的物料搬運(yùn)只能走水平和垂直直線。

1.2 優(yōu)化目標(biāo)

以物流費(fèi)用，非物流關(guān)系及面積費(fèi)用作為優(yōu)化目標(biāo)，具體分析如下：

(1) 物流搬運(yùn)費(fèi)用最小化。其中：i和j表示車間設(shè)備，i,j[1,2,…,n];xi和yi為設(shè)備i的坐標(biāo)值；Cij表示多設(shè)備i到設(shè)備j的單位距離物料搬運(yùn)費(fèi)用；fpij表示p階段從設(shè)備i到設(shè)備j的物料搬運(yùn)量。由文獻(xiàn)[5]對魯棒性布局問題的總結(jié)，建立車間物料搬運(yùn)費(fèi)用的計(jì)算公式，如式(1)，其中Dij表示設(shè)備i與設(shè)備j的距離。

(1)

(2) 非物流關(guān)系最大化。根據(jù) LEEK等人的研究，非物流關(guān)系可表達(dá)為：

(2)

cij為設(shè)備之間的非物流密切度值，如表 1 所示，bij是布局方案中設(shè)備之間的密切度關(guān)聯(lián)因子，它由資源間的實(shí)際物流距離dij和最大可能距離dmax決定，如表2所示。

表1 設(shè)備關(guān)系密切度分類

表2 密切度關(guān)聯(lián)因子

非物流關(guān)系的值越大，表明非物流關(guān)系越密切，為方便利用 NSGA- II 編程解決多目標(biāo)布局問題，非物流關(guān)系目標(biāo)函數(shù)如式(3)所示。其中M為一個(gè)較大的常數(shù)，可根據(jù)實(shí)際情況選擇。

(3)

(3) 車間面積費(fèi)用最小化。采用設(shè)備自動(dòng)換行的布局策略，即在同一行內(nèi)的各設(shè)備長度及其設(shè)備相互間距之和超過了布局車間的長度，則該行最后一臺(tái)設(shè)備自動(dòng)進(jìn)入下一行。

設(shè)備占地總面積簡化為矩形，長度為車間總長度L，寬度為h，h可以表達(dá)為：

h=(m-1)×s+s0+0.5×wi-(s0-0.5×wj)

其中，wi為最后一行上的設(shè)備的最大寬度，wj為第一行上的設(shè)備的最大寬度，s為行間距，s0為第一行設(shè)備與車間上邊界之間的最小距離，m為布局行數(shù)。不同布局方式中處于邊界的設(shè)備不同，h的取值也會(huì)相應(yīng)地發(fā)生變化；R為單位土地面積費(fèi)用。

因此，面積費(fèi)用公式如式(4)所示：

AC=min{R·L·h}

(4)

1.3 約束條件

(1) 邊界約束和空間約束：式(5)保證車間設(shè)備不重疊，由于使用自動(dòng)換行策略，Y方向上的行間距根據(jù)設(shè)備尺寸設(shè)定，設(shè)備之間不會(huì)出現(xiàn)重疊放置；式(6)保證一臺(tái)設(shè)備只能被放置一次，式(7)保證在設(shè)備自動(dòng)換行的布局策略下，設(shè)備不超過車間寬度；

(i,j=1,2...,n,i≠j)

(5)

(6)

h≤H

(7)

Xi和Yi表示設(shè)備i的長和寬；sij表示設(shè)備i與j的X向最小間距；L和H為車間的長和寬；hi0為設(shè)備i離車間邊距界的X向和Y向最小間距；zik是0～1決策變量，其中zik=1，表示設(shè)備i在k行上，zik=0，表示設(shè)備i不在k行上，k為設(shè)備所有的行。

Rc≤δ

(8)

(9)

2 優(yōu)化算法設(shè)計(jì)

為了對上述模型進(jìn)行化化計(jì)算，在NSGA-II的基礎(chǔ)上引入了DE策略[9-10]，從而使獲得的Pareto最優(yōu)解集保持較好的多樣性，加快算法的收斂速度。

2.1 染色體編碼/解碼機(jī)制

染色體編碼采用實(shí)數(shù)編碼方式，每個(gè)染色體由兩部分組成表示一種布局方案，這兩部分分別為設(shè)備排列順序和設(shè)備間凈間距。

[{Mv,Mr,…,Mu,…,Mz},{Δ1,Δ2,…,Δi,…,Δn}]

其中，Δ1表示設(shè)備Mv與車間邊界的最小距離，Δi表示第i臺(tái)設(shè)備與第i-1臺(tái)設(shè)備之間的凈間距，取值范圍為[Umin,Umax]。由于采用自動(dòng)換行的布局策略，當(dāng)?shù)趇臺(tái)設(shè)備剛好是某一行的第一臺(tái)設(shè)備時(shí)，Δi表示第i臺(tái)設(shè)備與車間邊界的最小距離。

染色體的解碼即求解每臺(tái)設(shè)備中心對應(yīng)的坐標(biāo)值，設(shè)備坐標(biāo)的求解公式為：

yk=(t-1)×s+s0

(10)

(i,k=1,2,…,n;t=1,2,…m)

其中，n為設(shè)備的數(shù)量，t為該染色體對應(yīng)的布局行數(shù)。

2.2 遺傳算子

(1) 二元錦標(biāo)賽選擇算子

通過快速非支配排序以及擁擠度計(jì)算之后，種群中的每個(gè)個(gè)體都得到兩個(gè)屬性：非支配序rank和擁擠度nd。利用這兩個(gè)屬性，可以區(qū)分種群中任意兩個(gè)個(gè)體的支配和非支配關(guān)系。個(gè)體優(yōu)劣比較依據(jù)為：當(dāng)且僅當(dāng)irankjd，個(gè)體i優(yōu)于個(gè)體j。

選用二元錦標(biāo)賽選擇算子，從種群中隨機(jī)選擇兩個(gè)個(gè)體，根據(jù)非支配排序和擁擠度比較兩個(gè)個(gè)體，選擇最優(yōu)的個(gè)體進(jìn)入交配池。

(2) 交叉算子

對于染色體的設(shè)備排列序列部分采用映射交叉(PMX)算子。

(3) 基于差分進(jìn)化的進(jìn)化算子

對于設(shè)備凈間距序列部分，引入DE策略進(jìn)行交叉和變異，提高算法局部搜索能力，在進(jìn)行精英保留策略選擇子代個(gè)體時(shí)擁有較高的競爭能力，即在一定程度上保證了個(gè)體的多樣性。

在DE中，常見的差分策略是隨機(jī)選取兩種群中兩個(gè)不同的個(gè)體，將其向量差縮放后與待變異個(gè)體進(jìn)行向量合成，即：

Ti=Xr1+F×[Xr2-Xr3]

其中，T為變異目標(biāo)個(gè)體；F為縮放因子；Xr1表示種群中第r1個(gè)個(gè)體。F[0,1]；r1≠r2≠r3≠i。在進(jìn)行變異操作時(shí)，為了保證解的有效性，要保證各“基因”滿足邊界條件，如果不滿足邊界條件，則隨機(jī)重新生成。

對xi及其變異的中間體Ti進(jìn)行個(gè)體間的交叉操作：

其中，Tij為變異個(gè)體Ti的第j個(gè)變量，j[1,NP]；rij為個(gè)體i第j個(gè)變量對應(yīng)的均勻分布的一人隨機(jī)變理，rij[0,1]；rnd為均勻分布的整數(shù)，rnd[1,NP]；cr為交叉概率，cr[0, 1]。

2.3 懲罰項(xiàng)

由于采用自動(dòng)換行的布局策略，因此設(shè)備在X方向上不會(huì)超出工作區(qū)域。所以只需要判斷在Y方向上最后一行的設(shè)備是否會(huì)超出車間區(qū)域。Pt為Y方向超出車間區(qū)域的懲罰項(xiàng)，如式(11)，其中m為布局行數(shù)，w最后一行設(shè)備的最大寬度，T為正的大數(shù)懲罰項(xiàng)。

(11)

2.4 算法流程

采用改進(jìn)后的NSGA-II算法求解已建立的優(yōu)化模型，DE-NSGA-II算法過程如圖1所示。首先將第t代產(chǎn)生的新種群Qt與父代Pt合并組成Rt，種群大小為2N，然后對Rt進(jìn)行非支配排序，產(chǎn)生一系列非支配集Zi并計(jì)算擁擠度。由于子代和父代個(gè)體都包含在Rt中，則經(jīng)過非支配排序以后的非支配集Z1中包含的個(gè)體是Rt中最好的，所以先將Z1放放新的父代種群Pt+1中，依次類推，直到添加Zi時(shí)，種群的大小超出N，此時(shí)對Zi中的個(gè)體使用擁擠度比較，取前(N-num(Pt+1))個(gè)元素添加到新的父代種群Pt+1中。對新的父代種群進(jìn)行選擇、交叉、變異操作，產(chǎn)生新的子代種群。

如此反復(fù)迭代直至達(dá)到最大迭代次數(shù)，得到pareto最優(yōu)解集。為了使得到的布局方案滿足魯棒性的要求，需要驗(yàn)證pareto解集中是否存在滿足魯棒性約束的解，若存在這樣的解，則對該解進(jìn)行解碼，即得到魯棒性布局方案，最后算法可能得到不只一種滿足魯棒性的布局方案，如果沒有一個(gè)解滿足魯棒性要求，則重啟算法。

圖1 NSGA-II算法流程

3 實(shí)例研究

3.1 實(shí)例描述

應(yīng)用上述算法對某柔性制造單元的布局問題進(jìn)行求解。該柔性制造單元的長為12m，寬為10m，需對12臺(tái)設(shè)備進(jìn)行布局設(shè)計(jì)，設(shè)備的具體尺寸如表3所示。設(shè)備間的凈間距?的取值范圍為[0, 1.5]，設(shè)備間行間距s為2m，第一行設(shè)備與車間邊界距離s0為1.2m。設(shè)懲罰值T=500元，土地面積費(fèi)用R=500元/m2。分析整個(gè)生產(chǎn)周期的實(shí)際情況以及車間安全性，可得到非物流關(guān)系cij，設(shè)備間水平最小間距要求hij和設(shè)備與車間邊界的最小距離要求hi0；魯棒性指標(biāo)δ=0.07。

分析該制造單元連續(xù)3個(gè)計(jì)劃期的工藝路線(表4)和物流信息(表5)，求解每個(gè)階段的物流搬運(yùn)頻率矩陣。

表3 設(shè)備尺寸(m×m)

表4 工藝路線

表5 生產(chǎn)計(jì)劃

3.2 算法參數(shù)設(shè)計(jì)與問題求解

DE-NSGA-II算法的相關(guān)參數(shù)設(shè)置如下：種群規(guī)模pop=100；最大遺傳代數(shù)maxgen=100；交叉概率pc=0.7，以式(1)～式(3)為目標(biāo)函數(shù)，運(yùn)行程序，最終得到的Pareto解集如圖2所示。針對提出的魯棒性布局模型分別應(yīng)用DE-NSGA-II、NSGA-II，SADE對該魯棒性布局模型進(jìn)行多次求解，結(jié)果對比，與NSGA-II及SADE相比，DE-NSGA-II的收斂性和多樣性更好，對比結(jié)果見表6。

圖2 pareto解集

在最終的Pareto解集中，剔除相似度比較高的布局方案，得到如表7所示的5種布局方案。方案1的目標(biāo)1值是所有解集中最小的，但是目標(biāo)2和目標(biāo)3的值是最大的；方案5的目標(biāo)3的值是最小的，但是目標(biāo)1的值是最大的；方案4的目標(biāo)2的值是所有解集中最小的，但是目標(biāo)1和目標(biāo)3的值均不是最小的。通過多次實(shí)驗(yàn)分析可得，不存在某種方案可以使得3個(gè)目標(biāo)都達(dá)到最優(yōu)。

該實(shí)例三個(gè)目標(biāo)的最優(yōu)解分別為F1=729698.92，F(xiàn)2=33.8，F(xiàn)3=50040，不存在任何一個(gè)個(gè)體能使三個(gè)目標(biāo)值同時(shí)達(dá)到最優(yōu)。企業(yè)決策者可以根據(jù)實(shí)際情況，在多種方案中選擇最合適的布局方案。

表6 三種優(yōu)化算法性能對比

表7 部分Pareto解集

4 結(jié)束語

針對提出的魯棒性布局模型，利用基于差分進(jìn)化與NSGA-II的多目標(biāo)算法驗(yàn)證了該模型的有效性，克服了使用加權(quán)系數(shù)將多目標(biāo)單一化求解多目標(biāo)問題的缺點(diǎn)，可以有效地應(yīng)對復(fù)雜多變的市場需求。算法設(shè)計(jì)的過程中，在NSGA-II算法的基礎(chǔ)上引入DE策略，有效地提高了Pareto解集的多樣性和算法的收斂速度，最終得出符合魯棒性要求的布局方案集。