丁祥海 姚文鵬

杭州電子科技大學(xué)工業(yè)工程與管理研究所，杭州，310018

基于粒子群算法的多目標(biāo)可重構(gòu)設(shè)施布局方法

丁祥海 姚文鵬

杭州電子科技大學(xué)工業(yè)工程與管理研究所，杭州，310018

提出了一種多目標(biāo)可重構(gòu)設(shè)施布局方法。該方法引入了空間填充曲線來表征設(shè)施位置，可以實現(xiàn)任意兩個設(shè)施之間的互換；考慮了柔性面積需求和設(shè)施形狀約束系數(shù)等因素，保證布局方案的可行性；建立了以成本(物料運輸成本和設(shè)施重構(gòu)成本)和在制品庫存為目標(biāo)的多目標(biāo)可重構(gòu)設(shè)施布局模型；設(shè)計了該模型的改進粒子群算法，該算法在全局極值和個體極值的選取、Pareto解集的更新策略方面相對于標(biāo)準(zhǔn)的粒子群算法有改進。最后用算例說明了該方法的有效性。

多目標(biāo)可重構(gòu)設(shè)施布局;改進粒子群算法;設(shè)施形狀約束系數(shù);Pareto解集

0 引言

可重構(gòu)設(shè)施布局(reconfigurable facilities layout problem，RFLP)是指已知下一周期的產(chǎn)品品種和數(shù)量的前提下，基于現(xiàn)有布局，尋求一種績效最佳的布局方案[1-2]。在城市生產(chǎn)環(huán)境中產(chǎn)品生產(chǎn)數(shù)據(jù)(包括產(chǎn)品品種和生產(chǎn)數(shù)量)不確定性程度高[3]，對制造提前期、在制品(works in process，WIP)、產(chǎn)出率等與運作相關(guān)的績效指標(biāo)提出了明確的要求，而這些指標(biāo)與布局方案相關(guān)[4]?，F(xiàn)有研究文獻中，RFLP的績效主要集中在物料運輸費用和設(shè)施重構(gòu)費用方面，很少綜合考慮運作方面的指標(biāo)，滿足不了實際需要[5-9]。這些運作指標(biāo)受到生產(chǎn)過程中許多動態(tài)因素的影響，很難精確建模。

多目標(biāo)可重構(gòu)布局模型比一般的布局模型更加復(fù)雜，難以精確求解，進化算法是求解這類問題的有效選擇[10-15]。粒子群優(yōu)化(particle swarm optimization，PSO)算法在單目標(biāo)優(yōu)化算法中表現(xiàn)出高效性和良好的魯棒性；而且PSO算法是基于群體操作的尋優(yōu)，可以并行地得到大量非劣解，適用于求解多目標(biāo)問題[16-17]。本文采用基于排隊論的近似計算方法[4]，綜合考慮物流運輸費用、設(shè)施重構(gòu)費用和WIP等績效指標(biāo)，建立了多目標(biāo)可重構(gòu)設(shè)施布局模型;選用PSO算法來求解多目標(biāo)可重構(gòu)設(shè)施布局模型，同時，針對Pareto解分布不均、局部堆積以及數(shù)量過大或過小的問題，對傳統(tǒng)多目標(biāo)PSO算法進行了改進。案例研究表明，該算法能夠獲得穩(wěn)定和均勻的Pareto解集，能使布局決策者對可能的布局方案有更全面的認(rèn)識，以便更好地權(quán)衡、折中和決策。

1 問題描述和模型構(gòu)建

1.1 問題描述

(2)車間有M個設(shè)施需要進行布局。所有物料從一個進料口進入車間，從一個出料口離開車間。把車間所有設(shè)施從i=0到i=M+1進行編號，i=0為進料口，i=M+1為出料口。在布局規(guī)劃時，進料口和出料口的坐標(biāo)位置不變。

(6)車間劃分為面積相等的網(wǎng)格，引入空間填充曲線來保證車間每個網(wǎng)格的連續(xù)性和遍歷性[18-19]，可很好地防止各設(shè)施之間的重疊以及設(shè)施擺放位置超出車間邊界等現(xiàn)象。網(wǎng)格分配從空間填充曲線的入口端開始，設(shè)施之間不留任何網(wǎng)格，沒有用完的網(wǎng)格余留在空間填充曲線的出口端。

(8)設(shè)施形狀不嚴(yán)格限定為矩形。為了避免產(chǎn)生一些不合適的形狀，引入設(shè)施形狀約束系數(shù)[20]。

