基于混合蟻群算法的生產系統設施規劃問題研究

李 輝，朱連宇，齊二石

（天津大學管理與經濟學部，天津300072）

基于混合蟻群算法的生產系統設施規劃問題研究

李 輝，朱連宇，齊二石

（天津大學管理與經濟學部，天津300072）

設施規劃問題主要研究生產設備的布局規劃，從而減小廠區內的物料搬運成本。一個有效的設施規劃有利于生產過程中整體運作效率的提高。隨著市場競爭的日趨激烈，市場環境處于不斷的變化之中，制造企業需不斷對設施布局進行重新規劃來適應不斷變化的市場環境對產品需求量的影響，并達到降低成本的目的。這一問題便需要用多階段設施規劃（MFLP）的方法來解決。本文提出了一種改進的混和蟻群算法（HACO）來解決帶有財務預算約束的多階段設施規劃問題，并將此方法與其他一些典型的啟發式算法進行了對比分析。結果表明，本文提出的HACO算法是求解帶有財務預算約束的MFLP問題的一種有效的方法。

多階段設施規劃；混合蟻群算法；財務預算約束

1 引言

當今世界，全球的競爭越來越體現在經濟和科技實力的競爭，而技術創新則日益成為促進經濟增長和提高科技競爭力的關鍵。技術獲取模式作為企業技術戰略的重要一環，對企業長遠發展意義重大。

設施規劃問題主要研究生產設備的布局規劃，從而減小廠區內的物料搬運成本。據統計資料表明，一個生產車間的物料搬運成本占整個生產運作成本的20%～50%，占產品生產總成本的15%-70%［1］。在一個生產車間中，一個有效的設施規劃能夠調整設備間的物流量，從而使每個設備在正確的時間得到正確數量的物料，這樣既可以減少在制品的庫存量，又能夠防止廠房中機器設備的過度使用，減少物流成本。一個有效的設施規劃有利于生產過程中整體運作效率的提高［2］。

物流成本主要由物料在各設備間的流動量以及各設備間的相對距離來決定。如果各設施間的物流量自始至終都是固定不變的，這樣的設施規劃問題稱為靜態設施規劃問題（Static Facility Layout Problem，SFLP）［3］。相反，如果各設備間的物流量在不同的階段內均有所變化，靜態設施規劃的方法就顯得無能為力了，為了維持、甚至提高制造系統的效率，就需要一種新的規劃方式，即根據不同時期生產系統中物流量的變化重新規劃生產系統或調整生產系統結構，這就是多階段設施規劃問題（Multistage Facility Layout Problem，MFLP）。近幾年，有不少學者對多階段設施規劃進行了研究。不同企業的生產制造系統劃分階段有不同的標準，可以以星期、月或年為單位劃分。在一個階段內，各設備間的物流量假定是恒定不變的。但是在不同的階段，由于生產系統發生了變化，各設備間的物流量會有所改變，這就需要在每個階段初期對設施布局進行重新設計［1］。導致設施間的物流量發生變化的因素主要有［4］：

（1）改變現有產品的設計；

（2）產品種類的增加或減少；

（3）現有生產設備的更換；

（4）產品生命周期的變化；

（5）產品生產計劃和產量的改變。

因此，有必要設計一個柔性生產系統來應對以上因素對設備間物流量變化的影響。據統計，有1/ 3的美國企業平均每兩年都會對生產系統做一次大的調整［5］。傳統上，設施規劃的有效應與各設備間的物流量有關。物料搬運成本的最小化通常被當作評價設施規劃有效性的標準。然而對生產系統進行調整或重新規劃也需要一定的費用。因此，就需要在物料搬運成本和生產系統的重新規劃成本之間取得一個權衡。這就是多階段設施規劃需解決的主要問題。

