（四川大學(xué) 商學(xué)院 工業(yè)工程系，四川 成都 610065）

1 引言

物流緩存區(qū)作為制造系統(tǒng)的重要物流設(shè)施，主要從事大部分零部件的拆箱、揀選、配貨和送貨上線等作業(yè)。物流緩存區(qū)的科學(xué)合理布局，可以有效加快物料流動速度，同時降低物流強(qiáng)度，節(jié)省空間，節(jié)約10%-30%的物料運(yùn)輸費(fèi)用，為企業(yè)贏得競爭優(yōu)勢。所以，研究制造業(yè)物流緩存區(qū)的布局優(yōu)化問題具有重要的理論意義和應(yīng)用價(jià)值。

2 布局優(yōu)化模型和算法分析研究

2.1 問題描述

本文將物流緩存區(qū)的布局問題描述為:在物流緩存區(qū)的若干尺寸和上下游產(chǎn)線的若干尺寸已知的條件下，以各作業(yè)單位間的總物流最小和作業(yè)單位之間實(shí)際關(guān)聯(lián)度與理論關(guān)聯(lián)度之間的方差最小為目標(biāo)，建立布局優(yōu)化模型。

2.2 布局優(yōu)化問題數(shù)學(xué)模型的建立

影響生產(chǎn)系統(tǒng)布局的約束條件[1]主要有：

（1）間距約束：圖1為作業(yè)單位i與作業(yè)單位j之間的相對位置關(guān)系示意圖。圖中（xi，yi）為作業(yè)單位i的中心坐標(biāo)；li，wi為作業(yè)單位i在X方向和Y方向上的寬度；dxij，dyij為作業(yè)單位i與作業(yè)單位j在X方向和Y方向上的最小距離。

由圖2-1可得，該約束可表示為公式（1）和公式（2）：

圖1 各個作業(yè)單位間的相對位置關(guān)系

（2）邊界約束：每個作業(yè)單位在X方向和Y方向上的布局不能超過車間的長寬尺寸。L、W為整個布局面積的總長度和總寬度。

該約束表示為公式（3）和（4）：

2.3 布局優(yōu)化問題數(shù)學(xué)模型

目標(biāo)函數(shù)為公式（5）：

約束條件為（6）：

式中：

F1：各個作業(yè)單位之間總物流量函數(shù)；

F2：各個作業(yè)單位之間實(shí)際關(guān)聯(lián)度與理論關(guān)聯(lián)度之間的方差函數(shù)；

n：作業(yè)單位的個數(shù)；

fij：作業(yè)單位i與作業(yè)單位j之間的物流量；

dij：作業(yè)單位i與作業(yè)單位j之間的幾何距離（即曼哈頓距離），如公式（7）所示：

rij：作業(yè)單位i與作業(yè)單位j之間的理論綜合關(guān)聯(lián)度；依據(jù)系統(tǒng)布局設(shè)計(jì)程序（SLP），將作業(yè)單位間物流的相互關(guān)系與非物流的相互關(guān)系進(jìn)行合并，得到rij的量化值見表1。

表1 Rij量化值

特別定義當(dāng)i=j時，rij=0；

bij：作業(yè)單位i與作業(yè)單位j之間的實(shí)際關(guān)聯(lián)度，其值由作業(yè)單位i與作業(yè)單位j之間的實(shí)際距離dij和最大可能距離dmax決定；bij的值見表2，當(dāng)i=j時，即為同一個作業(yè)單位，dij=0。

表2 關(guān)聯(lián)因子

zij：0-1整數(shù)，由約束3來保證約束1和約束2只有一個表達(dá)式有效；xi，yi：作業(yè)單位 i的中心坐標(biāo)；li：作業(yè)單位i在X方向上的寬度；wi：作業(yè)單位i在Y方向上的寬度；dxij，dyij：作業(yè)單位i與作業(yè)單位 j在X 方向和Y方向上的最小距離；L：整個布局面積的總長度；W：整個布局面積的總寬度。

2.4 基于遺傳算法的布局優(yōu)化算法

（1）基于遺傳算法的布局優(yōu)化算法[2]的設(shè)計(jì)?？梢约僭O(shè)各個作業(yè)單位的形狀均為矩形。根據(jù)各個作業(yè)單位在車間的相對位置關(guān)系，設(shè)計(jì)成對的染色體，分別表示水平約束和垂直約束。例如：染色體1：lpopulation=[……,a,b……]表示矩形a在矩形b的左面；染色體2：wpopulation=[……,a,b……]表示矩形a在矩形b的下面；由此，用1，2，…，n表示各個作業(yè)單位，那么由lpopulation和wpopulation來表示布局優(yōu)化問題的空間解。那么得到的布局效果如圖2所示。

（2）基于遺傳算法的布局優(yōu)化算法的實(shí)現(xiàn)。使用MATLAB軟件進(jìn)行編程，算法步驟：

圖2 編碼效果

Step 1:輸入作業(yè)單位數(shù)N、各作業(yè)單位的長寬、車間的總長寬、作業(yè)單位間相關(guān)度rij；

Step 2:使用自然數(shù)編碼，隨機(jī)產(chǎn)生初始群體；

Step 3:判斷停止條件，如滿足停止條件，跳到Step 9；

Step 4:計(jì)算種群中每一個染色體的適應(yīng)度值；

Step 5:根據(jù)適應(yīng)度值，隨機(jī)選擇一些染色體構(gòu)成一個新種群；

Step 6:以交叉概率Pc和設(shè)計(jì)的交叉方法進(jìn)行交叉運(yùn)算；