(9)設(shè)施不能被分割。分配給一個設(shè)施的所有網(wǎng)格必須在同一條空間填充曲線上，且所有的網(wǎng)格編號是連續(xù)的。

1.2 模型構(gòu)建

RFLP是為應(yīng)對多品種小批量的市場環(huán)境提出來的，其績效指標(biāo)不僅包括物流成本和重構(gòu)成本，還包括WIP、周期時間、生產(chǎn)提前期等。在一定的產(chǎn)出率前提下，根據(jù)Little法則，在制品庫存與周期時間成比例關(guān)系，而提前期與周期時間存在內(nèi)在聯(lián)系。為不失一般性，本文選擇費用和在制品庫存為可重構(gòu)設(shè)施布局的績效評價目標(biāo)。

1.2.1 成本目標(biāo)

RFLP中，主要考慮設(shè)施的重構(gòu)成本和物流運輸成本。由于本文假定當(dāng)沒有任何請求時，載具將停留在最后送料的地方，故當(dāng)載具接收到一個從設(shè)施i運料到設(shè)施j的指令時，從所在設(shè)施r到i有可能是空載。對一個特定的布局方案，空載將產(chǎn)生成本，需要加以考慮，而在現(xiàn)有的文獻中往往忽略了空載對成本的影響?；谝陨峡紤]，可以給出RFLP的成本目標(biāo)函數(shù)：

(1)

式中，cij為從設(shè)施i到設(shè)施j移動單位距離單位物料的費用；ci為設(shè)施i的重構(gòu)費用；cempty為載具空載單位距離的費用；xi為表征設(shè)施i是否重構(gòu)的變量，其值取1和0；dij為從設(shè)施i到設(shè)施j的距離。

式(1)中第一項為重構(gòu)成本；第二項為物流成本，考慮了載具空載的情況。xi和dij是目標(biāo)函數(shù)中的決策變量。dij可用兩個設(shè)施幾何中心之間的距離表示，可由網(wǎng)格編號與網(wǎng)格坐標(biāo)方便求得，xi描述了新舊方案中設(shè)施i的位置異同[20]。

空間填充曲線對模型的約束體現(xiàn)如下，設(shè)第i個設(shè)施占有Ai個網(wǎng)格，其沿空間填充曲線所占網(wǎng)格編號依次為Ai(a),…,Ai(m),Ai(n),…,Ai(b),則應(yīng)滿足:

(2)

Ai(n)=Ai(m)+1

(3)

(4)

(5)

f(Ai(a),…,Ai(m),Ai(n),…Ai(b))≤Klim

(6)

式(2)中，1與W分別為空間曲線的最小網(wǎng)格編號與最大網(wǎng)格編號，式(2)表示車間內(nèi)足以放置M個設(shè)施且各設(shè)施均不超出車間邊界；式(3)表示各個設(shè)施所占網(wǎng)格的連續(xù)性，保證設(shè)施不能被分割；式(4)表示不同設(shè)施之間依次相鄰，很好地防止了各設(shè)施之間的重疊；式(5)表示各設(shè)施需滿足柔性面積約束；式(6)表示形狀約束系數(shù)對各設(shè)施形狀的約束，Klim為本文規(guī)定的形狀約束系數(shù)，f(·)為形狀約束系數(shù)計算函數(shù)，其計算方式已在算法中體現(xiàn)，此處不做詳細(xì)說明。

1.2.2 在制品庫存目標(biāo)

考慮生產(chǎn)過程中的不確定性，以及載具的空載等情況，布局方案會對制造系統(tǒng)的WIP產(chǎn)生直接的影響[4]。對于給定的布局方案，要求在各設(shè)施處等待加工和等待運輸?shù)钠谕鸚IP最少，目標(biāo)函數(shù)如下：

(7)

式(7)中等號右邊第一項表示載具的WIP期望，第二項表示在各個設(shè)施處的WIP期望。

各個設(shè)施處的期望在制品庫存函數(shù)為[4]

(8)

ui=λitei

(9)

相似地，運輸工具的期望WIP由下式給出[4]:

(10)

設(shè)ti是載具運輸物料i所需的時間，據(jù)文獻[4]，可以給出以下參數(shù)的計算公式：

(11)

(12)

(13)

(14)

(15)

i=1,2,…,M+1

(16)

trij(x)=(dri+dij)/v

πi=λi/λti=1,2,…,M+1

式中，trij(x)為載具由r設(shè)施處到i設(shè)施處，然后由i運料到j(luò)設(shè)施處所需的時間；v為載具的平均運行速度。