許多學者都對設施規劃進行過研究［6］。王盈、吳正佳［7］介紹了車間設備布局的一般原則，并依據設施規劃的原則對鋸片車間的重新布局方式作了系統的闡述。董海［8］基于系統布置設計SLP原理，通過計算機仿真技術，并采用Visual Basic語言編寫程序，提出了對新建工廠設施布置的合理方案。王鳳仙、王英利［9］應用SLP原理分析了網卡的生產過程和物流系統，提出：根據各部門之間的物流和非物流關系進行規劃，使用計算機技術可以得到更合理、有彈性的車間布置。韓慶蘭［10］綜合考慮物流系統總成本與顧客滿意度之間的平衡，提取出對物流設施規劃有重要影響的因素，將其中顧客滿意度這一定性因素用量化的服務水平代替，由此建立一個多目標規劃模型。馬彤兵、馬可［11］把精益生產的思想引入了設施規劃改進程序模型中，通過該模型對一個具體的實例（某變壓器廠的箱體車間）進行的深入而系統的分析，對該車間的設備進行了重新布置，同時對操作人員也進行了相應的調整。

從以上文獻資料可以看出，國內大多數文獻都是針對靜態設施規劃問題進行的研究。人們開始關注多階段設施規劃問題是近些年的事。Rosenbaltt［12］第一個對多階段設施規劃問題進行了建模和求解。他是用多階段規劃的模型對MFLP問題進行了最優化求解。在求解過程中，多階段規劃模型中的每一個階段與設施規劃中的不同階段相對應。相比于SFLP問題，MFLP問題的求解會更加復雜。對于一個有N個設備T個階段的生產系統來說，將會有（N！）T種布局方案。因此，只有在問題規模不很大的時候才有可能在合理的運算時間內求出最優解。對于規模較大的MFLP問題，常用啟發式算法進行求解。Lacksonen和Enscore［13］將一系列的靜態設施規劃算法進行了修正，建立了一個改進的二次規劃模型。Urban［14］提出了一種基于定量布置技術（Computerized Relationship Facilities Technique，CRAFT）的啟發式算法。Balakrishnan［15］提出了兩種啟發式算法改進了Urban的最速下降成對交換法。Conway和Venkataramanan［16］應用改進的遺傳算法解決MFLP問題。Balakrishinan［17］提出了一種混合遺傳算法。Kaku和Mazzola［18］提出了一種基于禁忌搜索法的啟發式算法解決MFLP問題。模擬退火法也同樣被用于解決MFLP問題［19］。Erel等［20］人使用多階段規劃和模擬退火法相結合的方法對MFLP問題提出了一系列啟發式算法。Kochhar和Heragu［21］研究了多層多階段設施規劃問題。Balakrishman和Cheng［22］對現有的MFLP問題的各種算法進行了比較，并詳細分析了各種算法的優劣性。

之前的文獻很少考慮財務預算方面的約束。然而，我們應注意到，如果考慮到了財務預算方面的限制，某些階段中的重新規劃方案就變得不可行了。因此，財務預算的約束對多階段設施規劃方案的選擇會產生顯著的影響［23］。

2 MFLP問題描述和數學建模

SFLP問題假設各設備間的物流量是恒定不變的，因此它的規劃方案是要使各設備間總的物料搬運費用最小化。而MFLP問題不僅要在每一個階段確定一個靜態布局方案，而且還要決定在下一個階段是否進行重新規劃來改變生產系統的現有布局以提高生產系統的運作效率。如果對生產系統進行重新布局規劃，就會產生重新布局規劃的成本。這部分成本是由于設施的移動、產量的變化或對相關人員或器材的特殊需求等原因導致的［24］。如果重新規劃的成本比較低，我們就傾向于在每個階段重新規劃生產系統以維持它的高效率。相反的，如果重新規劃的費用過高，我們就有可能維持現有規劃方案不變。本文考慮了財務預算對MFLP的影響，在某些階段，由于財務預算的限制，即使重新規劃生產系統是有利的，也無法真正實施。

本文對MFLP問題的假設如下：

（1）各設備間的物流量隨每個階段的變化而變化，而在每個階段內物流量恒定不變；

（2）每個設備具有相同的形狀和面積；

（3）生產系統中設施能擺放的位置是確定的，并且和設施的數量相同；

