基于遺傳算法的車間設備布局優化

李 琳

（上海海事大學 工程訓練中心，上海 201306）

0 引言

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

1 車間設備布局模型的建立

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

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

L：車間的長度；

W：車間的寬度；

i：車間設備布局的行列；

圖1 設備布局模型

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

xt(i)：第 t 行第 i 個位置上的設備St(i)的 x 坐標值；

yt(i)：第 t 行的第 i 個位置上的設備St(i)的 y 坐標值；

lt(i)：設備St(i)的長度；

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

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

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

引入一個變量kit：

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

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

本文車間設備布局車間總物流成本最小為目標函數。

車間總物流成本函數可表達為：

當設備i和設備j在同一行：Dij=|xi-xj|

當設備i和設備j不在同一行：Dij=|xi-xj|+|yi-yj|

C：車間內總物流成本

Cij：設備i和設備j之間物料搬運的單位距離成本

已知量：

Fij：設備i和設備j之間的物料量

通過分析計算可得：

Dij：設備i和設備j之間的最小距離

（1）長度方向上的約束條件，各設備只能被布置在同一行內，而且只能被布置一次。

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

式中，Yt為第t行設備對應的y坐標。

（3）設備間的間隔約束，相鄰的設備之間要保持一定的距離，不出現相鄰設備發生碰撞或者重疊。

①保證設備在x方向上不出現碰撞或者重疊：

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

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

②保證設備在y方向上不出現碰撞或者重疊。

當滿足條件：

則進行以下約束：

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

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

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

b：通道寬度。

2 基于遺傳算法的目標函數求解

2.1 構造基因編碼和染色體

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

n：設備序列中開始分行的位置；

St(i)：設備t(i)的編號；

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

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

則本文的編碼方式為：

2.2 適應度函數設計

先要求出設備的x，y坐標值。

（1）xt(i)的坐標計算。

圖2 坐標計算示意圖

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

如圖2 所示，設備St(i)的橫坐標xt(i)為設備St(i-1)的橫坐標xt(i-1)加上兩個設備之間的間距加上兩個設備的長度和的一半，計算公式如下：

（2）yt(i)的坐標計算。計算公式如下：

rt：車間設備行間距。

（3）適應度函數。本文適應度函數的函數設計為綜合目標函數的倒數形式。將目標函數轉換為適應度函數需要考慮約束條件，因此采用引入懲罰項P。適應度函數為：

2.3 設計遺傳操作

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

fi：個體i的適應度值。

（2）交叉算子。根據車間設備布局的實際情況，采用雙點交叉，再結合修復程序的部分匹配交叉操作。假設在車間設備布局過程中一共有10 臺設備，每個染色體有10個基因，代表設備編號，則交叉操作步驟如下：

①在種群中隨機選擇兩條染色體為父代1 和父代2，隨機選擇兩個交叉點，如圖2所示選中位置3和位置7。

圖3 隨機選擇交叉點

②兩個交叉點之間的基因串進行交換，產生新的染色體，從而得到子代1 和子代2。如圖4 所示將位置3至位置7之間的編號全部互相交換。

圖4 交叉操作

③確定映射關系，如圖5所示。

圖5 映射關系

④由圖3 可以發現新生成的兩個染色體中有重復的序號，所以需要對染色體進行修復，使染色體合法，即不能有重復的設備編號。例如，子代1中位置2和位置5 都為編號2，位置4 和位置8 都為編號8，此時需要修復染色體。經過修復最后結果如圖6。

根據映射關系修復子代：

圖6 修復染色體

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

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

圖7 變異操作

3 應用研究

3.1 車間概況

上海海事大學機械加工車間總長為30m，寬為24m，總面積為720m2。

設備尺寸見表1。

表1 設備信息表

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

3.2 生產工藝流程分析

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

根據零件加工流程順序可以得出零件加工設備流轉表，見表4。

根據零件加工工藝流程結合物流分析方法，建立設備相互之間的物流量從至表。行表示物料搬運的起始點，列表示物料搬運的目的點，單元內數學表示設備間的物料搬運量，見表5。

表2 車間設備單元面積需求

表3 零件加工流程表

在加工過程中，在設備之間進行零件的運輸。每個設備間的搬運費用不同，表6為設備間物料搬運費用，這里只討論有搬運行為設備間的物料搬運費用。

3.3 SLP建立初始布局方案

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

通過分析各設備單元間的物流量和物流強度等級比例劃分，以及分析各作業單元之間的物流路線，生成物流強度分析表，見表7。

根據上面的物流強度分析表，繪制車間的各個設備單元的物流相關圖，如圖8所示。

表4 零件加工設備流轉表

表5 物流量從至表（g）

表6 設備間物料搬運費用（g/m）

確定了設備單元物流相互關系后，這里為了簡化布局設計就不考慮設備單元非物流相互關系，最后生成相互關系表，計算設備間的接近程度值，見表8。

根據設備單元相互關系表，按照作業單元關系的重要程度進行布局排列，首先布置A等級，然后再布置E、I、O、U等級，當同時出現兩個等級時，結合單元的接近程度和需求面積進行比較。比如A等級的設備單元對有1-5，2-6，5-7，包含4個設備單元。設備單元5 出現2 次，優先布置，其余根據接近程度值進行排序，根據設備單元的物流強度和設備單元需求面積布置其余的設備單元。得出最終的設備單元布局順序為5-2-6-1-7-10-9-8-4-3。

表7 物流強度分析表

圖8 設備單元物流相互關系表

根據SLP 方法設計得到的并不是符合實際情況的方案，還需要根據實際生產約束條件對其做出相應的位置調整，最后在AutoCAD 中繪制出調整后的車間布局方案，調整后的車間布局方案如圖9所示。

表8 設備單元相互關系表

圖9 車間布局方案

3.4 運用Matlab進行編程和求解

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

在Matlab R2015a中經過10次運算，染色體見表9。

在表9 的數據表中取目標函數較小的序號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)}。迭代次數和最優目標函數值曲線如圖10。

通過迭代次數和最優目標函數值曲線可知，在第210代目標函數值趨于穩定且最優化，即得到最優化的染色體，此時目標函數值為1.66×106。經過解碼后的設備布局圖如圖11所示。

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

表9 運算結果數據表

通過Matlab 計算求出的車間設備布局的優化方案和系統布置設計生成的方案進行對比，從車間內產品物流情況角度對優化前和優化后進行分析，得出結論。

圖10 迭代次數和最優目標函數值曲線

圖11 車間布局圖

圖12 最終車間布局圖

計算前后方案中各個設備之間的物料搬運距離，物料搬運距離由原來的248.25m 降到優化后181.27m，減少了27%。計算前后方案中各個設備之間的物流成本，物流成本由原來的2 317 894 降到優化后2 197 913，減少了5.2%。

4 結語

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