2 粒子群算法求解

很難找到一個布局方案，可使得費用和WIP同時最低，本文的目標(biāo)是盡可能找出RFLP的Pareto解集。PSO算法中每個粒子是解空間中的一個解，它根據(jù)自己的飛行經(jīng)驗和同伴的飛行經(jīng)驗來調(diào)整自己的飛行。每個粒子在飛行過程中所經(jīng)歷的最好位置，就是粒子本身找到的最優(yōu)解，稱為粒子i的個體極值Pb(i)；整個群體所經(jīng)歷過的最好位置，就是整個群體目前找到的最優(yōu)解，稱之為全局極值Gb。每個粒子都通過上述兩個極值不斷更新自己，更新公式如下：

(17)

式中，vi(t+1)、vi(t)、xi(t+1)、xi(t)分別為粒子i在時刻t+1和t的速度向量和位置向量；w為慣性權(quán)重；c1、c2為學(xué)習(xí)因子；r1、r2為隨機函數(shù)。

現(xiàn)有多目標(biāo)粒子群尋優(yōu)的文獻中，主要研究如何選擇確定Pb(i)和Gb來更新粒子的位置和速度[16-17]，使得粒子最終收斂于Pareto解附近，但還存在著Pareto解分布不均、局部堆積以及數(shù)量過大或過小的問題。另外，多目標(biāo)粒子群算法中，變量是連續(xù)的，而在多目標(biāo)可重構(gòu)布局問題中，布局方案是一個由整數(shù)組成的離散向量，需要對粒子群算法進行一定的改進才能適用。根據(jù)前面建立模型的特點，本文在粒子的編碼和解碼、初始粒子群的產(chǎn)生、個體極值和全局極值的選擇、Pareto解的更新策略等方面進行了改進，目的是獲得一個分布比較均勻的穩(wěn)定的Pareto解集。

2.1 粒子的編碼和解碼

根據(jù)前面空間曲線網(wǎng)格的分配規(guī)則，只要知道每個設(shè)施在空間曲線上的起始網(wǎng)格編碼，就能確定整個布局方案；因此每個粒子可以表示為由每個設(shè)施在空間曲線上的起始網(wǎng)格編碼組成的M維向量(M為設(shè)施數(shù))，如表1所示。

表1中編碼表示的網(wǎng)格分配為:F2(1～8)，F(xiàn)3(9～27)，F(xiàn)4(28～34) ，F(xiàn)1(35～52) ，F(xiàn)5(52～60)。其中60是車間最大的網(wǎng)格編號。

表1 布局方案編碼

由于粒子群算法為連續(xù)空間，而布局問題是整數(shù)規(guī)劃問題，所以需要作相應(yīng)的調(diào)整。

設(shè)xij(t)表示粒子i中設(shè)施j在第t次迭代后的起始網(wǎng)格編號。如果xij(t)<1,則xij(t)=1(1是最小的網(wǎng)格編號)；如果xij(t)>W,則xij(t)=W(W是最大的網(wǎng)格編號)；如果xij(t)為小數(shù)，按四舍五入方法取整；對每一個粒子i按照xij(t)的值由小到大排序，如果xij(t)相等則隨機排序。

對每一個排好序的粒子，需要針對每個設(shè)施檢驗面積大小和形狀約束系數(shù)是否滿足要求，具體算法如下。

設(shè)排序后的隊列為xi1(t)

(1)xi1(t)=1；

(2)forj=2 toM+1

計算并判斷設(shè)施j-1的形狀系數(shù)約束，如果滿足則停止

Next

如果設(shè)施j-1的形狀系數(shù)得不到滿足，則終止

如果xi，M+1(t)>W，則終止(最后設(shè)施結(jié)束編號大于空間填充曲線最大編號)

Next

2.2 初始粒子群的產(chǎn)生

用設(shè)施兩兩互換的方法來獲取初始粒子群[21-23]。在設(shè)施兩兩互換時，既要考慮面積相等設(shè)施之間的互換和相鄰設(shè)施之間的互換，還要考慮面積不相等的不相鄰的設(shè)施之間的互換[21-23]。面積不相等的不相鄰的設(shè)施互換時可能產(chǎn)生設(shè)施重構(gòu)的傳導(dǎo)效應(yīng)。當(dāng)發(fā)生設(shè)施重構(gòu)傳導(dǎo)效應(yīng)有多個重構(gòu)方案時，選擇重構(gòu)費用最小的方案。該種情形下的設(shè)施兩兩互換的算法屬于同層設(shè)施互換算法[20]。

