馬淑梅　蔡惠森　張一帆　李愛平

同濟(jì)大學(xué)，上海，201804

不確定需求下的設(shè)備動態(tài)布局方法

馬淑梅蔡惠森張一帆李愛平

同濟(jì)大學(xué)，上海，201804

針對現(xiàn)有車間設(shè)備動態(tài)布局方法存在的不足，在考慮產(chǎn)品需求不確定性對布局性能穩(wěn)定性影響的基礎(chǔ)上，提出了一種結(jié)合模糊理論與改進(jìn)遺傳算法的不等面積設(shè)備動態(tài)布局方法。分析了產(chǎn)品需求不確定性及其隨時間變化特性，引入了三角模糊數(shù)描述不確定產(chǎn)品需求；通過分析各生產(chǎn)階段間的設(shè)備重組過程，將動態(tài)布局轉(zhuǎn)化為數(shù)個靜態(tài)布局，構(gòu)建了基于柔性區(qū)域結(jié)構(gòu)的不確定需求動態(tài)布局模型。結(jié)合三角模糊數(shù)運(yùn)算及排序方法與自適應(yīng)局部搜索機(jī)制提出了改進(jìn)遺傳算法，以物料搬運(yùn)及設(shè)備重組費(fèi)用總和為優(yōu)化目標(biāo)，解決不確定需求下的不等面積設(shè)備動態(tài)布局問題。通過算例測試和實(shí)例分析，驗證了所提方法的有效性和實(shí)用性。

不確定需求；改進(jìn)遺傳算法；不等面積；設(shè)備動態(tài)布局

0　引言

車間設(shè)備布局規(guī)劃是制造過程的重要環(huán)節(jié)，良好的車間布局可以提高企業(yè)整體效益，降低高達(dá)50%的生產(chǎn)運(yùn)營費(fèi)用[1]。傳統(tǒng)靜態(tài)布局方法假設(shè)設(shè)備間物流量固定不變，忽視了品種、產(chǎn)量等因素波動的長遠(yuǎn)影響。動態(tài)車間設(shè)備布局方法將整個布局使用期限劃分為多個生產(chǎn)階段，綜合考慮各個生產(chǎn)階段的產(chǎn)品類型及需求信息，并在生產(chǎn)階段間進(jìn)行設(shè)備重組，因其對市場變化的快速響應(yīng)能力而引起學(xué)者們的廣泛關(guān)注[2-4]。在設(shè)備動態(tài)布局規(guī)劃中，影響布局性能的主要因素有規(guī)劃中所使用信息的準(zhǔn)確性、設(shè)備布局模型和求解算法。

大多數(shù)動態(tài)布局研究均假設(shè)規(guī)劃中使用的信息是絕對準(zhǔn)確的，但是布局規(guī)劃必須在產(chǎn)品投產(chǎn)前完成，規(guī)劃中涉及的品種、需求等與產(chǎn)品相關(guān)的信息均由市場預(yù)測方法獲得，具有不確定性。再者，由于長期預(yù)測比短期預(yù)測準(zhǔn)確性更低，信息的不確定性隨著時間推移而增大，故對布局性能的影響也隨之增大。在布局規(guī)劃涉及的諸多信息中，需求信息直接影響設(shè)備間物流量的大小，對布局性能穩(wěn)定性影響最為嚴(yán)重。

近年來，開始有學(xué)者在動態(tài)布局規(guī)劃中，考慮需求不確定性的影響。Balakrishnan等[5]研究了動態(tài)布局中產(chǎn)品需求的預(yù)測誤差問題，證明了產(chǎn)品需求的不確定性對布局性能穩(wěn)定性影響極大。Samarghandi等[6]采用模糊理論對不確定的物流量進(jìn)行建模，研究車間設(shè)備動態(tài)布局問題，但是沒有考慮不確定性隨時間增大的性質(zhì)。Drira等[7]研究了不確定需求下的動態(tài)布局問題并提出了一種有效的求解方法。以上研究均說明了考慮需求的不確定性可以提升布局面對需求波動時性能的穩(wěn)定性，但是在布局模型上均采用離散式模型，假設(shè)所有設(shè)備形狀尺寸均相同，在生產(chǎn)實(shí)際中，易造成空間浪費(fèi)，最終獲得的離散式塊狀布局亦不利于轉(zhuǎn)化為生產(chǎn)實(shí)際應(yīng)用。

