基于遺傳算法的多目標(biāo)雙行車間布局改善方法

牛占文，劉 晗

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

車間設(shè)施布局問題對生產(chǎn)成本有巨大的影響，一個好的設(shè)施布局可以降低企業(yè)近50%的運(yùn)營成本［1］。最簡單原始的布局問題是所有設(shè)備在一行中，只考慮設(shè)備的排布順序，目標(biāo)是使車間物料搬運(yùn)成本最低。在此基礎(chǔ)上，HASSAN 對多行設(shè)施布局問題進(jìn)行了研究［2］。KIM 和RAJASEKHARAN等在研究設(shè)施布局問題時引入了各個設(shè)備搬運(yùn)出入點(diǎn)的概念［3-4］。FICKO 和KUMAR 等考慮到了車間中的通道對設(shè)施布局的影響［5-6］。設(shè)施布局問題是一個NP 難題，因此很多啟發(fā)式算法應(yīng)用于該問題的求解。BANERJEE 等將遺傳算法應(yīng)用于設(shè)施布局問題的求解［7］。其后，GEN 等給出了針對設(shè)施布局問題的經(jīng)典編碼方式［8］。國內(nèi)清華大學(xué)學(xué)者于瑞峰等對編碼方式進(jìn)行了優(yōu)化［9］，去除了冗余編碼。DILIP 等又對原有遺傳算法進(jìn)行了改進(jìn)［10］，提高了算法的準(zhǔn)確性與效率。

筆者針對雙行布局問題，不再從傳統(tǒng)視角出發(fā)，即車間中尚未有任何設(shè)備，設(shè)施布局在一空白的空間中進(jìn)行，而是在原有設(shè)施布局的基礎(chǔ)之上進(jìn)行改善，因此在以傳統(tǒng)的物料搬運(yùn)成本作為目標(biāo)函數(shù)的同時，還要考慮到設(shè)備移動的成本。精益生產(chǎn)中強(qiáng)調(diào)生產(chǎn)時間，因此還將通過生產(chǎn)節(jié)拍轉(zhuǎn)化的效率函數(shù)作為第3 個目標(biāo)。

1 雙行車間布局改善問題描述

所謂的車間布局改善問題是指在原有的企業(yè)正在使用的車間布局的方案基礎(chǔ)之上，通過改變車間各個設(shè)施的位置，從而節(jié)約企業(yè)的成本。車間布局改善問題不同于車間布局規(guī)劃問題，車間布局改善問題需要考慮到原有車間布局方案，受到原有方案的限制，如由于某些制造單元移動困難，在改善時無法更改其原有位置;由于運(yùn)輸工具的限制，通道的位置和寬度無法更改等。同時，車間布局改善問題的目標(biāo)也不同于車間布局規(guī)劃問題。傳統(tǒng)的車間布局規(guī)劃僅需考慮一個目標(biāo)，即最小化車間內(nèi)部的運(yùn)輸成本［11］;而車間布局改善問題除此之外還應(yīng)考慮制造單元移動造成的成本和制造單元移動后生產(chǎn)效率的提升。雙行車間布局的布局結(jié)構(gòu)是指車間形狀為矩形，車間被一條通道分為雙行，車間各設(shè)施沿通道布置，車間中各設(shè)施也為矩形，長寬已知，忽略細(xì)節(jié)形狀。各設(shè)施的出入點(diǎn)為沿通道邊中點(diǎn)。雙行車間布局問題的研究不像傳統(tǒng)的簡單單行布局問題，與實(shí)際車間布局脫節(jié)，缺少指導(dǎo)作用。同時該研究也避免了多行布局問題中，在考慮到出入點(diǎn)和通道時會使問題過于復(fù)雜，模型難表示的問題。雙行布局問題在實(shí)際生產(chǎn)中經(jīng)常出現(xiàn)，并且在考慮到出入點(diǎn)和通道等因素時，仍可以比較簡潔地應(yīng)用數(shù)學(xué)模型表達(dá)。筆者的調(diào)研對象為河北某膠管企業(yè)的軟芯車間，其布局就是典型的雙行布局結(jié)構(gòu)。

2 雙行設(shè)施布局問題數(shù)學(xué)模型的建立

2.1 模型符號假設(shè)與說明