（4）各位置間的相對距離是預先確定的。

MFLP問題的總成本是由各設備間的總物料搬運成本與各時期生產系統重新規劃成本組成。因此，MFLP的目標函數通常被定義成各設備間的總物料搬運成本與各時期生產系統重新規劃成本在各個階段總和的最小化［7-8，20］。本文的MFLP數學模型如下所示：

其中，i，k表示生產系統中的設備，j，l表示生產系統中設備能夠擺放的位置，ctjk表示在階段t中i，k兩設備間的單位物料搬運成本（兩設備間一單位物料搬運一單位距離所花費的成本），ftik在階段t中i，k兩設備間的物流量，dtjl表示在階段t中j，l兩位置的距離，Atijl表示在階段t中將設備i從位置j移動到位置l所需要的固定成本，LB表示上一階段剩余財務預算，B表示當前階段財務預算。

在以上模型中，公式（1）即目標函數，是要求取各階段的物料搬運成本以及生產系統重新規劃成本之和的最小值；公式（2）說明在各個階段，每一個設備只能放在一個位置；公式（3）說明在各個階段，每一個位置只能容納一個設備；公式（4）說明只有當設備改變位置時，才會產生重新規劃成本；公式（5）說明Xtij屬于0，1變量，當在階段t中設備i處于位置j上時，Xtij=1，否則Xtij=0；公式（6）說明Ytijl也屬于0，1變量，當在階段t的開始設備i從位置j移動到了位置l時，Ytijl=1，否則Ytijl=0。公式（5）說明生產系統重新規劃成本要滿足預算要求。

對于MFLP問題，我們假設在每個階段內各設設備的物流量是恒定不變的。因此，在每個階段內的設施規劃問題均可看作是一個SFLP問題。我們用πt表示在階段t中生產系統中N個設備、N個位置的布局方案，即πt=（π1t，π2t，…，πNt）。其中πit表示在階段t中位置i上的設備（i=1，2，…，N）。因此，MFLP問題的一個求解方案便可表示成：

π=｛π1，π2，…，πT｝=｛（π11，π21，…，πN1），（π12，π22，…，πN2），…，（π1T，π2T，…，πNT）｝

以圖1為例，圖1描述了一個有6個設備3階段的MFLP問題示例。在階段1，設施6，4，2，1，5，3被分別安置在1，2，3，4，5，6號位置。階段1的布局可表示成π1=（6，4，2，1，5，3）。階段2和階段3以此類推。因此此示例的3個階段總的規劃方案可表示成：

π=｛（6，4，2，1，5，3），（5，4，2，1，6，3），（5，4，3，1，6，3）｝

在階段2中，設備5和設備6調換了位置，因此階段2的重新規劃成本就是將設備6從位置1移到位置5的費用加上將設備5

從位置5移到位置1的費用。由于2，3兩階段的布局沒有改變，所以在階段3并不產生重新規劃成本。而且每個階段的物料搬運成本也沒有變化。這樣便可計算出MFLP整體規劃的總成本。

圖1 一個6設施3階段的MFLP問題示例

2 混和蟻群算法對MFLP問題的求解

2.1 蟻群算法描述

蟻群算法（Ant Colony Optimization Algorithm，ACO）是近年來新發展起來的一種啟發式算法，由Dorigo等［25］在20世紀90年代首先提出，而后又進行了一系列改進。由于蟻群算法采用分布式并行計算機制，具有較強的魯棒性，容易與其他算法結合等優點，一經提出，立即受到各領域學者的重視。近幾年，蟻群算法被應用于加工車間調度問題、圖形著色問題、二次分配問題、車輛路徑問題等一系列NP難問題［26］。

