雙行布局問題的分解策略及啟發(fā)式求解方法

張則強(qiáng)，程文明

（西南交通大學(xué) 機(jī)械工程學(xué)院，四川 成都 610031）

0 引言

設(shè)施布局問題（Facility Layout Problem，F(xiàn)LP）常見于設(shè)施的重組織、車間的新建及機(jī)器設(shè)備的分配等，對(duì)前置時(shí)間、生產(chǎn)效率和成本等都有顯著影響，是制造領(lǐng)域中的一個(gè)重要問題［1］。據(jù)估計(jì)，物料搬運(yùn)相關(guān)費(fèi)用占據(jù)了生產(chǎn)過程中總支出的20%～50%，通過合理布局可節(jié)約10%～30%的物料搬運(yùn)費(fèi)用［2］。此外，良好的布局能有效加快物料處理效率、減少在制品停留、提高企業(yè)生產(chǎn)率。鑒于該問題的重要性和求解難度，設(shè)施布局問題受到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注［3－4］。設(shè)施布局問題作為一個(gè)典型的NP－h(huán)ard組合優(yōu)化問題［1］，啟發(fā)式方法是求解該問題的有效方法，吸引了國內(nèi)外眾多研究人員致力于該領(lǐng)域研究［5－12］。

RAMKUMAR等［5］針對(duì)二次分配模型的設(shè)施布局設(shè)計(jì)問題，提出一種改進(jìn)的迭代快速局部搜索啟發(fā)式方法，并經(jīng)大量算例測(cè)試驗(yàn)證了該方法的有效性。HALE等［6］提出一種新的基于距離的設(shè)施布局構(gòu)造啟發(fā)式方法，用于求解二維設(shè)施布局問題。SINGH等［7］針對(duì)多目標(biāo)設(shè)施布局問題，提出一種基于三層層次分析法（Analytic Hierarchy Process，AHP）的啟發(fā)式方法。文獻(xiàn)［8］提出一種基于流量矩陣的啟發(fā)式算法用于求解單元制造系統(tǒng)中的布局設(shè)計(jì)問題，并經(jīng)大量算法試驗(yàn)驗(yàn)證了方法的有效性。文獻(xiàn)［9］提出一種啟發(fā)式方法用于求解設(shè)施布局問題，該方法用于計(jì)算各設(shè)施間最小距離和修正的設(shè)施接近率，并將該方法集成到計(jì)算機(jī)輔助布局設(shè)計(jì)系統(tǒng)。ASEF－VAZIRI等［10］針對(duì)設(shè)施布局中的物料搬運(yùn)循環(huán)流路徑設(shè)計(jì)問題建立了相關(guān)模型，并提出一種基于鄰域搜索的啟發(fā)式方法求解。文獻(xiàn)［11］提出一種迭代構(gòu)造啟發(fā)式方法，在第一階段先構(gòu)造一個(gè)初始可行布局，在下階段中利用當(dāng)前可行布局來進(jìn)一步構(gòu)造更優(yōu)的布局。Matai等［12］提出一種非貪心系統(tǒng)化鄰域搜索啟發(fā)式方法，用于求解多目標(biāo)設(shè)施布局問題；該啟發(fā)式方法能融合超過2個(gè)的定量或定性化目標(biāo)，取得了良好的求解效果。國內(nèi)研究方面，鎖小紅和劉戰(zhàn)強(qiáng)［13］對(duì)制造系統(tǒng)設(shè)備布局的建模理論與求解方法進(jìn)行了全面闡述，為布局設(shè)計(jì)提供了很好的參考。應(yīng)保勝等［14］針對(duì)敏捷制造車間機(jī)器布局提出一種啟發(fā)式算法，該方法采用深度優(yōu)先的智能回溯策略，以設(shè)備間零件流的傳輸信息為啟發(fā)式知識(shí)，可有效解決布局優(yōu)化問題。文獻(xiàn)［15］針對(duì)單行布局問題展開了仿真研究，利用QUEST軟件對(duì)單行布局的三種布局形式進(jìn)行仿真，并對(duì)仿真結(jié)果進(jìn)行了分析，得出線形布局具有面積利用率高等結(jié)論。郭源源等［16］針對(duì)車間布局設(shè)計(jì)，提出將粒子群優(yōu)化算法與系統(tǒng)化布置設(shè)計(jì)法相結(jié)合的求解方法，以最小化設(shè)備間搬運(yùn)成本，該算法具有很好的求解性能。

