基于遺傳算法的車間設(shè)備布局優(yōu)化

李 琳

（上海海事大學(xué) 工程訓(xùn)練中心，上海 201306）

0 引言

車間設(shè)備布局是否合理直接影響著生產(chǎn)節(jié)奏，對(duì)生產(chǎn)效率起到長(zhǎng)期的影響。有資料統(tǒng)計(jì)，在制造型企業(yè)中，大約有20%～50%的生產(chǎn)費(fèi)用是花費(fèi)在物料運(yùn)輸中的，而合理的設(shè)備布局和物料搬運(yùn)設(shè)計(jì)可以有效減少這部分費(fèi)用，大約減少10%～30%的生產(chǎn)成本，提高生產(chǎn)效率；另外在車間生產(chǎn)中，從產(chǎn)品原材料投入到最后的生產(chǎn)完成，在這個(gè)生產(chǎn)周期過程中，物料平均只有15%左右的時(shí)間是在加工設(shè)備上的，而其余的85%左右的時(shí)間都在搬運(yùn)中或在倉(cāng)庫(kù)中，但是對(duì)生產(chǎn)車間設(shè)施進(jìn)行合理規(guī)劃之后，能加快物料加工的速度，有效減少產(chǎn)品搬運(yùn)時(shí)間，縮短產(chǎn)品生產(chǎn)周期。所以研究出一種優(yōu)良的車間設(shè)施布局優(yōu)化方案的方法，對(duì)于現(xiàn)代制造型企業(yè)有著重要的現(xiàn)實(shí)意義和應(yīng)用價(jià)值。

1 車間設(shè)備布局模型的建立

假設(shè)某車間一共有m臺(tái)設(shè)備，則設(shè)備集合S={s1,s2,...,sm}所有設(shè)備設(shè)置在n行上。

如圖1所示，建立車間設(shè)備布局模型。

L：車間的長(zhǎng)度；

W：車間的寬度；

i：車間設(shè)備布局的行列；

圖1 設(shè)備布局模型

t(i)：設(shè)備布置在第t行第i個(gè)位置；

xt(i)：第 t 行第 i 個(gè)位置上的設(shè)備St(i)的 x 坐標(biāo)值；

yt(i)：第 t 行的第 i 個(gè)位置上的設(shè)備St(i)的 y 坐標(biāo)值；

lt(i)：設(shè)備St(i)的長(zhǎng)度；

wt(i)：設(shè)備St(i)的寬度；

d(t(i),t(i+1))：設(shè)備St(i)和它相鄰的設(shè)備St(i+1)之間在X軸方向上的間距。

h(t(i),(t+1)(j))：設(shè)備St(i)和第 t+1 行的第 j 個(gè)設(shè)備S(t+1))(j)在Y軸方向上的間距；

引入一個(gè)變量kit：

其中i=1,2,...,m；t=1,2,...,n。

滿足kit=1 的設(shè)備組成了第t 行的設(shè)備集合，設(shè)為第t行的設(shè)備總和。

本文車間設(shè)備布局車間總物流成本最小為目標(biāo)函數(shù)。

車間總物流成本函數(shù)可表達(dá)為：

當(dāng)設(shè)備i和設(shè)備j在同一行：Dij=|xi-xj|

當(dāng)設(shè)備i和設(shè)備j不在同一行：Dij=|xi-xj|+|yi-yj|

C：車間內(nèi)總物流成本

Cij：設(shè)備i和設(shè)備j之間物料搬運(yùn)的單位距離成本

已知量：

Fij：設(shè)備i和設(shè)備j之間的物料量

通過分析計(jì)算可得：

Dij：設(shè)備i和設(shè)備j之間的最小距離

（1）長(zhǎng)度方向上的約束條件，各設(shè)備只能被布置在同一行內(nèi)，而且只能被布置一次。

（2）寬度方向上的約束條件，被布置在同一行的設(shè)施的Y坐標(biāo)都相等：

式中，Yt為第t行設(shè)備對(duì)應(yīng)的y坐標(biāo)。

（3）設(shè)備間的間隔約束，相鄰的設(shè)備之間要保持一定的距離，不出現(xiàn)相鄰設(shè)備發(fā)生碰撞或者重疊。

①保證設(shè)備在x方向上不出現(xiàn)碰撞或者重疊：

當(dāng)i=0 時(shí)，St(0)表示為第t 行開始的墻壁，則lt(0)=0，xt(0)=0，第一個(gè)位置的設(shè)備與車間墻壁之間的最小距離d(t(0),t(1))，不能發(fā)生碰撞。

