基于混合蟻群算法的生產(chǎn)系統(tǒng)設(shè)施規(guī)劃問題研究

李 輝，朱連宇，齊二石

（天津大學(xué)管理與經(jīng)濟(jì)學(xué)部，天津300072）

基于混合蟻群算法的生產(chǎn)系統(tǒng)設(shè)施規(guī)劃問題研究

李 輝，朱連宇，齊二石

（天津大學(xué)管理與經(jīng)濟(jì)學(xué)部，天津300072）

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

多階段設(shè)施規(guī)劃；混合蟻群算法；財(cái)務(wù)預(yù)算約束

1 引言

當(dāng)今世界，全球的競(jìng)爭(zhēng)越來越體現(xiàn)在經(jīng)濟(jì)和科技實(shí)力的競(jìng)爭(zhēng)，而技術(shù)創(chuàng)新則日益成為促進(jìn)經(jīng)濟(jì)增長(zhǎng)和提高科技競(jìng)爭(zhēng)力的關(guān)鍵。技術(shù)獲取模式作為企業(yè)技術(shù)戰(zhàn)略的重要一環(huán)，對(duì)企業(yè)長(zhǎng)遠(yuǎn)發(fā)展意義重大。

設(shè)施規(guī)劃問題主要研究生產(chǎn)設(shè)備的布局規(guī)劃，從而減小廠區(qū)內(nèi)的物料搬運(yùn)成本。據(jù)統(tǒng)計(jì)資料表明，一個(gè)生產(chǎn)車間的物料搬運(yùn)成本占整個(gè)生產(chǎn)運(yùn)作成本的20%～50%，占產(chǎn)品生產(chǎn)總成本的15%-70%［1］。在一個(gè)生產(chǎn)車間中，一個(gè)有效的設(shè)施規(guī)劃能夠調(diào)整設(shè)備間的物流量，從而使每個(gè)設(shè)備在正確的時(shí)間得到正確數(shù)量的物料，這樣既可以減少在制品的庫(kù)存量，又能夠防止廠房中機(jī)器設(shè)備的過度使用，減少物流成本。一個(gè)有效的設(shè)施規(guī)劃有利于生產(chǎn)過程中整體運(yùn)作效率的提高［2］。

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

（1）改變現(xiàn)有產(chǎn)品的設(shè)計(jì)；

（2）產(chǎn)品種類的增加或減少；

（3）現(xiàn)有生產(chǎn)設(shè)備的更換；

（4）產(chǎn)品生命周期的變化；

（5）產(chǎn)品生產(chǎn)計(jì)劃和產(chǎn)量的改變。

因此，有必要設(shè)計(jì)一個(gè)柔性生產(chǎn)系統(tǒng)來應(yīng)對(duì)以上因素對(duì)設(shè)備間物流量變化的影響。據(jù)統(tǒng)計(jì)，有1/ 3的美國(guó)企業(yè)平均每?jī)赡甓紩?huì)對(duì)生產(chǎn)系統(tǒng)做一次大的調(diào)整［5］。傳統(tǒng)上，設(shè)施規(guī)劃的有效應(yīng)與各設(shè)備間的物流量有關(guān)。物料搬運(yùn)成本的最小化通常被當(dāng)作評(píng)價(jià)設(shè)施規(guī)劃有效性的標(biāo)準(zhǔn)。然而對(duì)生產(chǎn)系統(tǒng)進(jìn)行調(diào)整或重新規(guī)劃也需要一定的費(fèi)用。因此，就需要在物料搬運(yùn)成本和生產(chǎn)系統(tǒng)的重新規(guī)劃成本之間取得一個(gè)權(quán)衡。這就是多階段設(shè)施規(guī)劃需解決的主要問題。

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

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

之前的文獻(xiàn)很少考慮財(cái)務(wù)預(yù)算方面的約束。然而，我們應(yīng)注意到，如果考慮到了財(cái)務(wù)預(yù)算方面的限制，某些階段中的重新規(guī)劃方案就變得不可行了。因此，財(cái)務(wù)預(yù)算的約束對(duì)多階段設(shè)施規(guī)劃方案的選擇會(huì)產(chǎn)生顯著的影響［23］。