假設(shè)該車間共有n個制造單元;i，j為制造單元編號，i=1，2，…，n;j=1，2，…，n;xi為連續(xù)變量，表示i制造單元的橫坐標(biāo);yi為0 -1 整型變量;yi=0 表示制造單元i位于車間第一行;yi=1表示制造單元i位于車間第二行;x'i為工作單元i在原始布局中的橫坐標(biāo);y'i為工作單元i在原始布局中的行數(shù)，0 為第一行，1 為第二行;dij為制造單元i至制造單元j之間的距離;di0為制造單元i重新布置后的位置與其原始位置之間的距離;mij為制造單元i至制造單元j之間單次運(yùn)輸?shù)奈锪髁?cij為制造單元i至制造單元j之間單位距離的運(yùn)輸成本;c'i為制造單元i移動單位距離的成本;tij為制造單元i至制造單元j之間單月的運(yùn)輸次數(shù);vij為制造單元i至制造單元j之間的運(yùn)輸次數(shù);li為制造單元i的長度;L為車間長度;w為車間過道寬度;p為該公司單位產(chǎn)品的利潤;TT為該工廠的生產(chǎn)節(jié)拍。

其余符號將在文中相應(yīng)位置加以說明。

2.2 目標(biāo)與加權(quán)函數(shù)

2.2.1 問題的3 個目標(biāo)

(1)最小化車間內(nèi)部的運(yùn)輸成本為：

運(yùn)輸成本目標(biāo)中，單位成本與運(yùn)輸次數(shù)是固定的，因此，該目標(biāo)通過制造單元間距離的調(diào)整來達(dá)到優(yōu)化的目的。

(2)制造單元移動造成的成本為：

制造單元移動成本目標(biāo)中移動制造單元的單位距離成本是一定的，因此需要調(diào)整制造單元移動前后的位置變化以達(dá)到優(yōu)化，很明顯，這與上述目標(biāo)是相悖的。

(3)制造單元移動后生產(chǎn)效率的提升為：

效率成本將布局調(diào)整后車間每月的總運(yùn)輸時間作為目標(biāo)。

2.2.2 加權(quán)評價函數(shù)

其中，λi為權(quán)系數(shù)。不難看出，目標(biāo)1 與目標(biāo)2 都是成本的單位，以貨幣進(jìn)行衡量，而目標(biāo)3是時間單位，這些目標(biāo)具有各自特定的經(jīng)濟(jì)含義，因此，不論是特爾菲法、層次分析法還是DEA，都不如利用其之間的經(jīng)濟(jì)關(guān)系來確定權(quán)系數(shù)λi。

以λ1=1 即以目標(biāo)1 的單月總運(yùn)輸成本作為基準(zhǔn)來確定λ2與λ3。

λ2表示目標(biāo)2 的經(jīng)濟(jì)含義為布局調(diào)整機(jī)動制造單元所花費(fèi)的一次性成本，考慮到資金的時間成本，假設(shè)r為每月利率，m為管理者估計(jì)本次設(shè)施布局調(diào)整的持續(xù)時間(m的單位為月)。

λ3=sp/TT表示目標(biāo)3 的經(jīng)濟(jì)含義為該車間生產(chǎn)中，浪費(fèi)在搬運(yùn)上的時間，精益生產(chǎn)理論中強(qiáng)調(diào)時間的價值［12］，筆者在不考慮庫存、生產(chǎn)均衡和銷售情況下，簡單地將生產(chǎn)中的時間轉(zhuǎn)化為成本，s為該車間的產(chǎn)值在整個公司產(chǎn)值中所占的比例，p為單位產(chǎn)品的利潤，TT代表生產(chǎn)節(jié)拍，TT=有效生產(chǎn)時間/顧客需求，p/TT表示整個公司生產(chǎn)流程中多1 s 有效生產(chǎn)時間所多獲得的利潤。

2.3 約束

(1)制造單元在橫軸方向不可超出車間范圍。

(2)制造單元之間不可重疊。

3 雙行設(shè)施布局改善問題的改進(jìn)遺傳算法

3.1 編碼與解碼

3.1.1 編碼

染色體編碼主要由制造單元順序編碼和制造單元間距編碼構(gòu)成。制造單元順序編碼記錄車間按照從左至右，從上至下的各制造單元的排列順序，制造單元間距編碼記錄了制造單元間的間隔距離。如圖1 所示染色體編碼示意圖的制造單元布局記錄為：

圖1 染色體編碼示意圖

3.1.2 解碼

通過編碼求解橫縱軸坐標(biāo)，可知：