當(dāng)i=g(t)時(shí)，St(g(t)+1)表示為第t行結(jié)束處的墻壁，則lt(g(t)+1)=0，xt(g(t)+1)=L，最后一個(gè)位置的設(shè)備與車間墻壁之間的最小距離d(t(g(t)),t(g(t)+1))，不能發(fā)生碰撞。

②保證設(shè)備在y方向上不出現(xiàn)碰撞或者重疊。

當(dāng)滿足條件：

則進(jìn)行以下約束：

當(dāng)t=0 時(shí)，則w0(i)=0，Y0=0，第一行的設(shè)備與車間墻壁之間的最小距離h(0(i),1(j))，不能發(fā)生碰撞。

當(dāng)t=n時(shí),，則w(n+1)(j)=0，Yn+1=W，最后一行設(shè)備與車間墻壁之間的最小距離h(n(i),(n+1)(j))，不能發(fā)生碰撞。

在本文所研究的車間問題中，設(shè)備間存在通道進(jìn)行工件和人員的流動(dòng)，所以設(shè)備i 和設(shè)備j 之間如果存在通道，則存在以下約束條件：

b：通道寬度。

2 基于遺傳算法的目標(biāo)函數(shù)求解

2.1 構(gòu)造基因編碼和染色體

本文的研究對(duì)象屬于多行車間設(shè)備布局問題。對(duì)于多行車間設(shè)備布局問題，通常采用的編碼方式為：

n：設(shè)備序列中開始分行的位置；

St(i)：設(shè)備t(i)的編號(hào)；

Δt(i)：設(shè)備t(i)和設(shè)備t(i-1)之間的凈間距，為實(shí)際間距和最小間距之差。

本文在多行車間設(shè)備布局編碼設(shè)計(jì)中采用自動(dòng)換行編碼方式，方法為計(jì)算設(shè)備的X坐標(biāo)xt(i)和長(zhǎng)度的一半lt(i)2 之和，再加上設(shè)備與墻壁的最小間距，如果值大于車間的總長(zhǎng)度L，則自動(dòng)將該設(shè)備排入第二行，依此類推。

則本文的編碼方式為：

2.2 適應(yīng)度函數(shù)設(shè)計(jì)

先要求出設(shè)備的x，y坐標(biāo)值。

（1）xt(i)的坐標(biāo)計(jì)算。

圖2 坐標(biāo)計(jì)算示意圖

圖中，xt(i)：設(shè)備St(i)的x 坐標(biāo)值；xt(i-1)：設(shè)備St(i-1)的x 坐標(biāo)值；d(t(i-1),t(i))：設(shè)備St(i)和它相鄰的設(shè)備St(i-1)之間在X軸方向上的間距；

如圖2 所示，設(shè)備St(i)的橫坐標(biāo)xt(i)為設(shè)備St(i-1)的橫坐標(biāo)xt(i-1)加上兩個(gè)設(shè)備之間的間距加上兩個(gè)設(shè)備的長(zhǎng)度和的一半，計(jì)算公式如下：

（2）yt(i)的坐標(biāo)計(jì)算。計(jì)算公式如下：

rt：車間設(shè)備行間距。

（3）適應(yīng)度函數(shù)。本文適應(yīng)度函數(shù)的函數(shù)設(shè)計(jì)為綜合目標(biāo)函數(shù)的倒數(shù)形式。將目標(biāo)函數(shù)轉(zhuǎn)換為適應(yīng)度函數(shù)需要考慮約束條件，因此采用引入懲罰項(xiàng)P。適應(yīng)度函數(shù)為：

2.3 設(shè)計(jì)遺傳操作

（1）選擇算子。選擇算子是遺傳算法求解過程中產(chǎn)生新種群的過程。操作步驟如下：①計(jì)算種群中所有個(gè)體的適應(yīng)度值，從大到小按順序排列，保留前10%的個(gè)體放入下一代種群中，這些個(gè)體不進(jìn)行交叉和變異操作。②對(duì)剩下90%的個(gè)體采用輪盤賭方法進(jìn)行選擇操作，并在之后進(jìn)行交叉和變異操作。③計(jì)算個(gè)體復(fù)制到下一代的概率Pi，計(jì)算公式為：

fi：個(gè)體i的適應(yīng)度值。

（2）交叉算子。根據(jù)車間設(shè)備布局的實(shí)際情況，采用雙點(diǎn)交叉，再結(jié)合修復(fù)程序的部分匹配交叉操作。假設(shè)在車間設(shè)備布局過程中一共有10 臺(tái)設(shè)備，每個(gè)染色體有10個(gè)基因，代表設(shè)備編號(hào)，則交叉操作步驟如下：