設(shè)備布局模型可以分為離散式和連續(xù)式，相比離散式布局模型，連續(xù)式布局模型考慮設(shè)備面積不盡相等的影響，以期獲得更貼合實(shí)際的設(shè)備布局方案。由于求解相對困難，連續(xù)式布局模型主要被應(yīng)用于靜態(tài)布局的研究中，在動態(tài)布局中的應(yīng)用較少。McKendall等[8]解決了基于混合整數(shù)規(guī)劃的動態(tài)布局問題；Mazinani等[9]則研究了以柔性區(qū)域結(jié)構(gòu)為布局模型的動態(tài)布局問題，但是均未考慮需求的不確定性。由于解決組合優(yōu)化問題的良好表現(xiàn)以及易于編碼等優(yōu)點(diǎn)，遺傳算法被廣泛地應(yīng)用于設(shè)備動態(tài)布局問題中[10]。遺傳算法在解決較小規(guī)模問題時表現(xiàn)優(yōu)異，但是在較大規(guī)模問題求解過程中也面臨著收斂速度緩慢和陷入局部收斂等問題。動態(tài)布局具有多階段多約束特性，屬于大規(guī)模問題，因此應(yīng)用遺傳算法求解動態(tài)布局問題時通常需對算法進(jìn)行改進(jìn)。

綜合以上分析可知，在不確定需求環(huán)境下的動態(tài)布局問題研究中，還存在有待深入研究的地方。在需求信息的處理上，需要考慮需求不確定性對布局性能穩(wěn)定性的影響，所以必須正確描述需求不確定性及其隨時間增大的特性；在布局模型上，為更貼合實(shí)際并提高車間面積利用率，必須考慮設(shè)備面積不盡相等的實(shí)際情況，從而使布局方案在轉(zhuǎn)化為生產(chǎn)應(yīng)用時更為容易；在求解算法上，解決較大規(guī)模問題時，算法應(yīng)具有較快的收斂速度，并能有效避免局部收斂。

因此，本文采用模糊理論描述產(chǎn)品需求不確定性以提升布局面對需求波動時的性能穩(wěn)定性，同時避開概率分布函數(shù)所引起的計算復(fù)雜性，構(gòu)建以針對不等面積設(shè)備的多行線性布局模型為基礎(chǔ)的動態(tài)布局模型；引入自適應(yīng)局部搜索機(jī)制來改進(jìn)遺傳算法性能，在增加較小運(yùn)算量的前提下提升遺傳算法的收斂速度并強(qiáng)化搜索方向性；再將改進(jìn)遺傳算法與三角模糊數(shù)運(yùn)算與排序方法結(jié)合，解決不確定需求下的動態(tài)布局問題。

1　不確定需求下的不等面積設(shè)備動態(tài)布局模型

1.1不確定需求的處理方法

(1)

由隸屬函數(shù)可以看出，b為可能性最大的值，而上限c與下限a之差的大小則表示該三角模糊數(shù)不確定性的大小。

(a)生產(chǎn)階段1(b)生產(chǎn)階段2

(c)生產(chǎn)階段3圖1　不同生產(chǎn)階段的需求不確定性

(2)

式中，N為產(chǎn)品種類數(shù)。

1.2問題描述與相關(guān)假設(shè)

在多品種加工車間中，將車間布局的規(guī)劃使用期限劃分為多個生產(chǎn)階段，每個產(chǎn)品在每個階段的具體產(chǎn)量需求數(shù)據(jù)通過預(yù)測獲得，具有不確定性；因為長期預(yù)測的可靠性比短期預(yù)測的可靠性低，所以產(chǎn)品需求數(shù)據(jù)的不確定性隨生產(chǎn)階段的推移而增大。本文研究的問題就是在考慮上述產(chǎn)品需求不確定性的前提下，在每個階段對已知的M臺不等面積設(shè)備進(jìn)行布局，并允許階段間設(shè)備重組，以物料搬運(yùn)與設(shè)備重組費(fèi)用總和最小為目標(biāo)，最終獲得切合實(shí)際的動態(tài)布局方案。

連續(xù)型布局模型主要有混合整數(shù)規(guī)劃(mixed-integer programming, MIP)和柔性區(qū)域結(jié)構(gòu)(flexible bays structure, FBS)兩類。混合整數(shù)規(guī)劃雖然理論上可以獲得物料搬運(yùn)費(fèi)用更小的布局方案，但是由于過多的邊界參數(shù)導(dǎo)致求解困難。相比混合整數(shù)規(guī)劃模型，柔性區(qū)域結(jié)構(gòu)求解更為簡單，也是最容易轉(zhuǎn)化為實(shí)際應(yīng)用的布局模型[11]。多行線性布局[12]是柔性區(qū)域結(jié)構(gòu)的特殊形式，其每一行相當(dāng)于柔性區(qū)域結(jié)構(gòu)中的一個區(qū)域，并且增加了設(shè)備間距和行間距約束，因此具有易于轉(zhuǎn)化為實(shí)際應(yīng)用、求解相對容易的優(yōu)點(diǎn)，是一種面向不等面積設(shè)備的設(shè)備布局模型。本文采用多行線性設(shè)備布局模型，并假設(shè)：①布局車間和設(shè)備形狀均為矩形且尺寸已知；②設(shè)備放置的方向確定；③布局車間生產(chǎn)產(chǎn)品型號及其對應(yīng)的單位物流量已知。