當(dāng)xsk＞L時，說明該行制造單元已經(jīng)超出了車間范圍，因此令：

3.2 函數(shù)

對于數(shù)學(xué)模型中的約束(1)，由于在解碼時，一旦在x軸方向超出了車間的范圍，車間布局就會自動換行，如果設(shè)施布局方案超出了車間的范圍，布局就會超出兩行，此時yn＞1，不滿足yn的定義域，因此，對于給定的染色體Ik，定義懲罰函數(shù)為：

對于約束(2)，由于Δ 的存在，顯然成立，不需要構(gòu)造懲罰函數(shù)。

3.3 適應(yīng)度函數(shù)尺度變換

正常的遺傳算法應(yīng)求解極大值問題，因此構(gòu)造傳統(tǒng)的適應(yīng)度函數(shù)應(yīng)為F(Ik)= -Uk-Pk，然而在計(jì)算過程中發(fā)現(xiàn)由于個別個體的適應(yīng)度過高，導(dǎo)致了早熟現(xiàn)象，因此通過適應(yīng)度函數(shù)尺度變化，得到的適應(yīng)度函數(shù)為：

在Matlab 中應(yīng)用遺傳算法工具箱求解時，系統(tǒng)默認(rèn)極小化目標(biāo)函數(shù)，因此將適應(yīng)度函數(shù)調(diào)整為：

3.4 遺傳操作

遺傳操作的步驟如下：

(1)生成初始種群?？梢圆捎秒S機(jī)方式生成初始種群。

(2)選擇。選擇方式采用錦標(biāo)賽選擇。在錦標(biāo)賽選擇方式中，隨機(jī)選擇一定數(shù)目的個體參加錦標(biāo)賽，適應(yīng)度函數(shù)大的個體會在競賽中取勝，從而被選作父個體。

(3)交叉。對于編碼中的順序編碼部分采用兩點(diǎn)交叉的交叉方式，具體交叉方式如下：

父個體1 為［3，4，2，8，|5，1，7|，6］

父個體2 為［5，1，6，7，|3，2，4|，8］

編碼第5、6、7位為交叉部分交叉后得到的子個體：

子個體為［3，4，2，8，|3，2，4|，6］

子個體有重復(fù)的編碼：3、2、4，對于這種情況，按照編碼的交叉方式對未交叉的部分進(jìn)行轉(zhuǎn)換：3→5，2→1，4→7;從而得到轉(zhuǎn)換后的子個體為［5，7，1，8，|3，2，4|，6］。

而對于間隔編碼部分采用中間重組的方式。在中間重組中，子個體按照式(17)產(chǎn)生：

式中：C為子個體;P1為父個體1;P2為父個體2;α 為一個比例因子，其取值范圍為［0，1］。

(4)變異。變異操作只針對間隔編碼，變異方式采用自適應(yīng)性的改進(jìn)變異方法［13-14］，取變異系數(shù)k為0.05，變異概率為：

4 實(shí)例計(jì)算及分析

應(yīng)用上述算法對A 車間的布局改善問題進(jìn)行求解。A 車間生產(chǎn)產(chǎn)品為軟芯膠管，車間長110 m，寬18.9 m，該車間共有12 個制造單元，其序號如表1 所示，其主要工序流程如圖2 所示，其原始車間布局如圖3 所示，該工廠的生產(chǎn)節(jié)拍為4.38 m/s，單位產(chǎn)品利潤為9.68 元/m，管理人員預(yù)計(jì)該布局調(diào)整需持續(xù)12 個月。

A 車間其他數(shù)據(jù)如表2 ～表6 所示。

表1 制造單元編號

圖2 A 車間工序流程圖

圖3 A 車間原始布局圖

表2 單元間的單位運(yùn)輸成本cij 元/m·kg

表3 單元間單次運(yùn)輸?shù)奈锪髁縨ij kg/次

表4 單元間的運(yùn)輸次數(shù)tij 次

表5 單元間的運(yùn)輸速度vijm/s

表6 各單元間的其他參數(shù)

應(yīng)用遺傳算法進(jìn)行計(jì)算，設(shè)定種群規(guī)模為100，懲罰值M取107，通過Matlab 軟件進(jìn)行計(jì)算，近似最優(yōu)解產(chǎn)生的代數(shù)為76 代，終止原因?yàn)樽顑?yōu)適值平均變化小于預(yù)設(shè)值，經(jīng)過解碼，得到近似最優(yōu)解為：