①在種群中隨機(jī)選擇兩條染色體為父代1 和父代2，隨機(jī)選擇兩個(gè)交叉點(diǎn)，如圖2所示選中位置3和位置7。

圖3 隨機(jī)選擇交叉點(diǎn)

②兩個(gè)交叉點(diǎn)之間的基因串進(jìn)行交換，產(chǎn)生新的染色體，從而得到子代1 和子代2。如圖4 所示將位置3至位置7之間的編號(hào)全部互相交換。

圖4 交叉操作

③確定映射關(guān)系，如圖5所示。

圖5 映射關(guān)系

④由圖3 可以發(fā)現(xiàn)新生成的兩個(gè)染色體中有重復(fù)的序號(hào)，所以需要對(duì)染色體進(jìn)行修復(fù)，使染色體合法，即不能有重復(fù)的設(shè)備編號(hào)。例如，子代1中位置2和位置5 都為編號(hào)2，位置4 和位置8 都為編號(hào)8，此時(shí)需要修復(fù)染色體。經(jīng)過修復(fù)最后結(jié)果如圖6。

根據(jù)映射關(guān)系修復(fù)子代：

圖6 修復(fù)染色體

（3）變異算子。變異的主要目的是增加染色體的多樣性，避免結(jié)果陷入局部最優(yōu)。變異概率通常取0.001～0.01之間。

本文使用的變異操作為反轉(zhuǎn)變異，操作步驟是：在染色體中選取兩個(gè)變異點(diǎn)（如圖7 位置4 和7），然后將兩個(gè)變異操作點(diǎn)位置4 到位置7 之間的基因字符順序反轉(zhuǎn)，得到新的染色體。

圖7 變異操作

3 應(yīng)用研究

3.1 車間概況

上海海事大學(xué)機(jī)械加工車間總長(zhǎng)為30m，寬為24m，總面積為720m2。

設(shè)備尺寸見表1。

表1 設(shè)備信息表

根據(jù)同種類型的原則將這些設(shè)備總共分為以下幾個(gè)設(shè)備單元，單位需求面積為設(shè)備面積加上操作需求面積，設(shè)備單元間水平最小間距要求為1.5m。

3.2 生產(chǎn)工藝流程分析

根據(jù)車間產(chǎn)品的工藝生產(chǎn)流程得出車間的物流信息。該車間產(chǎn)品屬于多品種小批量生產(chǎn)類型。零件加工流程見表3。

根據(jù)零件加工流程順序可以得出零件加工設(shè)備流轉(zhuǎn)表，見表4。

根據(jù)零件加工工藝流程結(jié)合物流分析方法，建立設(shè)備相互之間的物流量從至表。行表示物料搬運(yùn)的起始點(diǎn)，列表示物料搬運(yùn)的目的點(diǎn)，單元內(nèi)數(shù)學(xué)表示設(shè)備間的物料搬運(yùn)量，見表5。

表2 車間設(shè)備單元面積需求

表3 零件加工流程表

在加工過程中，在設(shè)備之間進(jìn)行零件的運(yùn)輸。每個(gè)設(shè)備間的搬運(yùn)費(fèi)用不同，表6為設(shè)備間物料搬運(yùn)費(fèi)用，這里只討論有搬運(yùn)行為設(shè)備間的物料搬運(yùn)費(fèi)用。

3.3 SLP建立初始布局方案

在使用遺傳算法求解之前，使用SLP方法對(duì)車間的物流相互關(guān)系進(jìn)行分析,確定車間的作業(yè)單元位置相關(guān)圖和面積相關(guān)圖，得到了車間初始布局方案。

通過分析各設(shè)備單元間的物流量和物流強(qiáng)度等級(jí)比例劃分，以及分析各作業(yè)單元之間的物流路線，生成物流強(qiáng)度分析表，見表7。

根據(jù)上面的物流強(qiáng)度分析表，繪制車間的各個(gè)設(shè)備單元的物流相關(guān)圖，如圖8所示。

表4 零件加工設(shè)備流轉(zhuǎn)表

表5 物流量從至表（g）

表6 設(shè)備間物料搬運(yùn)費(fèi)用（g/m）

確定了設(shè)備單元物流相互關(guān)系后，這里為了簡(jiǎn)化布局設(shè)計(jì)就不考慮設(shè)備單元非物流相互關(guān)系，最后生成相互關(guān)系表，計(jì)算設(shè)備間的接近程度值，見表8。