圖2是多行線性車間示意圖，M臺設(shè)備分行布置，在同一行內(nèi)各設(shè)備縱向(y軸)坐標(biāo)相同，L、W分別為車間的長度和寬度。xit、yit為設(shè)備i幾何中心在t階段時的x、y坐標(biāo)，hij為設(shè)備i與j間要求的橫向最小距離；s0為最小縱向行間距；so x、soy為設(shè)備邊界與車間邊界的橫向安全距離和縱向安全距離；six、siy分別為設(shè)備i的橫向和縱向尺寸。具體約束條件表達(dá)如下。

(1)設(shè)備間橫向距離約束。即在水平方向相鄰設(shè)備的距離必須不小于設(shè)備間要求的橫向最小距離hij：

(3)

式中，Zikt為決策變量，如果在t階段設(shè)備i布置于k行則取1，否則取0。

圖2　多行線性設(shè)備布局示意圖

(2)設(shè)備行間距約束。即任意兩行設(shè)備(p行、q行)的行間距必須不小于縱向行間距要求s0：

(4)

(3)邊界約束。為便于物料搬運(yùn)和人員運(yùn)動，設(shè)備邊緣與車間邊界間的距離必須不小于最小安全距離:

(5)

(6)

設(shè)備重組是在已有布局上進(jìn)行設(shè)備位置改變的復(fù)雜過程。本文根據(jù)車間實(shí)際情況，簡化設(shè)備重組過程，假設(shè)在車間邊緣位置有足夠大的設(shè)備暫存區(qū)，則相鄰生產(chǎn)階段間的設(shè)備重組步驟如下：

(1)在待重組設(shè)備中隨機(jī)選擇一臺設(shè)備Mn為當(dāng)前重組設(shè)備，先將該設(shè)備Mn目標(biāo)位置上的現(xiàn)有設(shè)備移至?xí)捍鎱^(qū)，再將設(shè)備Mn移至目標(biāo)位置；

(2)在暫存區(qū)設(shè)備中選擇一臺設(shè)備為當(dāng)前重組設(shè)備，按照步驟(1)的方法對當(dāng)前重組設(shè)備進(jìn)行位置重組，重復(fù)此步驟直至?xí)捍鎱^(qū)上無設(shè)備存放；

(3)判斷是否完成所有設(shè)備重組，若未完成，返回步驟(1)。

圖3所示為設(shè)備Mn的重組過程，先將Mn目標(biāo)位置上的設(shè)備Mk、Mj移至?xí)捍鎱^(qū)，再將設(shè)備Mn移至目標(biāo)位置。

圖3　動態(tài)布局重組過程

1.3優(yōu)化目標(biāo)模型

車間設(shè)備布局的主要優(yōu)化目標(biāo)是物料搬運(yùn)費(fèi)用最小，因此求解時必須考慮布局重組產(chǎn)生的費(fèi)用。按照上述動態(tài)布局設(shè)備重組過程，階段間的設(shè)備重組費(fèi)用主要由設(shè)備從現(xiàn)有位置移至目標(biāo)位置、設(shè)備從現(xiàn)有位置移至?xí)捍鎱^(qū)和設(shè)備從暫存區(qū)移至目標(biāo)位置三個設(shè)備移動動作所產(chǎn)生。車間動態(tài)設(shè)備布局方法的優(yōu)化目標(biāo)為整個規(guī)劃期物料搬運(yùn)與設(shè)備重組費(fèi)用總和最小，即

(7)

2　基于改進(jìn)遺傳算法的設(shè)備動態(tài)布局問題求解方法

2.1遺傳算法的改進(jìn)

本文選擇遺傳算法作為求解方法，并根據(jù)所解決問題的特性對遺傳算法進(jìn)行改進(jìn)：