上述文獻(xiàn)為設(shè)施布局問題及啟發(fā)式方法研究提供了很好的參照，但其研究主要集中于設(shè)施布局問題被描述為二次分配問題（Quadratic Assignment Problem，QAP）［5，7，12］、單行布局問題（Single Row Layout Problem，SRLP）［11，14－15］等模型的情形，這些模型對(duì)問題作了較多假設(shè)和簡(jiǎn)化，在相應(yīng)情形下取得了很好的結(jié)果，但在某些情況下并不能很好地反映實(shí)際情形。

當(dāng)前車間布局中廣泛應(yīng)用的雙行布局形式，具有占地空間小、設(shè)備利用率高、物流運(yùn)輸路線短等優(yōu)點(diǎn)，尤其適用于柔性制造系統(tǒng)中，它利用自動(dòng)導(dǎo)引小車（Automated Guided Vehicle，AGV）系統(tǒng)進(jìn)行物料或零件的輸送，直線型的布局方式使得AGV系統(tǒng)運(yùn)行更有效率。CHUNG等［17］于2010年首先提出雙行布局問題（Double Row Layout Problem，DRLP），考慮了機(jī)器不同尺寸和相互間存在最小間隙要求等更符合實(shí)際生產(chǎn)情形的約束，并建立了混合整數(shù)規(guī)劃模型，進(jìn)一步開發(fā)了基于該模型的幾種啟發(fā)式程序求解該問題，但所提方法對(duì)于大規(guī)模問題的運(yùn)算速度較慢，效率還有待進(jìn)一步提高。ZHANG在文獻(xiàn)［18］給出了DRLP修正的混合整數(shù)規(guī)劃模型，基于該模型可采用精確算法進(jìn)行求解，但并未給出高效求解方法。文獻(xiàn)［19］針對(duì)雙行布局問題，將其作了簡(jiǎn)化，忽略了相鄰機(jī)器的最小間隙要求，針對(duì)簡(jiǎn)化后的問題提出了一種混合整數(shù)規(guī)劃模型，并采用CPLEX對(duì)機(jī)器數(shù)為9～12的小規(guī)模問題進(jìn)行求解，其中機(jī)器數(shù)為12的測(cè)試問題12b計(jì)算時(shí)間為3 244．6s，依舊難以在合理的時(shí)間內(nèi)求解較大規(guī)模問題。因此，DRLP至今仍是一個(gè)尚未有效解決的難題，這正是展開本文研究的起源。

本文結(jié)合雙行布局問題的特征，考慮到DRLP是組合優(yōu)化問題與連續(xù)優(yōu)化問題的混合體，提出了DRLP的分解策略，將復(fù)雜問題分解為較易求解的組合優(yōu)化問題與線性規(guī)劃問題，并建立了相應(yīng)的數(shù)學(xué)模型，進(jìn)而提出了3種基于不同優(yōu)先規(guī)則的啟發(fā)式求解方法，并對(duì)大量不同規(guī)模的問題進(jìn)行驗(yàn)算與對(duì)比。試驗(yàn)結(jié)果表明，所提啟發(fā)式方法能快速有效地求解雙行布局問題，取得了滿意的效果。

1 DRLP的描述及數(shù)學(xué)模型

1．1 問題描述

DRLP如圖1b所示，分配一系列大小不一的矩形狀機(jī)器到通道兩側(cè)，以使機(jī)器間的總物料搬運(yùn)費(fèi)用最小；圖中有陰影部分的小圓圈表示物料搬運(yùn)點(diǎn)，自動(dòng)引導(dǎo)小車（Automatic Guided Vehicle，AGV）在通道中來回搬運(yùn)物料。為了降低物料搬運(yùn)距離，需要進(jìn)一步提高布局合理性，使之具有更好的物料搬運(yùn)結(jié)構(gòu)和效率。當(dāng)前許多單行布局（如圖1a）轉(zhuǎn)向了雙行布局形式。從布局應(yīng)用角度來看，雙行布局比單行布局具有更好的物料搬運(yùn)結(jié)構(gòu)和效率。DRLP是集成了物料搬運(yùn)路徑問題的一種特殊的布局問題，其物料流在布局中間沿著直線移動(dòng)。而對(duì)于常規(guī)多行布局問題而言，在得到機(jī)器的最優(yōu)布局后，物料流的路徑設(shè)計(jì)問題依舊存在［10］。

1．2 基本假設(shè)條件

為有效地描述雙行布局問題，假設(shè)如下：

（1）每個(gè)機(jī)器的大小給定，其形狀為矩形，各機(jī)器間的物料搬運(yùn)量為已知量（可根據(jù)車間內(nèi)產(chǎn)品、產(chǎn)量及工藝過程求得）。

（2）上下兩行機(jī)器間的通道寬度相對(duì)物料搬運(yùn)距離而言甚小，可忽略不計(jì)，即假設(shè)通道寬度為0。