根據(jù)設(shè)備單元相互關(guān)系表，按照作業(yè)單元關(guān)系的重要程度進(jìn)行布局排列，首先布置A等級(jí)，然后再布置E、I、O、U等級(jí)，當(dāng)同時(shí)出現(xiàn)兩個(gè)等級(jí)時(shí)，結(jié)合單元的接近程度和需求面積進(jìn)行比較。比如A等級(jí)的設(shè)備單元對(duì)有1-5，2-6，5-7，包含4個(gè)設(shè)備單元。設(shè)備單元5 出現(xiàn)2 次，優(yōu)先布置，其余根據(jù)接近程度值進(jìn)行排序，根據(jù)設(shè)備單元的物流強(qiáng)度和設(shè)備單元需求面積布置其余的設(shè)備單元。得出最終的設(shè)備單元布局順序?yàn)?-2-6-1-7-10-9-8-4-3。

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

圖8 設(shè)備單元物流相互關(guān)系表

根據(jù)SLP 方法設(shè)計(jì)得到的并不是符合實(shí)際情況的方案，還需要根據(jù)實(shí)際生產(chǎn)約束條件對(duì)其做出相應(yīng)的位置調(diào)整，最后在AutoCAD 中繪制出調(diào)整后的車間布局方案，調(diào)整后的車間布局方案如圖9所示。

表8 設(shè)備單元相互關(guān)系表

圖9 車間布局方案

3.4 運(yùn)用Matlab進(jìn)行編程和求解

在Matlab 的運(yùn)行環(huán)境中，設(shè)置遺傳算法的控制參數(shù)，設(shè)定初始種群大小nchr 為50，交叉概率Pc 為0.6，變異概率Pm為0.1，最大迭代次數(shù)G為250。

在Matlab R2015a中經(jīng)過10次運(yùn)算，染色體見表9。

在表9 的數(shù)據(jù)表中取目標(biāo)函數(shù)較小的序號(hào)9 染色體{(4，6，9，8，2，7，5，10，3，1)，(1.405 5，1.207 0，0.187 2，0.083 0，0.047 2，0.234 9，0.114 3，1.391 0，0.040 1，1.019 4)}。迭代次數(shù)和最優(yōu)目標(biāo)函數(shù)值曲線如圖10。

通過迭代次數(shù)和最優(yōu)目標(biāo)函數(shù)值曲線可知，在第210代目標(biāo)函數(shù)值趨于穩(wěn)定且最優(yōu)化，即得到最優(yōu)化的染色體，此時(shí)目標(biāo)函數(shù)值為1.66×106。經(jīng)過解碼后的設(shè)備布局圖如圖11所示。

最后結(jié)合車間的設(shè)備，在AutoCAD 中繪出最終完整的車間布局圖，如圖12。

表9 運(yùn)算結(jié)果數(shù)據(jù)表

通過Matlab 計(jì)算求出的車間設(shè)備布局的優(yōu)化方案和系統(tǒng)布置設(shè)計(jì)生成的方案進(jìn)行對(duì)比，從車間內(nèi)產(chǎn)品物流情況角度對(duì)優(yōu)化前和優(yōu)化后進(jìn)行分析，得出結(jié)論。

圖10 迭代次數(shù)和最優(yōu)目標(biāo)函數(shù)值曲線

圖11 車間布局圖

圖12 最終車間布局圖

計(jì)算前后方案中各個(gè)設(shè)備之間的物料搬運(yùn)距離，物料搬運(yùn)距離由原來的248.25m 降到優(yōu)化后181.27m，減少了27%。計(jì)算前后方案中各個(gè)設(shè)備之間的物流成本，物流成本由原來的2 317 894 降到優(yōu)化后2 197 913，減少了5.2%。

4 結(jié)語(yǔ)

本文以機(jī)械加工車間設(shè)備布局設(shè)計(jì)過程為主線，研究了車間布局方法，并根據(jù)實(shí)際生產(chǎn)情況設(shè)計(jì)合理的車間布局方案，應(yīng)用系統(tǒng)布置設(shè)計(jì)方法(SLP)對(duì)車間進(jìn)行初步布局設(shè)計(jì)，通過對(duì)所要加工的工件、產(chǎn)量、工藝流程、設(shè)備的分析，分析車間內(nèi)各個(gè)作業(yè)單元之間的相互關(guān)系，并繪制車間作業(yè)單元面積相關(guān)圖和車間作業(yè)單元位置相關(guān)圖，建立初步布局方案。應(yīng)用遺傳算法對(duì)車間進(jìn)行布局設(shè)計(jì)，將SLP中形成的布局方案作為遺傳算法的初始解，通過選擇操作、交叉操作和變異操作，應(yīng)用MATLAB軟件進(jìn)行編程及運(yùn)行計(jì)算，形成更合理的車間布局方案，進(jìn)而可以避免使用遺傳算法時(shí)陷入局部最優(yōu)解的情況。