(1)結(jié)合三角模糊數(shù)字運(yùn)算和排序方法。遺傳算法的目標(biāo)值計算和比較通常是精確數(shù)值運(yùn)算，但是在上述構(gòu)建的基于不確定需求的不等面積動態(tài)設(shè)備布局模型中，作為輸入之一的需求數(shù)據(jù)是三角模糊數(shù)字，目標(biāo)值計算過程涉及模糊運(yùn)算，目標(biāo)值的比較亦是模糊數(shù)字的大小比較。因此，在遺傳算法中引入三角模糊數(shù)字計算和排序方法，根據(jù)三角模糊數(shù)字運(yùn)算規(guī)律計算獲得每個可能方案的目標(biāo)函數(shù)值，再按照模糊數(shù)字排序方法比較不同方案目標(biāo)值的大小，完成優(yōu)勝劣汰過程。

(2)引入自適應(yīng)局部搜索機(jī)制。遺傳算法是一種全局搜索進(jìn)化算法，可有效避免局部收斂，但是在解決大規(guī)模復(fù)雜問題時存在收斂緩慢問題。引入局部搜索機(jī)制既可提升遺傳算法收斂速度，又可通過在次優(yōu)解的領(lǐng)域搜索增加獲得最優(yōu)解的概率[13]，是改善遺傳算法性能的有效方法。但是局部搜索需要進(jìn)行大量的運(yùn)算，將會大大延長求解時間，同時有可能導(dǎo)致局部收斂。因此，本文在遺傳算法中引入的是基于相似系數(shù)方法[14]的自適應(yīng)局部搜索機(jī)制，并非在每次循環(huán)都進(jìn)行局部搜索，而是通過計算每次遺傳循環(huán)中種群的平均相似度系數(shù)，判斷是否需要局部搜索。

改進(jìn)遺傳算法的求解流程如圖4所示，具體求解步驟如下。

圖4　改進(jìn)遺傳算法的求解流程圖

(1)迭代數(shù)i=0，隨機(jī)產(chǎn)生初始種群P0，種群規(guī)模N0，置P0為當(dāng)前種群P。

(2)根據(jù)式(7)計算當(dāng)前種群目標(biāo)值，比較獲得當(dāng)前種群的最優(yōu)個體并置為當(dāng)前最優(yōu)解Be。

(3)若迭代數(shù)i

(4)i←i+1，產(chǎn)生新種群Pi。①輪盤算法產(chǎn)生新種群，在當(dāng)前種群P上隨機(jī)選擇k個染色體，比較其目標(biāo)值，將較優(yōu)者復(fù)制至新種群Pi；②重復(fù)步驟①直至新種群Pi規(guī)模為N0；③將新種群Pi隨機(jī)劃分為Ni/2對父代染色體，按概率pc進(jìn)行交叉操作，被選中的父代染色體在交叉操作完成后由子代染色體取代，未被選中的染色體保留在種群Pi中；④對種群Pi按概率pm進(jìn)行變異操作；⑤計算種群Pi的相似度系數(shù)并判斷是否符合局部搜索條件，若符合則對當(dāng)前種群進(jìn)行局部搜索。

(5)將新種群Pi置為當(dāng)前種群P，返回步驟(2)。

2.2三角模糊數(shù)運(yùn)算與排序方法

(8)

(9)

根據(jù)上述三角模糊數(shù)字運(yùn)算定義，每個方案計算獲得的目標(biāo)值是三角模糊數(shù)字，故須比較模糊數(shù)字的大小(即模糊數(shù)字排序)。目前，在模糊數(shù)字排序上尚無公認(rèn)的最好的方法，出于可靠性和可實(shí)施性考慮，本文采用Fortemps等[15]提出的面積比較方法。

(10)

(11)

(12)

(13)

其中

(14)

(15)

(16)

圖5　三角模糊數(shù)比較示意圖

2.3染色體編碼

圖6　單階段布局示意圖

在動態(tài)環(huán)境下，一個動態(tài)布局方案由T(T為階段數(shù))個靜態(tài)布局方案組成，因此，其染色體編碼為T行矩陣，每行為一個單階段染色體序列，代表一個階段的靜態(tài)設(shè)備布局。圖7所示的車間動態(tài)布局方案對應(yīng)的染色體編碼為編碼后，每個染色體代表一個動態(tài)布局方案，通過交叉、突變和自適應(yīng)局部搜索等一系列遺傳操作完成優(yōu)勝劣汰過程，最終獲得最優(yōu)解或近最優(yōu)解。

圖7　動態(tài)布局示意圖

2.4染色體交叉操作

