丁祥海 姚文鵬

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

基于粒子群算法的多目標可重構設施布局方法

丁祥海 姚文鵬

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

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

多目標可重構設施布局;改進粒子群算法;設施形狀約束系數;Pareto解集

0 引言

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

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

1 問題描述和模型構建

1.1 問題描述

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

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

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

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

1.2 模型構建

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

1.2.1 成本目標

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

(1)

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

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

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

(2)

Ai(n)=Ai(m)+1

(3)

(4)

(5)

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

(6)

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

1.2.2 在制品庫存目標

考慮生產過程中的不確定性，以及載具的空載等情況，布局方案會對制造系統的WIP產生直接的影響[4]。對于給定的布局方案，要求在各設施處等待加工和等待運輸的期望WIP最少，目標函數如下：

(7)

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

各個設施處的期望在制品庫存函數為[4]

(8)

ui=λitei

(9)

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

(10)

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

(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設施處到i設施處，然后由i運料到j設施處所需的時間；v為載具的平均運行速度。

2 粒子群算法求解

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

(17)

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

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

2.1 粒子的編碼和解碼

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

表1中編碼表示的網格分配為:F2(1～8)，F3(9～27)，F4(28～34) ，F1(35～52) ，F5(52～60)。其中60是車間最大的網格編號。

表1 布局方案編碼

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

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

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

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

(1)xi1(t)=1；

(2)forj=2 toM+1

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

Next

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

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

Next

2.2 初始粒子群的產生

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

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

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

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

Dij=‖Fi-Fj‖

(18)

其中，Fi和Fj分別是粒子i和粒子j對應的目標向量。令：

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是粒子的個數)(圖1)。本文采用判斷個體極值粒子相對全局極值粒子的離散程度來選擇個體極值粒子Pb,i。令：

DGb=‖FGbC-FGbWIP‖

(20)

DPb,i=‖FPbC,i-FPbWIP,i‖

(21)

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

圖1 粒子的目標空間Fig.1 The target space of the particle

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

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

2.4 算法流程

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

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

(3)產生初始粒子群。用設施兩兩互換的方法，產生初始粒子群規(guī)模N，確定每個粒子的位置，計算粒子i的適應度值，并令速度等于零。為了提高初始粒子群的質量，要求產生的方案在費用和在制品庫存方面相對原方案不同時增加。用產生的布局方案的費用和在制品庫存分別除以初始方案的費用和制造品庫存。產生的布局方案應該滿足ρ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 算例及分析

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

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

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

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

表2 空間填充曲線的網格編號

表3 物流數據Tab.3 Logistics data

表4 物流費用數據Tab.4 Logistics cost data

表5 設施數據Tab.5 Facility data

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

表6 產品需求數據Tab.6 Product demand data

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

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

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

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

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

4 算例比較

4.1 遺傳算法

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

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

在進行上述三個操作之前，首先需要將問題的解表示成“染色體”，即編碼過程。本文采用二進制編碼，碼長根據設備類別數確定為20。由編碼與設備的初始布局方案而得到新的布局方案，如圖6所示。圖中，從左到右,0表示不移動，1表示移到最末端，則上述編碼(0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0)產生的新布局方案為(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)變異根據。交叉操作之后，在滿足變異概率的前提下反轉子代某個基因位置的值，其中變異基因的位置隨機確定。

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

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

4.2 退火算法

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

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

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

4.3 三種算法的比較

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

表8 三種算法的綜合比較

5 結論

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

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

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

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

[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]. 經濟地理，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)，楊將新. 可重構制造系統工藝路線與系統布局設計研究[J].計算機集成制造系統，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] 武志軍，寧汝新，王愛民. 可重構制造系統布局規(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] 張屹，盧超，張虎，等. 基于差分多元目標遺傳算法的車間布局優(yōu)化[J]. 計算機集成制造系統，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] 左興權, 王春露, 趙新超. 一種結合多目標免疫算法和線性規(guī)劃的雙行設備布局方法[J]. 自動化學報, 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] 王允良，李為吉.基于混合多目標粒子群算法的飛行器氣動布局設計[J]. 航空學報，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] 張利彪，周春光，馬銘，等. 基于粒子群算法求解多目標優(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] 丁祥海.基于改進模擬植物生長算法的多層可重構設施布局方法[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

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

TP18

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

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