2.3 全局極值和個體極值的選擇與確定

本文為獲取較均勻分布的Pareto解，對Gb和Pb(i)的選取依據(jù)為：根據(jù)各個目標(biāo)函數(shù)之間的制約關(guān)系，盡可能使得每個粒子都移向解區(qū)域中不同的解，則可找到更多不同的Pareto解，以免收斂于非最優(yōu)解的局部區(qū)域。

(1)Gb的確定。Gb引導(dǎo)Pareto粒子在目標(biāo)空間中分布均勻,因此，在目標(biāo)空間中選擇最孤立的Pareto粒子作為Gb。本文用以下方法來選定最孤立的粒子。定義目標(biāo)空間Pareto粒子i和粒子j之間的距離為

Dij=‖F(xiàn)i-Fj‖

(18)

其中，F(xiàn)i和Fj分別是粒子i和粒子j對應(yīng)的目標(biāo)向量。令：

Si=min(Dij)i≠j

(19)

Si越大，說明與Pareto粒子i相似的粒子越少,因此，取Si最大的粒子為全局極值。

(2)Pb(i)的確定。對于整個粒子群，存在兩個全局極值，即GbC和GbWIP；對于粒子i，存在兩個個體極值，即PbC,i和PbWIP,i(i=1,2,…,N；N是粒子的個數(shù))(圖1)。本文采用判斷個體極值粒子相對全局極值粒子的離散程度來選擇個體極值粒子Pb,i。令：

DGb=‖F(xiàn)GbC-FGbWIP‖

(20)

DPb,i=‖F(xiàn)PbC,i-FPbWIP,i‖

(21)

式中，DGb為兩個全局極值之間的距離；DPb,i為粒子i的兩個局部極值之間的距離。

圖1 粒子的目標(biāo)空間Fig.1 The target space of the particle

用以下算法實現(xiàn)Pb(i)的選擇：

fori=1 toN