交叉操作包括階段內(nèi)染色體交叉(行內(nèi)交叉)和階段間染色體交叉(行間交叉)兩部分，并按一定概率進(jìn)行。階段內(nèi)染色體交叉以行內(nèi)的單個設(shè)備編碼為交叉對象。如圖8所示，P11、P21是父代矩陣編碼P1、P2對應(yīng)階段的編碼(即進(jìn)行交叉操作的兩個階段編碼)，隨機(jī)生成兩個交叉點(diǎn)，將P11、P21位于兩交叉點(diǎn)間的編碼逐一交叉，依次對P1、P2各個階段進(jìn)行交叉操作。

階段間染色體交叉以整行編碼為交叉對象，在階段內(nèi)交叉完成后進(jìn)行。隨機(jī)產(chǎn)生交叉點(diǎn)t，將父代P12、P22中t以前階段的編碼保留至子代中，對于子代中t階段的編碼，以子代C12(C22)的t-1階段到t階段的重組費(fèi)用最小為標(biāo)準(zhǔn)，從P12、P22的t階段中選擇重組費(fèi)用較小的一個作為C12(C22)的t階段編碼，同理產(chǎn)生子代t以后階段的編碼。如圖8中，選中的交叉點(diǎn)為3，所以父代中第一、二階段的編碼直接保留至子代C12、C22中。子代C12中第三階段編碼的產(chǎn)生方法為：分別計算C12第二階段到P12第三階段和C12第二階段到P22第三階段的設(shè)備重組費(fèi)用并比較大小，若前者小，則將P12第三階段編碼復(fù)制至C12第三階段，否則將P22第三階段編碼復(fù)制至C12第三階段。同理產(chǎn)生C12的第四階段編碼和C22的第三、四階段編碼。

圖8　染色體交叉操作

2.5染色體突變操作

種群在完成交叉操作后按一定概率進(jìn)行突變操作，包括階段內(nèi)突變和階段間突變兩部分。如圖9所示，階段內(nèi)突變是在單階段染色體編碼中隨機(jī)選擇兩個編碼，交換其位置。階段間突變在階段內(nèi)突變之后進(jìn)行，隨機(jī)選取突變階段，將其替換為一個隨機(jī)產(chǎn)生的染色體編碼。

圖9　染色體變異操作

2.6自適應(yīng)局部搜索

本文采用基于相似度系數(shù)的自適應(yīng)性局部搜索。在每次迭代中，計算種群的染色體相似度系數(shù)，將種群相似度系數(shù)與預(yù)定參數(shù)比較，對符合條件的種群進(jìn)行局部搜索。種群相似度系數(shù)按文獻(xiàn)[14]提出的方法計算，染色體p和q的相似度系數(shù)Spq為

(17)

(18)

式中，v為染色體中的位置系數(shù)；gpv為在染色體p中布置于位置v的設(shè)備；?(gpv,gqv)為判斷指數(shù)。

按式(18)定義，整個種群的平均相似度系數(shù)為

(19)

只有當(dāng)種群的平均相似度系數(shù)大于預(yù)定值δ時，方在此次循環(huán)中進(jìn)行局部搜索。

對符合局部搜索條件的種群，先將種群中所有染色體按照式(7)目標(biāo)函數(shù)值升序排列，再根據(jù)文獻(xiàn)[16]所采用的方法篩選出需進(jìn)行領(lǐng)域搜索的染色體。這種篩選方法可保證較優(yōu)和較差的方案均有一定的概率被選中，但是較優(yōu)的方案有更大的概率被選中，從而保證在加快收斂速度的同時避免局部收斂。

局部搜索的領(lǐng)域結(jié)構(gòu)采用兩兩交換結(jié)構(gòu)，即在選定的染色體中隨機(jī)選取某一階段的任意兩個設(shè)備，交換其位置。比較交換前后染色體的目標(biāo)函數(shù)值，將較優(yōu)者保留在種群中，同時記錄這兩個設(shè)備的位置，在之后的λ次搜索中不改變其位置。如果重復(fù)θ次搜索之后仍未獲得更優(yōu)的方案，則放棄該染色體搜索，進(jìn)入下一個選定染色體的局部搜索。

3　算例測試

3.1不等面積設(shè)備布局問題測試

本文分別就解決不等面積設(shè)備靜態(tài)布局和不確定需求下的動態(tài)布局問題與文獻(xiàn)案例進(jìn)行對比分析，從而驗證所提方法的有效性。

以文獻(xiàn)[17]中的案例(記為算例1)作為測試算例進(jìn)行求解。算例1中共有12個設(shè)備組和一個原料堆放組，各個設(shè)備的尺寸不等，設(shè)備尺寸和物流量等相關(guān)信息在文獻(xiàn)[17]中均有詳述。取種群規(guī)模N0=100，交叉概率pc=0.8，突變概率pm=0.3，最大迭代數(shù)imax=100，在CPU主頻2.2 GHz，內(nèi)存4 G，Window 7操作系統(tǒng)下進(jìn)行求解。獲得最優(yōu)解的布局方案如圖10所示，圖11為算法收斂圖。