（3）機(jī)器可具有不同的尺寸，但每個(gè)機(jī)器的物料搬運(yùn)點(diǎn)均位于機(jī)器中心點(diǎn)。

（4）任意兩機(jī)器間有最小間隙要求。

（5）場(chǎng)地相對(duì)于機(jī)器足夠大，機(jī)器放置不受其他特殊情況限制。

1．3 變量與參數(shù)定義

為建立數(shù)學(xué)模型，定義如下變量與參數(shù)：

n為問題規(guī)模，即機(jī)器的數(shù)目；

i，j為機(jī)器標(biāo)號(hào)，i，j∈I，其中I＝｛1，2，…，n｝；

k為行標(biāo)號(hào)，k∈K，其中K＝｛U，L｝，U，L分別表示雙行布局的上面的行和下面的行；

wi為機(jī)器i的寬度；

fij為機(jī)器i到機(jī)器j的物料搬運(yùn)費(fèi)用，?i∈I1，?j∈I2，其中：I1＝｛1，2，…，n－1｝，I2（i）＝｛i＋1，i＋2，…，n｝；

aij為機(jī)器i和j之間所要求的最小間隙，?i∈I1，?j∈I2；

xik為機(jī)器i在k行中的裝/卸載的位置，若機(jī)器i沒有分配在k行，則為0；

yik為二進(jìn)制變量，若機(jī)器i分配在k行，則yik＝1；否則yik＝0；

zkij為二進(jìn)制變量，若機(jī)器j放置在k行中機(jī)器i的右邊，則zkij＝1；否則zkij＝0；

vij＋，vij－表示為了建立整數(shù)規(guī)劃模型而引入的兩個(gè)變量，兩者其一的值為0，兩者之和表示機(jī)器i，j的距離。

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

在上述基本假設(shè)的前提下，DRLP的混合整數(shù)規(guī)劃模型可以表示為［18］：

模型A：

上述模型中，M表示一個(gè)任意足夠大的數(shù)，為考慮計(jì)算效率，定義

其中：目標(biāo)函數(shù)（式（1））表示使總的物料搬運(yùn)費(fèi)用最小化。約束（2）確保當(dāng)且僅當(dāng)xik＞0時(shí)，分配變量yik＝1；約束（3）確保每個(gè)機(jī)器僅分配至一行；約束（4）和（5）用以防止同行的機(jī)器位置發(fā)生重疊放置；約束（6）用于計(jì)算各機(jī)器之間的距離；約束（7）保證二進(jìn)制變量zkij或zkji值為1，當(dāng)且僅當(dāng)機(jī)器i和j同時(shí)位于k行。此外，該約束限制zkij和zkji同時(shí)出現(xiàn)1的情況。如果機(jī)器i和j同時(shí)位于k行，則約束（8）要求zkij或zkji值為1；式（9）～式（12）為限定變量的取值。

2 雙行布局問題分解策略

2．1 雙行布局問題分析

由上述DRLP數(shù)學(xué)模型可知，該問題頗為復(fù)雜且難以求解，主要因素如下：

（1）DRLP的最簡(jiǎn)化形式，假設(shè)雙行中的其中一行無機(jī)器分配，則DRLP簡(jiǎn)化為SRLP?？紤]到SRLP本身就是一個(gè)難以求解的復(fù)合組合優(yōu)化問題，SRLP依然比設(shè)施布局中常見的二次分配模型QAP復(fù)雜，SRLP與QAP兩類問題十分相似，均屬NP－h(huán)ard問題，設(shè)備之間都存在物料流量、訪問頻率和設(shè)備距離矩陣；但兩者間最大的區(qū)別在于SRLP中的機(jī)器間距由機(jī)器各自的尺寸及相互間需要的最小間隙所決定，當(dāng)機(jī)器重新排序后機(jī)器間距會(huì)發(fā)生變化，難以預(yù)先確定。而QAP需要預(yù)先明確每個(gè)點(diǎn)的位置，為每個(gè)點(diǎn)指派設(shè)備以使全部物料運(yùn)輸費(fèi)用最小，即擺放機(jī)器位置的點(diǎn)是固定的，機(jī)器的距離也是一定的。由此可見，在計(jì)算上SRLP比QAP更復(fù)雜，因?yàn)榭紤]了不同機(jī)器的大小、相互間最小間隙等因素，所以更符合實(shí)際情形。

（2）DRLP除具有SRLP所具備的組合優(yōu)化特征外，受雙行因素的影響，還需進(jìn)一步對(duì)每個(gè)機(jī)器的具體位置加以確定，因此是組合優(yōu)化問題與連續(xù)優(yōu)化問題的混合體。因此，在所提的啟發(fā)式方法中，結(jié)合了線性規(guī)劃法來求得各機(jī)器的具體布置位置。