2 MFLP問題描述和數(shù)學(xué)建模

SFLP問題假設(shè)各設(shè)備間的物流量是恒定不變的，因此它的規(guī)劃方案是要使各設(shè)備間總的物料搬運(yùn)費(fèi)用最小化。而MFLP問題不僅要在每一個(gè)階段確定一個(gè)靜態(tài)布局方案，而且還要決定在下一個(gè)階段是否進(jìn)行重新規(guī)劃來改變生產(chǎn)系統(tǒng)的現(xiàn)有布局以提高生產(chǎn)系統(tǒng)的運(yùn)作效率。如果對(duì)生產(chǎn)系統(tǒng)進(jìn)行重新布局規(guī)劃，就會(huì)產(chǎn)生重新布局規(guī)劃的成本。這部分成本是由于設(shè)施的移動(dòng)、產(chǎn)量的變化或?qū)ο嚓P(guān)人員或器材的特殊需求等原因?qū)е碌模?4］。如果重新規(guī)劃的成本比較低，我們就傾向于在每個(gè)階段重新規(guī)劃生產(chǎn)系統(tǒng)以維持它的高效率。相反的，如果重新規(guī)劃的費(fèi)用過高，我們就有可能維持現(xiàn)有規(guī)劃方案不變。本文考慮了財(cái)務(wù)預(yù)算對(duì)MFLP的影響，在某些階段，由于財(cái)務(wù)預(yù)算的限制，即使重新規(guī)劃生產(chǎn)系統(tǒng)是有利的，也無法真正實(shí)施。

本文對(duì)MFLP問題的假設(shè)如下：

（1）各設(shè)備間的物流量隨每個(gè)階段的變化而變化，而在每個(gè)階段內(nèi)物流量恒定不變；

（2）每個(gè)設(shè)備具有相同的形狀和面積；

（3）生產(chǎn)系統(tǒng)中設(shè)施能擺放的位置是確定的，并且和設(shè)施的數(shù)量相同；

（4）各位置間的相對(duì)距離是預(yù)先確定的。

MFLP問題的總成本是由各設(shè)備間的總物料搬運(yùn)成本與各時(shí)期生產(chǎn)系統(tǒng)重新規(guī)劃成本組成。因此，MFLP的目標(biāo)函數(shù)通常被定義成各設(shè)備間的總物料搬運(yùn)成本與各時(shí)期生產(chǎn)系統(tǒng)重新規(guī)劃成本在各個(gè)階段總和的最小化［7-8，20］。本文的MFLP數(shù)學(xué)模型如下所示：

其中，i，k表示生產(chǎn)系統(tǒng)中的設(shè)備，j，l表示生產(chǎn)系統(tǒng)中設(shè)備能夠擺放的位置，ctjk表示在階段t中i，k兩設(shè)備間的單位物料搬運(yùn)成本（兩設(shè)備間一單位物料搬運(yùn)一單位距離所花費(fèi)的成本），ftik在階段t中i，k兩設(shè)備間的物流量，dtjl表示在階段t中j，l兩位置的距離，Atijl表示在階段t中將設(shè)備i從位置j移動(dòng)到位置l所需要的固定成本，LB表示上一階段剩余財(cái)務(wù)預(yù)算，B表示當(dāng)前階段財(cái)務(wù)預(yù)算。

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

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

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

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

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

在階段2中，設(shè)備5和設(shè)備6調(diào)換了位置，因此階段2的重新規(guī)劃成本就是將設(shè)備6從位置1移到位置5的費(fèi)用加上將設(shè)備5

從位置5移到位置1的費(fèi)用。由于2，3兩階段的布局沒有改變，所以在階段3并不產(chǎn)生重新規(guī)劃成本。而且每個(gè)階段的物料搬運(yùn)成本也沒有變化。這樣便可計(jì)算出MFLP整體規(guī)劃的總成本。