蟻群算法模仿了自然界中螞蟻覓食的行為，主要通過螞蟻群體之間的信息傳遞而達到尋優的目的。螞蟻在移動過程中會釋放出一種稱作“信息素”的化學物質。信息素濃度越高，對螞蟻的吸引力就越強，因此螞蟻更傾向于選擇信息素濃度高的路徑。一開始每個螞蟻并不知道食物在何處，只是在本身所能見到的局部范圍內搜索，并以一定的概率向其他螞蟻留下的信息素濃度高的方向移動，同時自己也釋放信息素。如果許多螞蟻都經過了同一條路徑，則此路徑上的信息素濃度便會升高，后來的螞蟻就更傾向于選擇這條路徑。同時所有螞蟻釋放的信息素將以一定速率揮發，因此經過一段時間后，最短路徑上的信息素濃度會越來越高，從而形成一種正反饋，因此到最后所有的螞蟻都會選擇最短的路徑去尋找食物。這一過程如圖2所示。

圖2 螞蟻尋找最短路徑過程示意圖：（a）初態；（b）階段一；（c）階段二；（d）終態：螞蟻集中于最短路徑

為了能夠有效的應用蟻群算法解決MFLP問題，我們可將蟻群算法解空間看作一種網狀結構。圖2描述了一個2階段3設備的網狀結構可行解示意圖。在這一結構中假設只有一只螞蟻（即一個可行解）。在第一階段，螞蟻所經過的位置1-2-3中的設施為2-1-3，。而在第二階段，螞蟻所經過的位置1-2-3中的設施為3-2-1。因此，這兩個階段的可行解便可表示成一個字符串的形式：2-1 -3-3-2-1。這一可行解也可表示成結構書的形式如圖3所示。

圖3 MFLP問題蟻群算法解空間的網絡表示

2.2 蟻群算法求解MFLP問題的步驟

蟻群算法的核心內容包括以下三部分：（1）選擇機制：某條路徑上留下的信息素越多，此路徑被選擇的概率越大；（2）更新機制：某條路徑上的信息素濃度會隨著螞蟻經過數量的增加而變大，同時信息素也會逐漸的揮發；（3）協調機制：螞蟻之間通過信息素交換信息并相互影響。

求解過程中所用字母的含義如下：

M：蟻群規模（螞蟻的數量）

m：螞蟻序數（m=1，…，M）

N：設施（位置）的數量

i，z：生產系統中的設備（i，z=1，…，N）

j：生產系統中的位置（j=1，…，N）

S：階段總數

t：階段

F：目標函數

BLt：階段t的最優布局方案

r：失敗迭代計數器，記錄連續迭代連續失敗的次數

R：失敗迭代的上限

Pijt：信息素濃度（在階段t中將設施i放置在位置j中的傾向性）

Q：信息素更新參數

W：交換次數。

α：信息素揮發率

u：ACO流程迭代次數

U：ACO流程迭代上限

用蟻群算法求解MFLP問題的步驟如下：

Ⅰ.確定初始解

令Fbest=一個很大的數。從第一只螞蟻開始（m=1）對每一只螞蟻重復進行如下操作（重復M次）：

步驟1：隨機確定第一階段的設備布局方式，即將所有的設備隨機排列。令之后的每一階段的設備布局方式不變，因此其重新規劃成本為0（π1=π2=…=πS）。

步驟2：改進過程。令r=0。計算初始布局方案的目標函數（Fm）。隨機選擇一個階段，在此階段中隨機選擇2個設備進行交換。檢驗是否滿足預算約束條件。若滿足條件，計算交換設備后的目標函數（Fm'）。若Fm＞Fm'，則接受改變后的布局方式，并令r=0。如果Fm＜Fm'或不滿足預算約束條件，就要重新選擇兩個設備進行交換，并令r=r+1。

步驟3：更新最優解。如果第m只螞蟻的目標函數（Fm）優于現階段最優解，即Fm＜Fbest，則要更新最優解（Fbest=Fm，BLt=πt，t=1，…，S），否則，最優解不更新。

步驟4：更新螞蟻數量（m=m+1），返回步驟1。

根據以上步驟，可確定問題的一個初始解。此時各路徑上的信息素濃度為Pijt=Pijt+Q/Fbest（i= 1，…，N，t=1，…，S，Q表示所規定的目標函數的上限）。

Ⅱ.ACO流程