圖10　算例1布局方案圖

圖11　算例1收斂圖

由圖11可看出，采用本文提出的改進(jìn)遺傳算法能夠在有限的迭代次數(shù)內(nèi)獲得最優(yōu)解或近最優(yōu)解，并能有效避免局部收斂。兩種算法運(yùn)算結(jié)果對比列于表1，由于在遺傳算法中增加了自適應(yīng)局部搜索，搜索方向性更強(qiáng)，因此能夠在較少的迭代次數(shù)中獲得最優(yōu)解。

表1　算例1兩種算法運(yùn)算結(jié)果對比

3.2不確定需求下的動態(tài)布局問題測試

算例1驗證了所提算法在解決不等面積設(shè)備布局問題的有效性，為進(jìn)一步驗證算法解決不確定需求下設(shè)備動態(tài)布局的有效性，采用文獻(xiàn)[7]的案例進(jìn)行測試。文獻(xiàn)[7]采用遺傳算法解決不確定需求環(huán)境下的動態(tài)布局問題，但是布局模型是離散式模型，共有3個案例，選取其中含有12個設(shè)備(記為算例2)和30個設(shè)備(記為算例3)的兩個算例進(jìn)行求解，兩種方法獲得的結(jié)果如表2所示。

表2　算例2和算例3的兩種算法結(jié)果對比

由表2可知，在算例2和算例3中，改進(jìn)遺傳算法均能獲得較優(yōu)方案，這是因為引入自適應(yīng)局部搜索，在次優(yōu)解的領(lǐng)域進(jìn)行搜索，增加了獲得更優(yōu)解的概率。

4　實(shí)例分析

4.1實(shí)例概述

為了從整體上更全面地驗證本文所提方法的有效性和實(shí)用性，以發(fā)動機(jī)缸蓋加工車間為實(shí)例，在不確定需求環(huán)境下進(jìn)行動態(tài)布局規(guī)劃。

某發(fā)動機(jī)廠擬新建一加工車間，需確定12個設(shè)備組的布局位置，設(shè)備組尺寸及單位距離重組費(fèi)用如表3所示。該車間計劃用于生產(chǎn)H1、H2、H3三種類型的缸蓋，三種產(chǎn)品的單位物流量矩陣已知，在可預(yù)見的各個生產(chǎn)階段的預(yù)測產(chǎn)量如表4所示。車間為34 m×28 m的矩形場地，相鄰設(shè)備間橫向最小間距h=1.5 m，縱向最小行間距s=2 m，設(shè)備與車間邊界橫向最小距離so x=2 m，縱向最小距離soy=2 m。

表3　設(shè)備尺寸信息

表4　產(chǎn)品預(yù)測需求量　件

4.2不確定需求描述

4.3算法參數(shù)設(shè)計及問題求解

根據(jù)車間實(shí)際約束要求，按照1.2節(jié)構(gòu)建多行線性設(shè)備布局模型。優(yōu)化算法的參數(shù)設(shè)置如下：種群規(guī)模200，交叉概率0.85，變異概率0.3；自適應(yīng)局部搜索的相關(guān)參數(shù)設(shè)置δ=0.6，λ=20，θ=60。以式(7)為優(yōu)化目標(biāo)，對實(shí)例問題進(jìn)行求解。獲得方案總費(fèi)用值用三角模糊數(shù)表示為(3.85×107,4.16×107,4.45×107)，布局方案如圖12所示，圖13是求解過程的算法收斂圖。

圖12　動態(tài)布局方案圖

圖13　實(shí)例求解過程收斂圖

4.4結(jié)果分析

實(shí)例問題如果采用靜態(tài)布局方法求解，獲得的最優(yōu)方案物料搬運(yùn)費(fèi)用值為4.26×107kg·m，而采用本文所提出的方法獲得的模糊總費(fèi)用值為(3.85×107,4.16×107,4.45×107)kg·m，可看出，兩種方案的費(fèi)用值基本在一個數(shù)值范圍內(nèi)且本文所提方法的結(jié)果更優(yōu)一些，由此可說明獲得的動態(tài)布局方案是一個有效方案。在圖12所示的動態(tài)布局方案中，設(shè)備根據(jù)實(shí)際尺寸在布局空間中分行布置，滿足設(shè)備間距和行間距要求，比較容易轉(zhuǎn)化為實(shí)際應(yīng)用。由圖13可看出，由于引入自適應(yīng)局部搜索，求解過程可較迅速地搜索到最優(yōu)解或近最優(yōu)解，從整體上驗證了所提出的方法在解決不確定需求下不等面積設(shè)備動態(tài)布局問題的有效性和實(shí)用性。