Step 7:以變異概率Pm和設(shè)計(jì)的變異方法進(jìn)行變異運(yùn)算；

Step 8:計(jì)算群體中適應(yīng)度值最大的個體及其適應(yīng)度值，返回Step 3；

Step 9:輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的最優(yōu)解。

流程如圖3所示。

3 轎車總裝車間物流緩沖區(qū)布局優(yōu)化[3]

3.1 原型概述

某知名品牌汽車公司成都分公司其車間總面積為4 590m2，其中物流緩沖區(qū)為1 220m2，占整個車間面積的22.2%，使用手推車進(jìn)行物料搬運(yùn)。

3.2 數(shù)據(jù)采集與統(tǒng)計(jì)

該總裝車間的區(qū)域名稱、代碼、幾何尺寸、面積，各個作業(yè)單位間的物流強(qiáng)度見表3、表4。

3.3 布局及優(yōu)化過程[4]

（1）參數(shù)確定。需要確定的參數(shù)有理論綜合關(guān)聯(lián)度rij、種群大小popsize、最大進(jìn)化代數(shù)maxgen、交叉概率pc、變異概率pm。

圖3 Matlab求解流程圖

表3 作業(yè)單位參數(shù)

表4 作業(yè)單位間的物流強(qiáng)度

①物流分析。將各作業(yè)單位對的物流強(qiáng)度按大小排序，根據(jù)表4，得到原始物流相關(guān)表5。

②非物流分析。首先，界定各作業(yè)單位間的關(guān)系，包括工藝流程、物流聯(lián)系、工作性質(zhì)形似性等因素；其次，確定各個作業(yè)單位之間相互關(guān)系的影響因素，評價(jià)各個作業(yè)單位之間的相互關(guān)系等級；最后，得出作業(yè)單位非物流相互關(guān)系見表6。

③綜合關(guān)聯(lián)度RIJ。確定物流與非物流相互關(guān)系相對重要性，即加權(quán)值m:n=1:1；量化物流與非物流相互關(guān)系等級；根據(jù)表5和表6，綜上分析可得各個工作單位間的綜合關(guān)聯(lián)度見表7。

表5 物流強(qiáng)度分析表

表6 作業(yè)單位非物流相互關(guān)系表

表7 作業(yè)單位間的綜合關(guān)聯(lián)度

（2）其他參數(shù)

①種群規(guī)模的大小可在[20,100]進(jìn)行選擇，選擇種群大小popsize=80。

②遺傳算法的最大進(jìn)化代數(shù)[100，500]；取最大進(jìn)化代數(shù)maxgen=200。

③pc一般取為[0.4,0.99]，選取pc=0.9。

④增大pm，增加解空間的多樣性，可得收斂全局最優(yōu)解；但當(dāng)變異概率值過大時，會破壞種群中的優(yōu)良性；pm的取值范圍[0.000 1,0.1]；選取pm=0.1。

綜合上述分析，得遺傳算法的參數(shù)如表8所示。

（3）模型求解

①主要變量定義。popsize:種群大小；maxgen：最大進(jìn)化世代數(shù)；lchrom：染色體長度；pc、pm：交叉概率和變異概率；a1、a2：總物流量權(quán)重和方差權(quán)重；ZL、ZW：整個車間的總長和總寬；L、W：各個工作單位的長度和寬度，表示為矩陣形式；d：走道的寬度；lpopulation,wpopulation：成對的染色體；lpopselect,wpopselect：選擇后的染色體解；lpopcross,wpopcross：交叉后的染色體解；lpopmutate,wpopmutate：變異后的染色體解；fitness：適應(yīng)度值；currentbest：當(dāng)前最佳適應(yīng)度值；bestind：最佳個體；bestfit：最佳個體的適應(yīng)度；bestever：最佳個體產(chǎn)生世代數(shù)。

表8 遺傳算法參數(shù)表

②功能函數(shù)。initpop()：初始化函數(shù)；objvalue():計(jì)算目標(biāo)函數(shù)值；fitvalue():計(jì)算適應(yīng)度；best():選擇最佳個體；select():選擇操作；cross()：交叉操作；mutate()：變異操作；

③MATLAB中遺傳算法主程序代碼。主程序運(yùn)行結(jié)果見圖4，從圖中得知：生產(chǎn)線U型布局，兩個緩存區(qū)5和6鄰近布置，可以大大簡化運(yùn)輸作業(yè)，方便工人多工序操作，節(jié)約物流成本。

圖4 MATLAB運(yùn)行結(jié)果

4 結(jié)論

本文建立了物流緩存區(qū)布局的優(yōu)化模型；應(yīng)用遺傳算法，并利用MATLAB進(jìn)行求解，得到物流緩存區(qū)優(yōu)化布局。該方案運(yùn)行效果顯著，物流緩存區(qū)的布局科學(xué)合理。

[1]朱耀祥,朱立強(qiáng).設(shè)施規(guī)劃與物流[M].北京:機(jī)械工業(yè)出版社,2003.

[2]王蓀馨.基于遺傳算法的作業(yè)車間設(shè)備布局優(yōu)化方法[J].工業(yè)工程,2009,12(3).

[3]葉慕靜,周根貴.基于遺傳算法的系統(tǒng)布置設(shè)計(jì)及初步應(yīng)用[J].工業(yè)工程,2005,(5).

[4]龔全勝,李世其.基于遺傳算法的制造系統(tǒng)設(shè)備布局設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用,2004,(26).