設置參數m=1，r=0。重復操作以下步驟，直到迭代次數達到迭代上限為止：

步驟1：更新初始解（令πt=BLt，t=1，…，S）。

步驟2：對每一只螞蟻重復以下操作：

步驟2.1：交換過程。重復以下交換過程W次：

首先，隨機選擇一個階段，并在所選階段中隨機選擇一個設備u。然后，再選擇一個設備v。選擇設備v的概率與設備u和設備v的相關信息素濃度（Pu，lc（v），t+Pv，lc（u），t）成正比（lc（u）表示設備u的位置）。最后，交換所選兩設備的位置。需要強調一點：設備v與設施u可以相同。當所選兩設備相同時，說明設備的位置沒有改變。

根據信息素的濃度選擇設備v的具體操作如下：令

任意取q∈（0，1），選擇滿足以下不等式的第i個設備作為設施v：

步驟2.2：改進過程。與“Ⅰ.確定初始解”中的“改進過程”步驟完全相同。

步驟2.3：更新信息素。首先將信息素進行揮發（Pijt=Pijt*α，i=1，…，N，j=1，…，N，t= 1，…，S），再聚集信息素（Pijt=Pijt+Q/Fbest*α，i =1，…，N，j=1，…，N，t=1，…，S）。

步驟2.4：更新最優解。如果第m只螞蟻的目標函數優于當前最優解（Fm＜Fbest），則要將最優解進行更新（Fbest=Fm，BLt=πt，t=1，…，S）。這樣，下一只螞蟻就可以使用改進后的最優解作為其初始解了。再次揮發信息素（Pijt=Pijt*α，i=1，…，N，j=1，…，N，t=1，…，S）和聚集信息素（Pijt=Pijt+Q/Fbest，i=1，…，N，j=1，…，N，t =1，…，S）。由于消除了參數α對信息素增加的影響，此時信息素濃度增加的更多。這樣一來最優解被選中的概率會增加。最后令r=0。

步驟2.5：若螞蟻數量m=M則繼續執行以下步驟，否則令m=m+1，返回步驟2.1。

步驟3：如果最優解沒有更新，則令r=r+1。如果r=R，則清空所有信息素（Pijt=0，i=1，…，N，j=1，…，N，t=1，…，T）并重新聚集信息素（Pijt=Pijt+Q/Fbest，i=1，…，N，j=1，…，N，t =1，…，S）。

步驟4：返回步驟1，進行下一輪迭代。

以上ACO算法的流程圖如圖4所示。

根據以往實驗結論，以上步驟所需參數的取值如下：R=（N*S）/2，W=（N*S）/2，α=0.5，β =1。

2.3 改進的混和蟻群算法(HACO)求解MFLP問題的步驟

本文在簡單蟻群算法的基礎上加入了模擬退火法（SA），形成了混和蟻群算法（Hybrid Ant Colony Optimization Algorithm，HACO），從而改進了原始蟻群算法的性能。

模擬退火法是一種解決混合優化問題的隨機方法，它模擬了金屬煅燒退火的過程。在這一過程中，一個金屬固體被加熱到其融化，而后它的溫度不斷降低直到達到一種最低能量的狀態（或稱基態）。如果初始溫度不夠高或溫度下降的過快，固體達到基態時就會產生多種缺陷。Kirkpatrick等［27］第一次運用SA解決混合優化問題。Wilhelm和Ward［28］運用SA解決SFLP問題。Baykasoglu和Gindy［29］第一次運用SA解決MFLP問題。

本文的混合蟻群算法就是用模擬退火法來替換上述蟻群算法中的兩次“改進過程”。本文中的模擬退火法的步驟如下：

步驟1：定義SA參數：令T0=初始溫度；T=當前溫度；γ=冷卻率；AM=2（N）（T2）=每一個溫度下的最大設備交換次數；Tmin=0.01=最低溫度。

步驟2：初始化溫度變化計數器k=1。

步驟3：對于初始布局方案π=｛π1，π2，…，πS｝，計算其目標函數f（π），令BS=π，Fbest=f（π）。