（3）如果在本問題中移去線性規(guī)劃法部分，則可看成是兩個(gè)單行的簡(jiǎn)單組合，此時(shí)DRLP依舊復(fù)雜。對(duì)于規(guī)模數(shù)為n的問題，DRLP可選擇的布局方案將是SRLP的n倍。

為降低DRLP求解的復(fù)雜性，以提高有效求解效率，本文采取問題的分解策略。

2．2 分解策略

在求解DRLP的過程中，其目標(biāo)函數(shù)值（Objective Function Value，OFV）的評(píng)價(jià)是算法尋優(yōu)的基礎(chǔ)。CHUNG所提啟發(fā)式方法［17］中，在構(gòu)造解的每一步中均將通過運(yùn)行線性規(guī)劃來計(jì)算機(jī)器的絕對(duì)位置。以CHUNG所提MinLCF方法為例，其運(yùn)行時(shí)間為O（n3L），L為線性規(guī)劃的平均運(yùn)行時(shí)間，這將耗費(fèi)大量的計(jì)算時(shí)間。為提高算法搜索效率，本文引入一種新的二階段方法來更簡(jiǎn)便地計(jì)算OFV：①找出各機(jī)器間的相對(duì)布置位置：在構(gòu)造一個(gè)完整解之前，可比較一種近似布局方案的OFV，該方案假定最左邊的機(jī)器靠墻（虛擬）布置，每行中的所有機(jī)器以最小間隙情形布置。將復(fù)雜問題轉(zhuǎn)化成一個(gè)純粹的組合優(yōu)化問題，使之易于求解。②計(jì)算各機(jī)器的絕對(duì)位置：在構(gòu)造一個(gè)完整解后，線性規(guī)劃用于求解所得到布局方案每個(gè)機(jī)器的最優(yōu)位置。因此，根據(jù)所提二階段方法，對(duì)于簡(jiǎn)單的啟發(fā)式程序而言，只需要運(yùn)行一次線性規(guī)劃，就可以節(jié)省大量運(yùn)行時(shí)間。

第一階段的組合優(yōu)化問題模型可以描述為：

模型D1：

式中：

π表示DRLP機(jī)器布局方案的一個(gè)特定序列，Π表示所有序列的集合，π∈Π；

πUp是序列π中上行第p個(gè)機(jī)器，p＝1，…，P；πLq是序列π中下行第q個(gè)機(jī)器，q＝1，…，Q，P＋Q＝n；

xi是機(jī)器i的位置，xi與模型A中的xik不同。但兩者間存在著一定的關(guān)系，即

圖2闡述了機(jī)器間的位置關(guān)系。

在構(gòu)造一個(gè)完整的解π后，即得到DRLP的一個(gè)布局方案（僅是機(jī)器的相對(duì)布置位置），模型A中的整數(shù)變量yik，zkij的取值也確定了。因此，可根據(jù)模型A通過求解線性規(guī)劃來確定給定機(jī)器的最優(yōu)位置xik，第二階段的線性規(guī)劃模型如下：

模型D2：

s．t． 約束（2），（4），（5），（6）和（10）。

3 基于分解策略的DRLP啟發(fā)式求解方法

啟發(fā)式方法求解思路如下：首先依據(jù)某啟發(fā)式規(guī)則，依次成對(duì)選擇機(jī)器進(jìn)行分配，得到一個(gè)有效布局方案；再根據(jù)線性規(guī)劃求得各機(jī)器的精確位置。首先作如下定義：

Ia為已分配的機(jī)器的集合。

Iu為尚未分配的機(jī)器的集合，Iu＝I＼Ia。其中“＼”表示集合中元素的相減操作。

機(jī)器對(duì)（i，j）表示分別布置在走廊兩側(cè)面對(duì)面的兩機(jī)器i和j，如圖3中的機(jī)器5和6，機(jī)器1和4，機(jī)器2和3。

3．1 啟發(fā)式規(guī)則

對(duì)于SRLP而言，緊鄰放置兩個(gè)有較大流量成本的機(jī)器通常被認(rèn)為是較好的啟發(fā)式規(guī)則；對(duì)DRLP而言，兩個(gè)機(jī)器面對(duì)面放置在同一位置裝卸為優(yōu)先方案。分別按流量大小、流量與機(jī)器寬度及間距之積、流量與機(jī)器寬度及間距之商建立如下規(guī)則：

（1）按流量大小排序，建立如下啟發(fā)式規(guī)則：