在動態(tài)布局規(guī)劃中考慮需求不確定性的影響是為了提升布局在面對未來產(chǎn)品需求波動時的性能穩(wěn)定性，以節(jié)省生產(chǎn)過程中的物料搬運(yùn)費(fèi)用。為進(jìn)一步驗證所獲得的布局方案在面對未來需求波動時的性能，通過隨機(jī)產(chǎn)生需求數(shù)據(jù)以模擬未來的需求波動，計算總費(fèi)用值，以靜態(tài)布局方案為參照進(jìn)行驗證。隨機(jī)產(chǎn)品需求數(shù)據(jù)列于表5，對應(yīng)的總費(fèi)用值列于表6。表5中，(1100，120，3000)指產(chǎn)品H1在生產(chǎn)階段1、2、3的需求分別為1100、120、3000。

表5　測試需求數(shù)據(jù)　件

表6　測試結(jié)果　kg·m

由表6可看出，在5組數(shù)據(jù)測試結(jié)果中，本文所提出方法獲得的布局方案較優(yōu)的有4組(加粗)，說明本文提出的方法可以獲得較高魯棒性的動態(tài)布局方案，應(yīng)對未來需求波動時性能穩(wěn)定。

5　結(jié)束語

傳統(tǒng)車間設(shè)備布局方法假設(shè)產(chǎn)品需求信息確定、物流量固定不變，忽視通過預(yù)測獲得的需求信息的不確定性及其隨時間增大特性的影響。本文針對現(xiàn)有布局方法存在的不足，從更利于轉(zhuǎn)化為生產(chǎn)實(shí)際應(yīng)用的角度出發(fā)，以基于柔性區(qū)域結(jié)構(gòu)并增加設(shè)備間距約束的多行線性布局為基礎(chǔ)，構(gòu)建不確定需求下的不等面積設(shè)備動態(tài)布局模型。在此基礎(chǔ)上，引入三角模糊數(shù)運(yùn)算與排序方法和自適應(yīng)局部搜索機(jī)制對遺傳算法進(jìn)行改進(jìn)，提出改進(jìn)遺傳算法。分別就不等面積設(shè)備靜態(tài)布局問題和不確定需求動態(tài)布局問題分別驗證所提算法的有效性。再以某發(fā)動機(jī)缸蓋加工車間為實(shí)例，應(yīng)用本文提出的方法獲得不確定需求下的動態(tài)布局方案，從整體上驗證所提方法的有效性和實(shí)用性。車間設(shè)備布局有較多評價指標(biāo)，本文僅以物料搬運(yùn)和設(shè)備重組費(fèi)用為優(yōu)化目標(biāo)進(jìn)行求解，在今后的研究中，可以著重研究不確定需求下設(shè)備動態(tài)布局的多目標(biāo)優(yōu)化技術(shù)，也可以進(jìn)一步提升算法的搜索效率以解決大規(guī)模設(shè)備布局問題。

[1]Tompkins J A. Facilities Planning[M]. Hoboken:John Wiley & Sons, 2010.

[2]Jr McKendall A R, Liu W H. New Tabu Search Heuristics for the Dynamic Facility Layout Problem[J]. International Journal of Production Research, 2012, 50(3): 867-878.

[3]Hosseini-Nasab H, Emami L. A Hybrid Particle Swarm Optimisation for Dynamic Facility Layout Problem[J]. International Journal of Production Research, 2013, 51(14): 4325-4335.

[4]祝恒云,葉文華. 模擬退火粒子群算法在動態(tài)單元布局中的應(yīng)用[J]. 中國機(jī)械工程,2009,20(2):181-185.

Zhu Hengyun, Ye Wenhua. Application of Particle Swarm Algorithm Based on Simulated Annealing in Variable Cellular Facility Layout Problems[J]. China Mechanical Engineering,2009,20(2):181-185.

[5]Balakrishnan J, Hung Cheng C. The Dynamic Plant Layout Problem: Incorporating Rolling Horizons and Forecast Uncertainty[J]. Omega, 2009, 37(1): 165-177.

[6]Samarghandi H, Taabayan P, Behroozi M. Metaheuristics for Fuzzy Dynamic Facility Layout Problem with Unequal Area Constraints and Closeness Ratings[J]. The International Journal of Advanced Manufacturing Technology, 2013, 67(9/12): 2701-2715.