步驟4：如果當前溫度T≤Tmin，即停止迭代，并返回BS=π，Fbest=f（π）。否則，初始化設施交換次數計數器a=0，并設置當前溫度T=T0γk-1。

圖4 ACO算法流程圖

步驟5：任選一階段t，在階段t中任意交換兩個設施的位置，得到一新的規劃方案π′。

步驟6：令a=a+1，計算目標函數的變化量Δf =f（π′）-f（π），如果Δf＜0，或Δf＞0且x= random（0，1）＜P（Δf）=exp（-Δf/S），則接受這一新方案，令π=π′。若Fbest＞f（π），則令Fbest=f（π），否則，拒絕這一新方案。

步驟7：如果a≥AM，更新k=k+1，返回步驟3；否則，返回步驟4。

以上步驟的流程圖如圖5所示。

以上模擬退火法中的各個參數值的確定方法如下：初始溫度T0由公式P（Δf）=ex p（-Δf/T0）來確定，根據以往的實證研究［3］，一般設Δf=0.10 f（π），P（Δf）=0.25， 因此，T0=-0.10 f（π）/ln（0.25）。我們分別設γ=0.99，AM= 2（N）（S2）。

3 數據分析

在這一節中，我們利用Balakrishnan和Cheng［30］的文獻資料中的48組檢測數據來對本文所提出的簡單蟻群算法（ACO）和改進的蟻群算法（HACO）的運算效率進行檢驗。這48組數據分三種類型，分別是每組6臺設備、每組15臺設備和每組30臺設備，每種類型各占16組。在每種類型的數據中，階段數為5和階段數為10的數據各占一半，均為8組。

圖5 SA算法流程圖

表1至表3描述了本文提出的簡單蟻群算法和改進的混和蟻群算法與其他一些用于解決MFLP問題的典型的啟發式算法進行了對比，其他啟發式算法包括Baykosaglu和Gindy［19］提出的模擬退火法（SA），Balakrishnan［17］提出的混合遺傳算法（GA），Erel［20］提出的多階段規劃方法（DP）。為了提高算法的精確度，本文將每一個參與檢驗的算法對每一組檢驗數據均計算3次，并取其最優解。表1至表3顯示了每一種算法對每一個數據經過3次計算后的最優解。簡單蟻群算法和混合蟻群算法的數據分別填入“ACO”和“HACO”兩列中，而模擬退火法、混合遺傳算法以及多階段規劃方法所得到的最優解數據分別填入“SA”，“GA”和“DP”列中。三個表格中的粗體數字均表示每一組數據達到最優解的計算結果。

由表1可知，在6臺設備的數據中，對于階段數為5的8個數據（數據1～8），本文提出的ACO和HACO兩種蟻群算法均得到了最優解。其次是GA和DP算法，分別得到了7次和6次最優解，SA算法最少，僅得到2次最優解；對于階段數為10的8數據（數據9～16），ACO和HACO兩種蟻群算法全部得到最優解，其次是DP算法，得到6次最優解，而SA算法沒有出現最優解。因此，對于表1中的數據，ACO和HACO是兩個最優算法。

由表2可知，在15臺設備的數據中，對于階段數為5的8個數據（數據17～24），HACO算法得到了4次最優解，而ACO算法僅得到2次最優解，其他算法（SA、GA和DP）均沒有得到最優解）；對于階段數為10的8個數據（數據25～32），HACO算法得到了5次最優解，而ACO算法僅得到1次最優解，其他三種算法沒有得到最優解。由此可見，在15臺設備的數據中，HACO算法明顯優于其他算法。

由表3可以看出，在30臺設備的數據中，對于階段數為5的8個數據（數據33～40），HACO算法得到了6次最優解，其次是ACO和GA兩種算法，均得到了1次最優解，而其他算法沒有得到最優解；對于階段數為10的8個數據（數據41～48），HACO算法得到了4次最優解，ACO和GA算法各得到2次最優解，而其他算法均無最優解。由此可見，在30臺設備的數據中，HACO算法仍然是最優算法，其次是ACO和GA兩種算法。