（2）協(xié)同考慮物料的搬運(yùn)成本和機(jī)器寬度及間距，費(fèi)用fij和機(jī)器寬度及間距之積大的優(yōu)先分配，建立如下啟發(fā)式規(guī)則：

（3）協(xié)同考慮物料的搬運(yùn)成本和機(jī)器寬度及間距，費(fèi)用fij和機(jī)器寬度及間距之商大的優(yōu)先分配，建立如下啟發(fā)式規(guī)則：

3．2 算法步驟

將基于上述3種啟發(fā)式規(guī)則發(fā)展起來的方法，分別定義為heuristic1，heuristic2和heuristic3。以heuristic1方法為例，其發(fā)展起來的啟發(fā)式算法步驟如下：

步驟1 從文件中讀入所求解的問題信息，｛fij｝，wi，｛aij｝；初始化Iu＝I。

步驟2 從集合Iu中找到一個(gè)機(jī)器對(duì)（i1，j1），滿足，將兩機(jī)器面對(duì)面布置并放置于 AGV通道兩側(cè)；更新Iu←Iu＼｛i1，j1｝。

步驟3 在尚未分配的機(jī)器集合Iu中，找出滿足f1（iR，jR）＝ max｛fiRjR｝的機(jī)器對(duì)（iR，jR），分別將機(jī)器放置于當(dāng)前已放置機(jī)器右邊的上下行；更新Iu←Iu＼｛iR，jR｝。

步驟4 在尚未分配機(jī)器集合Iu中，找出滿足的機(jī)器對(duì)（iL，jL），分別將機(jī)器放置于當(dāng)前已放置機(jī)器左邊的上下行；更新Iu←Iu＼｛iL，jL｝。

步驟5 重復(fù)步驟3和步驟4，直到所有機(jī)器分配完畢，即Iu＝?。若最后僅有一個(gè)機(jī)器剩余，則隨機(jī)放置該機(jī)器至相應(yīng)邊（已分配機(jī)器的左側(cè)或右側(cè)）的上行或下行。

步驟6 在得到一個(gè)完整解后，即得到了所有機(jī)器的相對(duì)位置布置方案，根據(jù)相對(duì)位置關(guān)系確定模型A中0－1整數(shù)變量yik，zijk的取值。

步驟7 依據(jù)2．2節(jié)的模型D2，應(yīng)用單純形法求解線性規(guī)劃模型，得到每個(gè)機(jī)器的絕對(duì)位置xik，?i∈I，?k∈K。

步驟8 輸出布局方案的目標(biāo)函數(shù)值、計(jì)算時(shí)間，以及繪制布置方案圖。

針對(duì)啟發(fā)式方法heuristic2和heuristic3，只需將步驟2～步驟4中的優(yōu)先規(guī)則由式（21）改成式（22）或式（23）即可，其余部分一致。

4 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證算法的有效性，針對(duì)不同規(guī)模的問題，應(yīng)用所提啟發(fā)式方法進(jìn)行了測(cè)試。所提啟發(fā)式方法在Windows 7操作系統(tǒng)下用MATLAB 7．8開發(fā)了試驗(yàn)程序，并運(yùn)行在Intel Core i5－2410M、2．30GHz主頻、4GB內(nèi)存的筆記本電腦上，使用該試驗(yàn)程序進(jìn)行了實(shí)驗(yàn)計(jì)算。

4．1 測(cè)試問題

本文采用機(jī)器數(shù)從6～36不同規(guī)模的16個(gè)測(cè)試問題，以檢驗(yàn)所提啟發(fā)式方法求解DRLP的有效性。問題的數(shù)據(jù)均隨機(jī)產(chǎn)生，產(chǎn)生方法類似于文獻(xiàn)［17］所采取的方法，表1給出了所用測(cè)試問題特征：?jiǎn)栴}規(guī)模分別從6～36臺(tái)機(jī)器，以2為間隔依次遞增；物料搬運(yùn)費(fèi)用和每對(duì)機(jī)器間的最小間隙分別依據(jù)U（0，50）和U（1，2）隨機(jī)創(chuàng)建；機(jī)器寬度根據(jù) U（0，20）隨機(jī)產(chǎn)生。

表1 測(cè)試實(shí)例

4．2 測(cè)試結(jié)果與分析