圖1 一個(gè)6設(shè)施3階段的MFLP問題示例

2 混和蟻群算法對(duì)MFLP問題的求解

2.1 蟻群算法描述

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

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

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

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

圖3 MFLP問題蟻群算法解空間的網(wǎng)絡(luò)表示

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

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

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

M：蟻群規(guī)模（螞蟻的數(shù)量）

m：螞蟻序數(shù)（m=1，…，M）

N：設(shè)施（位置）的數(shù)量

i，z：生產(chǎn)系統(tǒng)中的設(shè)備（i，z=1，…，N）

j：生產(chǎn)系統(tǒng)中的位置（j=1，…，N）

S：階段總數(shù)

t：階段

F：目標(biāo)函數(shù)

BLt：階段t的最優(yōu)布局方案

r：失敗迭代計(jì)數(shù)器，記錄連續(xù)迭代連續(xù)失敗的次數(shù)

R：失敗迭代的上限

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

Q：信息素更新參數(shù)

W：交換次數(shù)。

α：信息素?fù)]發(fā)率

u：ACO流程迭代次數(shù)

U：ACO流程迭代上限

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

Ⅰ.確定初始解

令Fbest=一個(gè)很大的數(shù)。從第一只螞蟻開始（m=1）對(duì)每一只螞蟻重復(fù)進(jìn)行如下操作（重復(fù)M次）：

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

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

步驟3：更新最優(yōu)解。如果第m只螞蟻的目標(biāo)函數(shù)（Fm）優(yōu)于現(xiàn)階段最優(yōu)解，即Fm＜Fbest，則要更新最優(yōu)解（Fbest=Fm，BLt=πt，t=1，…，S），否則，最優(yōu)解不更新。

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

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

Ⅱ.ACO流程

設(shè)置參數(shù)m=1，r=0。重復(fù)操作以下步驟，直到迭代次數(shù)達(dá)到迭代上限為止：

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

步驟2：對(duì)每一只螞蟻重復(fù)以下操作：

步驟2.1：交換過程。重復(fù)以下交換過程W次：

首先，隨機(jī)選擇一個(gè)階段，并在所選階段中隨機(jī)選擇一個(gè)設(shè)備u。然后，再選擇一個(gè)設(shè)備v。選擇設(shè)備v的概率與設(shè)備u和設(shè)備v的相關(guān)信息素濃度（Pu，lc（v），t+Pv，lc（u），t）成正比（lc（u）表示設(shè)備u的位置）。最后，交換所選兩設(shè)備的位置。需要強(qiáng)調(diào)一點(diǎn)：設(shè)備v與設(shè)施u可以相同。當(dāng)所選兩設(shè)備相同時(shí)，說明設(shè)備的位置沒有改變。

根據(jù)信息素的濃度選擇設(shè)備v的具體操作如下：令

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

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

步驟2.3：更新信息素。首先將信息素進(jìn)行揮發(fā)（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：更新最優(yōu)解。如果第m只螞蟻的目標(biāo)函數(shù)優(yōu)于當(dāng)前最優(yōu)解（Fm＜Fbest），則要將最優(yōu)解進(jìn)行更新（Fbest=Fm，BLt=πt，t=1，…，S）。這樣，下一只螞蟻就可以使用改進(jìn)后的最優(yōu)解作為其初始解了。再次揮發(fā)信息素（Pijt=Pijt*α，i=1，…，N，j=1，…，N，t=1，…，S）和聚集信息素（Pijt=Pijt+Q/Fbest，i=1，…，N，j=1，…，N，t =1，…，S）。由于消除了參數(shù)α對(duì)信息素增加的影響，此時(shí)信息素濃度增加的更多。這樣一來最優(yōu)解被選中的概率會(huì)增加。最后令r=0。

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

步驟3：如果最優(yōu)解沒有更新，則令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，進(jìn)行下一輪迭代。

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