通過以上分析可以看出，在這48個設施規劃數據中，SA、GA、DP和ACO方法分別得到了2次、13次、12次和22次最優解，而HACO方法則得到了36次最優解，其最優解的數量遠遠多于其他方法。從表1至表3中的數據我們可以看出，本文所提出的HACO方法無論是解決小規模設施規劃問題還是大規模問題，均能表現出良好的性能。而其他方法在解決大規模設施規劃問題時較HACO方法則有較大差距。可證明本文所提出的HACO方法是解決帶有財務預算約束的多階段設施規劃問題的一種有效方法。

4 結語

本文構建了帶有財務預算約束的多階段設施規劃模型，并提出了兩種蟻群算法來對此模型進行求解。先用簡單蟻群算法對此模型進行求解。而后再在簡單蟻群算法的基礎上加以改進，融入了模擬退火法，形成了混和蟻群算法，從而提高了蟻群算法的計算性能。利用Balakrishnan和Cheng［26］的48組監測數據，將本文提出的混合蟻群算法與其他一些用于解決MFLP問題的啟發式算法進行比較，實踐證明，本文所提出的混合蟻群算法能夠有效的解決帶有財務預算約束的MFLP問題。

表1 6臺設備的設施規劃問題的計算結果

表2 15臺設備的設施規劃問題的計算結果

表3 30臺設備的設施規劃問題的計算結果

本文認為，在本文研究的基礎上，還有一些后續問題值得進一步的研究和探討。這些問題包括：

（1）本文在模型構建中，僅以成本最小化作為模型目標函數。今后的研究可考慮建立并求解多目標模型；

（2）本文僅研究了生產車間的單層多階段設施規劃問題，今后可進一步研究多層生產車間的設施規劃問題；

（3）在本文提出的算法的基礎上，研究是否還有其他更加有效的算法解決此類問題。

［1］Tompkins JA，White JA，Bozer YA，et al.Facilities planning［M］.New York：Wiley，1996.

［2］Ulutas B H，Islier A A.A clonal selection algorithm for dynamic facility layout problems［J］.Journal of Manufacturing Systems，2009，28（4）：123-131.

［3］Mc Kendall Jr A R.，Shang Jin.Hybrid ant systems for the dynamic facility layout problem［J］.2006，33（3）：790-803.

［4］Shore R H，Tompkins J A.Flexible facilities design［J］.AIIE Transactions，1980，12（2）：200-205.

［5］Gupta T，Seifoddini H.Production data based similarity coefficient for machine-component grouping decisions in the design of cellular manufacturing system［J］.International Journal of Production Research，1990，28（7）：1247-1269.

［6］Liggett R S.Automated facilities layout：Past，present and future［J］.Automation in Construction，2000，9（2）：197-215.

［7］王盈，吳正佳，王魁.鋸片制造車間設施規劃設計［J］.機械設計與制造，2008，1：229-230.

［8］董海，計算機仿真技術在設施規劃與設計中的應用［J］.沈陽大學學報.2004，16（4）：35-37.

［9］王鳳仙，王英利.基于SLP法對網卡車間的物流研究與設施規劃［J］.內蒙古科技與經濟，2009，9：129-131.

［10］韓慶蘭.物流設施規劃的多目標優化模型［J］.控制與決策，2006，8：957-960.

［11］馬彤兵，馬可.基于精益生產的車間設施規劃改善設計［J］.組合機床與自動化加工技術，2005，6：110-112.

［12］Rosenbaltt M J.The dynamics of plant layout［J］. Management Science，1986，32（1）：76-85.

［13］Lacksonen T A，Enscore E E.Quadratic assignment algorithms for the dynamic layout problem［J］.International Journal of Production Research，1993，31（3）：503-517.

［14］Urban T L.A heuristic for the dynamic facility layout problem［J］.IIE Transactions 1993，25（4）：57-63.

［15］Balakrishnan J，Cheng C H，Conway G.An improved pair-wise exchange heuristic for the dynamic plant layout problem［J］.International Journal of Production Research，2000，38（13）：3067-3077.