為給所提啟發(fā)式方法的性能比較提供參考依據(jù)，首先采用Lingo 9．0軟件，依據(jù)1．4節(jié)給出的混合整數(shù)模型A使用分枝定界法求解測(cè)試問題。經(jīng)測(cè)試，對(duì)于機(jī)器數(shù)在10臺(tái)以下的小規(guī)模問題，可在一定時(shí)間內(nèi)找到問題的最優(yōu)解：對(duì)于問題規(guī)模分別為6，8，10的測(cè)試問題，其求解時(shí)間分別為5s，101 s和10 861s，超過12臺(tái)機(jī)器的問題已無法在合理時(shí)間內(nèi)精確求解。可以看出，隨著問題規(guī)模的增加，分枝定界法的計(jì)算時(shí)間呈指數(shù)級(jí)增加，因此對(duì)于中大規(guī)模問題難以在合理的時(shí)間內(nèi)求得最優(yōu)解。為便于對(duì)比所提算法的求解性能，兼顧運(yùn)算效率，將Lingo中求解混合整數(shù)規(guī)劃模型A的運(yùn)算時(shí)間設(shè)置為600s，以得到一個(gè)近似最優(yōu)解用于算法的比較。

隨后，對(duì)16個(gè)測(cè)試問題在Lingo 9．0軟件中分別運(yùn)行600s，求解混合整數(shù)規(guī)劃模型A，所得計(jì)算結(jié)果如表2所示，其中第1列給出了測(cè)試問題的規(guī)模n＝16～36，第2列給出了Lingo軟件運(yùn)行600s所求得的目標(biāo)函數(shù)值OFV0。進(jìn)而應(yīng)用所提3種啟發(fā)式方法分別求解了16個(gè)測(cè)試問題，計(jì)算結(jié)果在表2第3～5列中分別給出，包含了目標(biāo)函數(shù)值（3種方法分別為OFV1，OFV2，OFV3）、解的偏差gap及運(yùn)算時(shí)間（單位：s）。其中，與OFV0的偏差gap定義為：gap（%）＝（OFV－OFV0）/OFV0×100%；顯然，若當(dāng)前方法求得的解優(yōu)于OFV0，則該偏差值將為負(fù)數(shù)。通過對(duì)表2中的數(shù)據(jù)進(jìn)行對(duì)比分析可以看出，所提啟發(fā)式方法均可以快速求得滿意解，所提3種啟發(fā)式方法的計(jì)算時(shí)間相差不大，對(duì)于問題規(guī)模n分別為6，8，10的測(cè)試問題，所用時(shí)間分別為0．01 s，0．02s及0．05s（以heuristic3為例），問題規(guī)模為16的測(cè)試問題計(jì)算時(shí)間也不足1s，所提啟發(fā)式方法具有較高的效率。

表2 所提3種啟發(fā)式方法計(jì)算結(jié)果

續(xù)表2

文獻(xiàn)［18］給出了5種啟發(fā)式方法，其中方法MinLCF的總體性能最佳；因此，將所提3種啟發(fā)式方法與MinLCF進(jìn)行比較?？紤]所有問題均是隨機(jī)產(chǎn)生的，故將與Lingo解的偏差gap作為驗(yàn)證算法求解質(zhì)量的一個(gè)指標(biāo)。根據(jù)計(jì)算結(jié)果，繪制了求解性能相關(guān)曲線圖，求解質(zhì)量和求解時(shí)間比較分別如圖4和圖5所示。

4．2．1 求解質(zhì)量比較

圖4給出了所提3種啟發(fā)式方法heuristic1，heuristic2，heuristic3和 MinLCF間的求解質(zhì)量比較，繪制了16個(gè)不同規(guī)模測(cè)試問題的求解偏差曲線圖，從圖中可以看出：總體求解性能上heuristic1方法略優(yōu)于heuristic2方法。在所測(cè)試的16個(gè)問題中，有14個(gè)問題（n＝10～36）的heuristic1比heuristic2求得更優(yōu)的解，有1個(gè)問題（n＝6）兩者得到了相同的解，1個(gè)問題的heuristic1比heuristic2求得較差的解差（n＝8）。heuristic1和heuristic2的總體求解能力略低于 MinLCF。啟發(fā)式方法heuristic3對(duì)所有測(cè)試的16個(gè)問題在求解性能上均優(yōu)于MinLCF，也優(yōu)于heuristic1和heuristic2，具有明顯的優(yōu)勢(shì)；且隨著問題規(guī)模的增加，heuristic3比MinLCF求解質(zhì)量提升越為明顯。

4．2．2 求解效率比較