根據(jù)以往實(shí)驗(yàn)結(jié)論，以上步驟所需參數(shù)的取值如下：R=（N*S）/2，W=（N*S）/2，α=0.5，β =1。

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

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

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

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

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

步驟2：初始化溫度變化計(jì)數(shù)器k=1。

步驟3：對(duì)于初始布局方案π=｛π1，π2，…，πS｝，計(jì)算其目標(biāo)函數(shù)f（π），令BS=π，F(xiàn)best=f（π）。

步驟4：如果當(dāng)前溫度T≤Tmin，即停止迭代，并返回BS=π，F(xiàn)best=f（π）。否則，初始化設(shè)施交換次數(shù)計(jì)數(shù)器a=0，并設(shè)置當(dāng)前溫度T=T0γk-1。

圖4 ACO算法流程圖

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

步驟6：令a=a+1，計(jì)算目標(biāo)函數(shù)的變化量Δ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所示。

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

3 數(shù)據(jù)分析

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

圖5 SA算法流程圖

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

由表1可知，在6臺(tái)設(shè)備的數(shù)據(jù)中，對(duì)于階段數(shù)為5的8個(gè)數(shù)據(jù)（數(shù)據(jù)1～8），本文提出的ACO和HACO兩種蟻群算法均得到了最優(yōu)解。其次是GA和DP算法，分別得到了7次和6次最優(yōu)解，SA算法最少，僅得到2次最優(yōu)解；對(duì)于階段數(shù)為10的8數(shù)據(jù)（數(shù)據(jù)9～16），ACO和HACO兩種蟻群算法全部得到最優(yōu)解，其次是DP算法，得到6次最優(yōu)解，而SA算法沒有出現(xiàn)最優(yōu)解。因此，對(duì)于表1中的數(shù)據(jù)，ACO和HACO是兩個(gè)最優(yōu)算法。

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

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

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

4 結(jié)語

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

表1 6臺(tái)設(shè)備的設(shè)施規(guī)劃問題的計(jì)算結(jié)果

表2 15臺(tái)設(shè)備的設(shè)施規(guī)劃問題的計(jì)算結(jié)果

表3 30臺(tái)設(shè)備的設(shè)施規(guī)劃問題的計(jì)算結(jié)果

本文認(rèn)為，在本文研究的基礎(chǔ)上，還有一些后續(xù)問題值得進(jìn)一步的研究和探討。這些問題包括：

（1）本文在模型構(gòu)建中，僅以成本最小化作為模型目標(biāo)函數(shù)。今后的研究可考慮建立并求解多目標(biāo)模型；

（2）本文僅研究了生產(chǎn)車間的單層多階段設(shè)施規(guī)劃問題，今后可進(jìn)一步研究多層生產(chǎn)車間的設(shè)施規(guī)劃問題；

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

［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］王盈，吳正佳，王魁.鋸片制造車間設(shè)施規(guī)劃設(shè)計(jì)［J］.機(jī)械設(shè)計(jì)與制造，2008，1：229-230.

［8］董海，計(jì)算機(jī)仿真技術(shù)在設(shè)施規(guī)劃與設(shè)計(jì)中的應(yīng)用［J］.沈陽(yáng)大學(xué)學(xué)報(bào).2004，16（4）：35-37.

［9］王鳳仙，王英利.基于SLP法對(duì)網(wǎng)卡車間的物流研究與設(shè)施規(guī)劃［J］.內(nèi)蒙古科技與經(jīng)濟(jì)，2009，9：129-131.

［10］韓慶蘭.物流設(shè)施規(guī)劃的多目標(biāo)優(yōu)化模型［J］.控制與決策，2006，8：957-960.

［11］馬彤兵，馬可.基于精益生產(chǎn)的車間設(shè)施規(guī)劃改善設(shè)計(jì)［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，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

國(guó)家自然科學(xué)基金面上項(xiàng)目（70671072）

朱連宇（1970-），男（滿族），遼寧人，天津大學(xué)管理與經(jīng)濟(jì)學(xué)部，博士生，研究方向：精益生產(chǎn).