［16］Conway D G，Venkataramanan M A.Genetic search and the dynamic facility layout problem［J］.Computers and Operations Research，1994，21（8）：955-960.

［17］Balakrishnan J，Cheng C H，Conway D G，et al.A hybrid genetic algorithm for the dynamic plant layout problem［J］.International Journal of Production Economics，2003，86（2）：107-120.

［18］Kaku B K，Mazzola J B.A tabu search heuristic for the dynamic plant layout problem［J］.INFORMS：Journal on Computing，1997，9（4）：374-384.

［19］Baykasoglu A，Gindy N N Z.A simulated annealing algorithm for dynamic layout problem［J］.Computers and Operations Research，2001，28（4）：1403-1426.

［20］Erel E，Ghosh J B，Simon J T.New heuristic for the dynamic layout problem［J］.Journal of the Operational Research Society，2003，54（12）：1202-1275.

［21］Kochhar J S，Heragu S S.Facility layout design in a changing environment［J］.International Journal of Production Research，1999，37（11）：2429-2446.

［22］Balakrishnan J，Cheng C H.Dynamic layout algorithms：a state-of-the-art survey［J］.Omega：International Journal of Management Science，1998，26：507 -21.

［23］Balakrishnan J，Jacobs F R，Venkataramanan M A. Solutions for the constrained dynamic facility layout problem［J］.European Journal of Operational Research，1992，57（2）：280-286.

［24］Mc Kendall Jr A R.，Shang Jin，Kuppusamy S.Simulated annealing heuristics for the dynamic facility layout problem［J］.Computers&Operations Research，2006，33（8）：2431-2444.

［25］Dorigo M，Maniezzo V，Colorni A.Positive feedback as a search strategy［R］.Technical Report，1991.

［26］Baykasoglu A，Dereli T，Sabuncu I.An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems［J］.The International Journal of Management Science，2006，34（4）：385-396.

［27］Kirkpatrick S，Gelatt C D，Vecchi M P.Optimization by simulated annealing［J］.Science，1983，220（4598）：671-80.

［28］Wilhelm M R，Ward T L.Solving quadratic assignment problems by simulated annealing［J］.IIE Transactions，1987，19（1）：107-19.

［29］Baykasoglu A，Gindy N N Z.Asimulated annealing algorithm for dynamic facility layout problem［J］. Computers&Operations Research，2001，28（14）：1403 -26.

［30］Balakrishnan J，Cheng C H.Genetic search and the dynamic layout problem［J］.Computers&Operations Research，2000，27（6）：587-93.

A Research for Multi-stage Facility Layout Problem of Production System Based on Hybrid Ant Colony Optimization Algorithm

LI Hui，ZHU Lian-yu，QI Er-shi
（The College of Management and Economics，Tianjin University，Tianjin 300072，China）

Facility layout problem mainly studies the layouts of manufacturing facilities，which aims at reducing the material handling costs in the plant.An effective facility layout method can contribute to improve the overall operation efficiencies during the process of manufacturing.With the increasingly fierce competition in the market，the market environment is constantly changing.Manufacturing enterprises must continuously redesign the facility layout so as to adapt the changing production demands and reduce the cost.This problem requires the solution of Dynamic facility layout problem（DFLP）.In this paper，an improved hybrid ant colony optimization（HACO）is proposed to solve the DFLP with budget constraints. The HACO algorithm proposed by this paper can show good performance both for small and for large scale facility layout problems.There exists great gap between HACO and the other algorithms on solving large scale facility layout problems.Therefore，HACO is an effective method to solve dynamic facility layout problem with budget constraints.

dynamic facility layout problem；hybrid ant colony algorithm；budget constraint

F207

：A

1003-207(2014)01-0074-10

2012-02-01；

2012-11-21

國家自然科學基金面上項目（70671072）

朱連宇（1970-），男（滿族），遼寧人，天津大學管理與經濟學部，博士生，研究方向：精益生產.