[7]Drira A, Pierreval H, Hajri-Gabouj S. Design of a Robust Layout with Information Uncertainty Increasing Over Time: a Fuzzy Evolutionaryapproach[J]. Engineering Applications of Artificial Intelligence, 2013, 26(3):1052.

[8]McKendall A R, Hakobyan A. Heuristics for the Dynamic Facility Layout Problem with Unequal-area Departments[J]. European Journal of Operational Research, 2010,201(1):171-82.

[9]Mazinani M, Abedzadeh M, Mohebali N. Dynamic Facility Layout Problem Based on Flexible Bay Structure and Solving by Genetic Algorithm[J]. The International Journal of Advanced Manufacturing Technology, 2013,65(5):929-43.

[10]Drira A, Pierreval H, Hajri-Gabouj S. Facility Layout Problems: a Survey[J]. Annual Reviews in Control, 2007,31(2):255-67.

[11]Kulturel-Konak S. A Linear Programming Embedded Probabilistic Tabu Search for the Unequal-area Facility Layout Problem with Flexible Bays[J]. European Journal of Operational Research, 2012,223(3):614-25.

[12]周娜,宓為建,徐子奇,等. 基于改進(jìn)型自適應(yīng)遺傳算法求解設(shè)備多行布局問題[J]. 上海交通大學(xué)學(xué)報,2013,47(12):1924-1929.

Zhou Na, Mi Weijian, Xu Ziqi,et al. Solution to Multi-line Layout Problems of Equipment Based on Improved Adaptive Genetic Algorithm[J]. Journal of Shanhai Jiaotong University,2013,47(12):1924-1929.

[13]Ripon K S N, Glette K, H?vin M, et al. An Adaptive Local Search Based Genetic Algorithm for Solving Multi-objective Facility Layout Problem[M]. Berlin: Springer， 2010.

[14] Yun Y, Moon C, Kim D. Hybrid Genetic Algorithm with Adaptive Local Search Scheme for Solving Multistage-based Supply Chain Problems[J]. Computers & Industrial Engineering,2009,56(3):821-38.

[15]Fortemps P, Roubens M. Ranking and Defuzzification Methods Based on Area Compensation[J]. Fuzzy Sets and Systems, 1996, 82(3): 319-330.

[16]Rochat Y, Taillard é D. Probabilistic Diversification and Intensification in Local Search for Vehicle Routing[J]. Journal of Heuristics,1995,1(1):147-67.

[17]郭源源, 王謙, 梁峰. 基于粒子群優(yōu)化算法的車間布局設(shè)計[J]. 計算機(jī)集成制造系統(tǒng),2012,18(11):2476-2484.

Guo Yuanyuan, Wang Qian, Liang Feng. Facility Layout Design Based on Particle Swarm Optimization[J]. Computer Integrated Manufacture systems, 2012, 18(11):2476-2484.

(編輯袁興玲)

Dynamic Facility Layout Method under Uncertain Product Demands

Ma ShumeiCai HuisenZhang YifanLi Aiping

Tongji University,Shanghai,201804

The dynamic facility layout method combined with fuzzy set theory and improved genetic algorithm was brought out on the basis of considering the influences of uncertain product demands, aiming at the deficiency of the present dynamic facility layout method. The characteristics of product demand uncertainty change over time were analyzed, and the uncertain demands were described by the triangular fuzzy numbers. The dynamic layout was transformed into several static layouts through analyzed facility relocation process between each period so as to establish a dynamic facility layout model under uncertain demands based on flexible bays structure. An improved genetic algorithm was proposed by combined triangular fuzzy number operation and adaptive local search with genetic algorithm, and then solved dynamic facility layout problems with uncertain product demands and unequal area constraints; the target of the problem was minimum the total cost of material handling and facility relocation. At last，the examples were illustrated to verify the practicability and effectiveness of the given method．

uncertain demand; improved genetic algorithm; unequal area; dynamic facility layout

2014-12-23

國家科技重大專項(2013ZX04012-071)

TH165< class="emphasis_italic">DOI

：10.3969/j.issn.1004-132X.2015.11.012

馬淑梅，女，1967年生。同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院副教授、博士。主要研究方向為數(shù)字化設(shè)計與制造、逆向工程技術(shù)及快速原型制造技術(shù)等。蔡惠森，男，1990年生。同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院碩士研究生。張一帆，男，1992年生。同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院碩士研究生。李愛平，女，1951年生。同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院教授、博士研究生導(dǎo)師。