為分析各方法的計(jì)算效率，對(duì)求解時(shí)間進(jìn)行了分析比較，從表3所給出的計(jì)算時(shí)間來看，所提3種啟發(fā)式方法heuristic1，heuristic2和heuristic3的計(jì)算時(shí)間差異不大。因此，選取heuristic3作為代表算法與MinLCF進(jìn)行比較。圖5給出了heuristic3與MinLCF的算法運(yùn)行效率的比較，16個(gè)測(cè)試問題中，heuristic3的計(jì)算時(shí)間均不足MinLCF的1/10，heuristic3在短時(shí)間內(nèi)比MinLCF取得了更好的解，所提啟發(fā)式方法具有明顯的計(jì)算時(shí)間優(yōu)勢(shì)。究其原因，主要在于MinLCF方法每分配一個(gè)設(shè)施分配位置，就運(yùn)行一次線性規(guī)劃程序求解具體分配位置，因此計(jì)算量大，而本文所提啟發(fā)式方法在基于問題分解策略的基礎(chǔ)上，在得到最終完整布局方案后再運(yùn)行一次線性規(guī)劃程序，因此極大地節(jié)省了計(jì)算時(shí)間。從上述分析可知，所提啟發(fā)式方法尤其是heuristic3，在更短的時(shí)間內(nèi)得到了較優(yōu)的解。隨著問題規(guī)模的增加，在計(jì)算時(shí)間上heuristic3的優(yōu)越性比MinLCF更趨明顯。

值得一提的是：本文的結(jié)果在Intel Core i5－2410M2．30GHz PC、內(nèi)存4GB的筆記本電腦上求得，而 MinLCF的結(jié)果在Sun UltraSPARCⅢi（1．6GHz，4－CPU、內(nèi)存為16G）的工作站上求得；從運(yùn)行平臺(tái)來看，MinLCF方法計(jì)算用的工作站性能更優(yōu)。

通過上述大量測(cè)試問題的對(duì)比實(shí)驗(yàn)表明，所提3種啟發(fā)式方法均具有良好的穩(wěn)健性，尤其是heuristic3比MinLCF能更快地找到更優(yōu)解。

4．2．3 解的具體布局方案闡述

為闡述所提啟發(fā)式方法heuristic3的性能，對(duì)規(guī)模n＝18的測(cè)試問題進(jìn)行了測(cè)試，并給出了具體布置方案圖，該問題的實(shí)驗(yàn)數(shù)據(jù)｛fij｝n×n，wi及｛aij｝n×n在附錄給出。基于方法heuristic3所開發(fā)的程序僅用了1．55s就求得了滿意解，其總物料搬運(yùn)費(fèi)用為124 877，其解優(yōu)于Lingo運(yùn)行600s時(shí)所求的解（總物料搬運(yùn)費(fèi)用為132 874），與Lingo運(yùn)行600s時(shí)所求得解間的偏差gap為－6．02%；所編寫程序自動(dòng)繪制方案布局圖，如圖6所示。為方便繪圖顯示，假定機(jī)器長(zhǎng)寬相等；圖中各矩形方塊表示機(jī)器，方塊內(nèi)的數(shù)字表示機(jī)器代碼，各方塊靠近走廊側(cè)的小圓圈表示該機(jī)器的物料搬運(yùn)點(diǎn)。從圖中可以看出，該布局方案的各機(jī)器依據(jù)最小間隙緊密布置，所生成的方案是合理可行的。

5 結(jié)束語

本文針對(duì)DRLP展開研究，提出了問題求解的分解策略，進(jìn)而提出了3種啟發(fā)式方法用于求解該問題，并通過大量問題測(cè)試了所提方法的性能。實(shí)驗(yàn)結(jié)果顯示，對(duì)于DRLP所提啟發(fā)式方法是有效且高效的。本文的主要成果如下：

（1）針對(duì)DRLP提出了問題求解的分解策略，建立了DRLP子問題的數(shù)學(xué)模型，進(jìn)而提出了DRLP兩階段求解思路，為后續(xù)建立高效求解算法提供了一種新思路與途徑。

（2）基于DRLP兩階段求解思路，提出了求解DRLP的3種融合線性規(guī)劃的啟發(fā)式求解方法，并開發(fā)了相關(guān)程序，經(jīng)大量測(cè)試問題驗(yàn)證了算法性能。結(jié)果表明：3種啟發(fā)式方法均能快速求得問題的滿意解，尤其是heuristic3具有較優(yōu)異的性能，在求解精度和求解速度方面均明顯優(yōu)于現(xiàn)有的MinLCF方法。

（3）無論中小規(guī)模DRLP還是大規(guī)模DRLP，所提3種啟發(fā)式方法均具有良好的適用性；隨著問題規(guī)模的增加，heuristic3比現(xiàn)有方法 MinLCF在計(jì)算時(shí)間和求解質(zhì)量上更具優(yōu)越性。

在將來的研究中，希望將所提的方法應(yīng)用于DRLP的拓展問題中，如多約束、多目標(biāo)DRLP等，從而進(jìn)一步提高算法的搜索效率和求解質(zhì)量。