近似最優(yōu)解對應(yīng)目標(biāo)函數(shù)：U=430 810。A車間改善后設(shè)施布局如圖4 所示，計(jì)算實(shí)例的進(jìn)化過程如圖5 所示。

圖4 A 車間改善后設(shè)施布局圖

圖5 計(jì)算實(shí)例的進(jìn)化過程

從圖5 中可以看出，當(dāng)平均適值和最小適值穩(wěn)定時，最大適值仍有較大波動，說明種群仍有較好的多樣性，沒有陷入局部最優(yōu)。改善前后數(shù)據(jù)對比如表7 所示。

表7 改善前后數(shù)據(jù)對比

將改善前后3 個目標(biāo)通過目標(biāo)函數(shù)轉(zhuǎn)化為單位統(tǒng)一，可以對比每月成本。對比發(fā)現(xiàn)，在付出較少的固定性投資后，車間搬運(yùn)成本與生產(chǎn)效率都得到了有效的改善，總成本節(jié)約了59.0%。

5 結(jié)論

雙行車間布局是實(shí)際生產(chǎn)中常見的布局形式，筆者建立數(shù)學(xué)模型時，在考慮到傳統(tǒng)的車間搬運(yùn)成本的同時，引入了在布局改善問題中特有的設(shè)備移動固定成本和與生產(chǎn)節(jié)拍相關(guān)的生產(chǎn)效率成本。并且，為了進(jìn)一步貼近實(shí)際生產(chǎn)，在應(yīng)用遺傳算法求解過程中，考慮到了車間通道和制造單元出入點(diǎn)。通過實(shí)例計(jì)算，生產(chǎn)成本顯著降低。關(guān)于生產(chǎn)效率成本，可以進(jìn)一步進(jìn)行討論，考慮庫存情況和銷售情況后，可以進(jìn)一步優(yōu)化模型參數(shù)以貼近企業(yè)的實(shí)際情況，同時還可以從質(zhì)量、現(xiàn)金流等其他角度對生產(chǎn)效率成本進(jìn)行表述。

［1］TOMPKINS J A，WHITE J A，BOZER Y A，et al. Facilities planning［M］. New York：Wiley，1996：65-98.

［2］HASSAN M M D. Machine layout problem in modern manufacturing facilities ［J］. International Journal of Production Research，1994，32(11)：2559 -2584.

［3］KIM J G，KIM Y D. Layout planning for facilities with fixed shapes and input and output points［J］. International Journal of Production Research，2000，38(18)：4635 -4653.

［4］RAJASEKHARAN M，PETERS B A，YANG T. A genetic algorithm for facility layout design in flexible manufacturing systems［J］. International Journal of Production Research，1998，36(1)：95 -110.

［5］FICKO M，BREZOCNICK M，BALIC J. Designing the layout of singleand multiple -rows flexible manufacturing system by genetic algorithms［J］. Journal of Materials Processing Technology，2004(1)：150-158.

［6］KUMAR K R，HADJINICOLA G C，LIN T L. A heuristic procedure for the single-row facility layout problem［J］. European Journal of Operational Research，1995，87(1)：65 -73.

［7］BANERJEE P，ZHOU Y. Facilities layout design optimization with single loop material flow path configuration［J］. International Journal of Production Research，1995，33(1)：183 -204.

［8］GEN M，CHENG R. Genetic algorithms and engineering design［M］. New York：John Wiley ＆ Sons Inc，1997：87 -102.

［9］于瑞峰，王永縣，彭海.工作地中設(shè)施布局問題的改進(jìn)遺傳算法［J］.清華大學(xué)學(xué)報：自然科學(xué)版，2003，43(10)：1351 -1354.

［10］DILIP D，ANDRE R S，AMARAL，et al. Single row facility layout problem using a permutation - based genetic algorithm ［J］. European Journal of Operational Research，2011(213)：388 -394.

［11］AMINE D，HENRI P，SONIA H G. Facility layout problems：a survey［J］. Annual Reviews in Control，2007(31)：255 -267.

［12］大野耐一.豐田生產(chǎn)方式［M］.北京：中國鐵道出版社，2006：56 -87.

［13］王小平，曹立明.遺傳算法：理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安：西安交通大學(xué)出版社，2002：34 -87.

［14］鄭永前，張錦，王偉有.自適應(yīng)粒子群算法的制造單元集成布局方法［J］.工業(yè)工程與管理，2010，15(6)：58 -74.