If (DPb,i

Pb,i=Rselect(Pb,WIP,i,PbC,i) //隨機選擇

Else

Pb,i=Aver(PbC,i,PbWIP,i) //可以平均，也可以按照某種比例計算

end if

Next

(3)Pareto解集的更新策略。Pareto解集更新策略的實質(zhì)是在迭代過程中，采用什么機制來保存Pareto粒子，避免因粒子規(guī)模膨脹而使收斂速度慢，同時也避免Pareto解堆積在某一局部區(qū)域。本文在傳統(tǒng)粒子群算法之外，引入三個粒子池，分別是Pareto粒子池、個體極值粒子池和新粒子池，三個粒子池和粒子群算法之間的關(guān)系如圖2所示。Pareto粒子池保存每次迭代更新后的Pareto粒子，個體極值粒子池保存每次迭代后產(chǎn)生的每個粒子的個體極值粒子，新粒子池保存最新迭代后的粒子。為了避免因Pareto粒子數(shù)量過多，增加計算量，需要將Pareto粒子維持在一定的規(guī)模。當(dāng)Pareto粒子達(dá)到限定的規(guī)模時，可以根據(jù)式(19)中的值來找出并刪除發(fā)生堆積的粒子(越小，堆積越嚴(yán)重)。另外，為了獲取更加廣泛的Pareto邊界(GbC和GbWIP的目標(biāo)值盡可能小)，在當(dāng)前目標(biāo)值的基礎(chǔ)上，可以采用模擬退火方法，繼續(xù)進行局部搜索[24]，也可以選擇值大的粒子進行局部搜索。具體方法，本文不作贅述。

圖2 粒子的更新策略Fig.2 The update strategy of the particle

2.4 算法流程

(1)讀取數(shù)據(jù)。讀取的數(shù)據(jù)既包括物流數(shù)據(jù)、車間網(wǎng)格坐標(biāo)和編號數(shù)據(jù)、初始布局方案數(shù)據(jù)、價格數(shù)據(jù)(設(shè)施重構(gòu)費率、物流運輸費率、載具空載費)、時間數(shù)據(jù)(每個設(shè)施加工時間的數(shù)學(xué)期望、方差和變異數(shù))、載具平均運行速度等基礎(chǔ)數(shù)據(jù)，還包括一些程序運行所需的數(shù)據(jù)，如迭代次數(shù)、粒子群規(guī)模、Pareto粒子規(guī)模等。

(2)計算原始方案的E[C]和E[IWIP]。

(3)產(chǎn)生初始粒子群。用設(shè)施兩兩互換的方法，產(chǎn)生初始粒子群規(guī)模N，確定每個粒子的位置，計算粒子i的適應(yīng)度值，并令速度等于零。為了提高初始粒子群的質(zhì)量，要求產(chǎn)生的方案在費用和在制品庫存方面相對原方案不同時增加。用產(chǎn)生的布局方案的費用和在制品庫存分別除以初始方案的費用和制造品庫存。產(chǎn)生的布局方案應(yīng)該滿足ρcos t<1或ρWIP<1。

(4)更新各個粒子池中的粒子。

(5)計算粒子i的體極值PbC,i、PbWIP,i；找出兩個全局極值GbC、GbWIP。

(6)計算Pareto粒子之間的Dij和Si，確定全局極值Gb。

(7)計算DGb值，對粒子i求DPb，i，并確定Pb(i)。

(8)用步驟(6)和步驟(7)求得的Gb和Pb(i)更新粒子i的速度和位置。

(9)對每個粒子進行解碼，每個粒子需滿足E[Ci]和E[IWIP,i]不同時增大，如果不能滿足，則粒子位置不變。

(10)如滿足條件中止退出，否則返回步驟(4)。

3 算例及分析

本文算例的車間網(wǎng)格和空間填充數(shù)據(jù)如表2所示，物流數(shù)據(jù)如表3所示，物流費用數(shù)據(jù)如表4所示，設(shè)施數(shù)據(jù)如表5所示，初始布局方案如圖3所示。生產(chǎn)10種產(chǎn)品，產(chǎn)品需求如表6所示。入料口的坐標(biāo)為(0,0)，出料口坐標(biāo)為(21,31)，入口處理單位物料的平均時間為9 min，出口為9.3 min，變異系數(shù)設(shè)為1。載具運行的平均速度為1.67 m/s，單位距離空載的費用為0.01元，粒子的種群規(guī)模取20，最大迭代次數(shù)為150，Pareto解集規(guī)模取50，學(xué)習(xí)因子c1=c2=2，慣性權(quán)重w=0.5，所有設(shè)施形狀系數(shù)設(shè)為1.5，設(shè)施的加工時間變異系數(shù)設(shè)為1，產(chǎn)品需求變異系數(shù)設(shè)為1。以上算法用MATLAB R2010b編程實現(xiàn)。

本算法對粒子群算法的改進主要體現(xiàn)在以下三個方面：

(1)針對多目標(biāo)的方案選擇問題，引入Pareto解集的概念，使得決策者可從多個Pareto解集方案中選出一個適合自身情況的優(yōu)化方案。

(2)改善后的算法增加了算法的局部搜索能力。如圖4所示，在每一次迭代運算過后，針對現(xiàn)有的Pareto解集中的每一個Pareto解逐個采用退火算法進行局部搜索(分別在A框、B框、C框、D框內(nèi)產(chǎn)生適宜的新Pareto解)，使得Pareto解更加廣泛。

表2 空間填充曲線的網(wǎng)格編號

表3 物流數(shù)據(jù)Tab.3 Logistics data

表4 物流費用數(shù)據(jù)Tab.4 Logistics cost data

表5 設(shè)施數(shù)據(jù)Tab.5 Facility data

圖3 初始布局方案Fig.3 The initial layout scheme

表6 產(chǎn)品需求數(shù)據(jù)Tab.6 Product demand data

圖4 粒子的局部搜索更新Fig.4 The updating of local search for particle

(3)選用Gb和Pb(i)，使得Pareto解更加均勻。在圖4的Pareto解中，根據(jù)Gb的確定方法，A框點(與其他點的相似程度最低)所對應(yīng)的方案編碼將會被設(shè)定為Gb進行迭代運算，因此迭代運算后的新方案編碼將會較大概率出現(xiàn)在A框附近，則會使得Pareto解更加均勻。

(4)算法采用最優(yōu)解保存策略，限定Pareto解集的規(guī)模，加快算法收斂速度。Pareto解集的規(guī)模被限定之后，進行退火算法的局部搜索次數(shù)將會減少，此外Gb的確定過程也變得便捷，這將加快算法的收斂速度，節(jié)約算法運算時間。

改進粒子群算法結(jié)果見圖5和表7。

圖5 粒子群算法迭代后的情形Fig.5 The situation after the iteration by the particle swarm optimization algorithm

4 算例比較

4.1 遺傳算法

遺傳算法是解決搜索問題的一種通用算法，該算法的計算優(yōu)化過程就如同生物學(xué)上遺傳進化的過程，主要包括選擇、交叉、變異三個基本操作。本算例種群規(guī)模取20,最大進化代數(shù)取150，雜交概率取0.9，變異概率取0.05，二進制編碼位串的長度取20。

表7 改進粒子群算法得到的結(jié)果Tab.7 Improved particle swarm optimization algorithm results

在進行上述三個操作之前，首先需要將問題的解表示成“染色體”，即編碼過程。本文采用二進制編碼，碼長根據(jù)設(shè)備類別數(shù)確定為20。由編碼與設(shè)備的初始布局方案而得到新的布局方案，如圖6所示。圖中，從左到右,0表示不移動，1表示移到最末端，則上述編碼(0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0)產(chǎn)生的新布局方案為(A B H S G T W D C V F U K E P M R L N J)。

(1)選擇策略。在每次迭代之后，從種群中選取E[Ci]/E[C]與E[IWIP,i]/E[IWIP]之和最小的編碼作為父代編碼，母代編碼則從迭代后的種群中隨機選擇。

(2)交叉方法。在滿足交叉概率的前提下，對選取的父代編碼和母代編碼采用隨機選取切點位置的單點交叉方式。

(3)變異根據(jù)。交叉操作之后，在滿足變異概率的前提下反轉(zhuǎn)子代某個基因位置的值，其中變異基因的位置隨機確定。

由于此算例是多目標(biāo)的，最終的結(jié)果并不是僅僅希望得到E[Ci]/E[C]與E[IWIP,i]/E[IWIP]之和的最小值，而是收集與E[C]和E[IWIP]相比,E[Ci]和E[IWIP,i]不同時增大的方案，所以在每次迭代之后會收集此方案的編碼并存儲，結(jié)果見圖7。

圖7 遺傳算法迭代后的情形Fig.7 The situation after the iteration by the genetic algorithm

4.2 退火算法

本算例初始溫度設(shè)為20，終止溫度設(shè)為1，且采用等比例下降法降溫，此比例設(shè)為0.9，此外最大迭代次數(shù)設(shè)為20，最穩(wěn)定狀態(tài)的步數(shù)設(shè)為20。

此算法的編碼與解碼原理和粒子群算法相同，編碼中數(shù)據(jù)的大小順序決定相應(yīng)設(shè)備的先后排列順序。由初始溫度、終止溫度以及溫度下降比例三個變量控制外循環(huán)的次數(shù)，由最大迭代次數(shù)和最穩(wěn)定狀態(tài)的步數(shù)控制內(nèi)循環(huán)的次數(shù)，并以E[Ci]/E[C]與E[IWIP,i]/E[IWIP]之和的值為比較指標(biāo)(使之趨于較小值)。與遺傳算法類似，在每次迭代之后會收集此方案的編碼并存儲，結(jié)果如圖8所示。

圖8 退火算法迭代后的情形Fig.8 The situation after the iteration by the annealing algorithm

4.3 三種算法的比較

綜合比較三種算法在搜索Pareto解、尋優(yōu)能力以及尋優(yōu)速度等方面的表現(xiàn)，給出表8的比較結(jié)果。

表8 三種算法的綜合比較

5 結(jié)論

(1)引入了空間填充曲線，并按空間填充曲線確定的順序給設(shè)施分配面積，利用空間填充曲線的連續(xù)性，將二維的平面布局問題轉(zhuǎn)化為設(shè)施網(wǎng)格編號的一維排列問題，降低了算法的復(fù)雜性；考慮了不同面積的設(shè)施交換時可能產(chǎn)生的設(shè)施重構(gòu)傳導(dǎo)效應(yīng)，通過引入設(shè)施的柔性面積需求，減少了這種效應(yīng)的影響；引入設(shè)施形狀約束系數(shù)，使獲得的布局方案更加符合實際情況。

(2)將車間近似描述為GI/G/1的網(wǎng)絡(luò)排隊模型，既考慮了設(shè)施的加工時間，又考慮了載具的處理時間；既考慮了載具送料到各個設(shè)施的到達(dá)時間間隔，又考慮了載具空載情況。

(3)采用粒子群進行求解。在計算粒子個體最佳值和全局最佳值的過程中，綜合考慮了費用和在制品庫存兩個目標(biāo)函數(shù)的影響，保證了算法收斂于非劣最優(yōu)解和全局性；Pareto解集的更新策略，保證了算法的效率和解集的均勻性。

(4)本文沒有考慮在制品庫存和設(shè)施面積之間的關(guān)系。在實際生產(chǎn)中，在制品庫存需要有緩沖的空間，本文雖引入了設(shè)施的柔性面積需求，但在建立的模型中沒有仔細(xì)探討它們之間的關(guān)系。在城市生產(chǎn)方式中，面積使用費日益提高，成為影響制造企業(yè)生產(chǎn)成本的重要影響因素。另外，本文沒有對粒子群算法中慣性權(quán)重、學(xué)習(xí)因子等參數(shù)的設(shè)定進行討論。

[1] MENG G ,HERAGU S S, ZIJM H. Reconfigurable Layout Problem[J]. International Journal Production Research,2004,42(22):4709-472.

[2] BENJAAFAR S，HERAGU S S，IRANI S A. Next Generation Factory Layouts: Research Challenges and Recent Progress[J]. Interfaces，2002，32(6):58-76.

[3] 王磊，付建榮. 美國都市工業(yè)的空間分布及其對中國城市發(fā)展的啟示[J]. 經(jīng)濟地理，2014,34(8)：81-88. WANG Lei, FU Jianrong. The Spatial Distribution of Urban Manufacturing Industries in the United States and Its Implications for Urban Development in China[J].Economic Geography,2014,34(8)：81-88.

[4] WHITT W. Approximations for the GI/G/mQueue[J]. Production and Operations Management，1993，2(2):114-161.

[5] GUAN X，DAI X, QIU B， et al. A Revised Electromagnetism-like Mechanism for Layout Design of Reconfigurable Manufacturing System[J].Computer & Industrial Engineering, 2012,63(1):98-108.

[6] ABDI M R. Layout Configuration Selection for Reconfigurable Manufacturing Systems Using the Fuzzy AHP[J].International Journal Technology and Management,2009,17(1/2):149-165.

[7] 金哲，宋執(zhí)環(huán)，楊將新. 可重構(gòu)制造系統(tǒng)工藝路線與系統(tǒng)布局設(shè)計研究[J].計算機集成制造系統(tǒng)，2007,13(1)：7-12. JIN Zhe, SONG Zhihuan, YANG Jiangxin. Process Route and Layout Design Method for Reconfigurable Manufacturing Systems[J].Computer Integrated Manufacturing Systems,2007,13(1)：7-12.

[8] 武志軍，寧汝新，王愛民. 可重構(gòu)制造系統(tǒng)布局規(guī)劃方案的灰色模糊綜合評價方法[J]. 中國機械工程，2007,18(19):2313-2318. WU Zhijun, NING Ruxin, WANG Aimin. GreyFuzzy Synthetically Evaluation Method for RMS Layout Planning[J].China Mechanical Engineering, 2007,18(19):2313-2318.

[9] SHAFIGH F， DEFERSHA F M. A Mathematical Model for the Design of Distributed Layout by Considering Production Planning and System Reconfiguration over Multiple Time Periiods[J]. Journal of Industrial Engineering International,2015,11(3):283-295.

[10] 張屹，盧超，張虎，等. 基于差分多元目標(biāo)遺傳算法的車間布局優(yōu)化[J]. 計算機集成制造系統(tǒng)，2013，19(4)：727-734. ZHANG Yi，LU Chao，ZHANG Hu，et al. Workshop Layout Optimization Based on Differential Cellular Multi-objective Genetic Algorithm[J]. Computer Integrated Manufacturing Systems，2013，19(4)：727-734.

[11] 左興權(quán), 王春露, 趙新超. 一種結(jié)合多目標(biāo)免疫算法和線性規(guī)劃的雙行設(shè)備布局方法[J]. 自動化學(xué)報, 2015,41(3):528-540. ZUO Xingquan，WANG Chunlu，ZHAO Xinchao. Combining Multi-objective Immune Algorithm and Linear Programming for Double Row Layout Problem[J]. Acta Automatica Sinica，2015，41(3)：528-540.

[12] SINGH S P, SINGH V K. An Improved Heuristic Approach for Multi-objective Facility Layout Problem[J]. International Journal of Production Research,2010,48(4):1171-1194.

[13] MATAI R. Solving Multi-objective Facility Layout Problem by Modified Simulated Annealing[J]. Applied Mathemtics and Computation,2015,261(7):302-311.

[14] CHEN G Y， LO J C. Dynamic Facility Layout with Multi-objectives[J].Asia-Pacific Journal of Operational Research，2014,31(4):1450027.1-1450027.26.

[15] AIELLO G, SCALIA G L, ENEA M.A Non-dominated Ranking Multi-objective Genetic Algorithm and Electre Method for Unequal Area Facility Layout Problems[J]. Expert Systems with Applications,2013,40(12):4812-4819.

[16] 王允良，李為吉.基于混合多目標(biāo)粒子群算法的飛行器氣動布局設(shè)計[J]. 航空學(xué)報，2008，29(5)：1202-1206. WANG Yunliang，LI Weijie. Aerodynamic Configuration Design of Aircraft with Hybrid Multi-objective Particle Swarm Optimization[J]. Acta Aeronautica et Astronautica Sinica,2008,29(5):1202-1206.

[17] 張利彪，周春光，馬銘，等. 基于粒子群算法求解多目標(biāo)優(yōu)化問題[J]. 計算機研究與發(fā)展，2004，41(7)：1286-1291. ZHANG Libiao， ZHOU Chunguang，MA Ming, et al. Solutions of Multi-objective Optimization Problems Based on Particle Swarm Optimization[J]. Journal of Computer Research and Development, 2004,41(7):1286-1291.

[18] BOZER Y A， MELLER R D，ERLEBACHER S J. An Improvement-type Layout Algorithm for Single and Multiple-floor Facilities[J]. Management Sci.,1994,40(7):918-932.

[19] JOHNSON R V. Spacecraft for Multi-floor Layout Planning[J]. Management Science,1982,28(2):407-417.

[20] 丁祥海.基于改進模擬植物生長算法的多層可重構(gòu)設(shè)施布局方法[J].中國機械工程，2016,27(15)：2027-2034. DING Xianghai. Multi-floor Reconfigurable Facility Layout Method Based on Improved Plant Growth Simulation Algorithm[J].China Mechanical Engineering,2016,27(15):2027-2034.

[21] POURVAZIRI H，NADERI B. A Hybrid Multi-population Genetic Algorithm for the Dynamic Facility Layout Problem[J]. Applied Soft Computing，2014，24(11)：457-469.

[22] SAMARGHANDI H, TAABAYAN P, JAHANTIGH F F. A Particle Swarm Optimization for the Single Row Facility Layout Problem[J]. Cpmputer&Industrial Engineering,2010,58(4):529-534.[23] GARCA-HERNNDEZ L, PALOMO-ROMERO J M, SALAS-MORERA L, et al. A Novel Hybrid Evolutionary Approach for Capturing Decision Maker Knowledge into the Unequal Area Facility Layout Problem [J]. Expert System with Applications,2015(42):4697-4708.

(編輯 袁興玲)

Multi-objective Reconfigurable Facility Layout Method Based on Particle Swarm Optimization

DING Xianghai YAO Wenpeng

Institute of Industrial Engineering and Management，Hangzhou Dianzi University, Hangzhou,310018

A method of multi-objective reconfigurable facilities layout was presented. The space filling curve was used to describe the facilities locations and it was possible to exchange between any two facilities. The flexibility area requirements of facility and the facility’s shape constraint coefficient were used to keep the layout solution’s feasibility. A multi-objective reconfigurable facilities layout model with costs (material transportation costs and facility reconstruction costs) and works in processes (WIP) as targets was established. An improved particle swarm optimization algorithm was designed for this model. Compared with standard particle swarm optimization the algorithm was improved in the selection of global extremum and individual extremum, and the updating strategy of Pareto solution set. Finally, an example was given to illustrate the effectiveness of this method.

multi-objective reconfigurable facility layout；improved particle swarm optimization algorithm；facility shape constraint coefficient；Pareto set

2016-09-05

國家社會科學(xué)基金資助項目(15BGL100)；NSFC-浙江兩化融合聯(lián)合基金資助項目(U1509220)；浙江省自然科學(xué)基金資助項目(LY13G010007)；浙江省人文社科基地資助重點項目(ZD05-2016ZB)；浙江省哲學(xué)社會科學(xué)重點研究基地浙江省信息化與經(jīng)濟社會發(fā)展研究中心資助項目(15XXHJD11)

TP18

10.3969/j.issn.1004-132X.2017.07.016

丁祥海，男，1971年生。杭州電子科技大學(xué)管理學(xué)院副教授。主要研究方向為工業(yè)工程、柔性裝配系統(tǒng)等。發(fā)表論文20余篇。E-mail：dxh@hdu.edu.cn。姚文鵬，男，1992年生。杭州電子科技大學(xué)管理學(xué)院碩士研究生。