［1］ DRIRA A，PIERREVAL H，HAJRI－GABOUJ S．Facility layout problems：a survey［J］．Annual Reviews in Control，2007，31（2）：255－267．

［2］ TOMPKINS J A，WHITE J A，BOZER Y A，et al．Facilities planning［M］．4th ed．New York，N．Y．，USA：John Wiely＆Sons，2010．

［3］ MAZINANI M，ABEDZADEH M，MOHEBALI N．Dynamic facility layout problem based on flexible bay structure and solving by genetic algorithm［J］．International Journal of Advanced Manufacturing Technology，2013，65（5－8）：929－943．

［4］ MOSLEMIPOUR G，LEE T．Intelligent design of a dynamic machine layout in uncertain environment of flexible manufacturing systems［J］．Journal of Intelligent Manufacturing，2012，23（5）：1849－1860．

［5］ RAMKUMAR A S，PONNAMBALAM S G，JAWAHAR N．A new iterated fast local search heuristic for solving QAP formulation in facility layout design［J］．Robotics and Computer－Integrated Manufacturing，2009，25（3）：620－629．

［6］ HALE T S，HUQ F，HIPKIN I．An improved facility layout construction method［J］．International Journal of Production Research，2012，50（15）：4271－4278．

［7］ SINGH S，SINGH V．Three－level AHP－based heuristic approach for a multi－objective facility layout problem［J］．International Journal of Production Research，2011，49（4）：1105－1125．

［8］ MAHDAVI I，SHIRAZI B，PAYDAR M．A flow matrixbased heuristic algorithm for cell formation and layout design in cellular manufacturing system［J］．The International Journal of Advanced Manufacturing Technology，2008，39（9）：943－953．

［9］ RAWABDEH I，TAHBOUB K．A new heuristic approach for a computer－aided facility layout［J］．Journal of Manufacturing Technology Management，2006，17（7）：962－986．

［10］ ASEF－VAZIRI A，LAPORTE G，ORTIZ R．Exact and heuristic procedures for the material handling circular flow path design problem［J］．European Journal of Operational Research，2007，176（2）：707－726．

［11］ DJELLAB H，GOURGAND M．A new heuristic procedure for the single－row facility layout problem［J］．International Journal of Computer Integrated Manufacturing，2001，14（3）：270－280．

［12］ MATAI R，SINGH S P，MITTAL M L．Non－greedy systematic neighbourhood search heuristic for multi－objective facility layout problem［J］．International Journal of Services and Operations Management，2012，12（1）：118－138．

［13］ SUO Xiaohong，LIU Zhanqiang．Modeling and solution algorithms for facility layout of manufacturing systems［J］．Computer Integrated Manufacturing Systems，2007，13（10）：1941－1951（in Chinese）．［鎖小紅，劉戰(zhàn)強(qiáng)．制造系統(tǒng)設(shè)備布局的建模理論與求解方法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2007，13（10）：1941－1951．］

［14］ YING Baosheng，ZHANG Hua，YANG Shaohua．Heuristic algorithm for machine layout in cellular shop［J］．Computer Integrated Manufacturing Systems，2004，10（8）：962－965（in Chinese）．［應(yīng)保勝，張 華，楊少華．敏捷制造車間布局優(yōu)化的啟發(fā)式算法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2004，10（8）：962－965．］

［15］ SUO Xiaohong，LIU Zhanqiang．Modeling and simulation of single－row layout based on logistics routing［J］．China Mechanical Engineering，2007，18（21）：2576－2579（in Chinese）．［鎖小紅，劉戰(zhàn)強(qiáng)．基于物流路徑的單行布局建模與仿真研究［J］．中國機(jī)械工程，2007，18（21）：2576－2579．］

［16］ GUO Yuanyuan，WANG Qian，LIANG Feng．Facility layout design based on particle swarm optimization［J］．Computer Integrated Manufacturing Systems，2012，18（11）：2476－2484（in Chinese）．［郭源源，王 謙，梁 峰．基于粒子群優(yōu)化算法的車間布局設(shè)計(jì)［J］．計(jì)算機(jī)集成制造系統(tǒng)，2012，18（11）：2476－2484．］

［17］ CHUNG J，TANCHOCO J M A．The double row layout problem［J］．International Journal of Production Research，2010，48（3）：709－727．

［18］ ZHANG Zeqiang，MURRAY C C．A corrected formulation for the double row layout problem［J］．International Journal of Production Research，2012，50（15）：4220－4223．

［19］ AMARAL A R S．Optimal solutions for the double row layout problem ［J］．Optimization Letters，2013，7（2）：407－413．