基于可重構思路的智慧車間優(yōu)化布局算法

丁穗庭 王智偉 王思揚

（南京航空航天大學，南京 210000）

隨著智慧車間概念的提出，在多品種小批量的生產(chǎn)方式推動下，車間布局整體規(guī)劃越來越重要，日益強調(diào)可重構性，即根據(jù)生產(chǎn)要求快速調(diào)整設備和產(chǎn)線布局[1]。據(jù)Francis與White統(tǒng)計，固定而低效的車間設備布局會使搬運成本提高10%～30%，這不僅是企業(yè)巨大的浪費，也與當今智慧工廠追求高效敏捷的觀念不符[2]。

車間設備布局問題最早由Meller、Narayanan和Vance在1999年提出，定義設備布局問題是指對n個矩形設備在給定的矩形車間內(nèi)面向同一方向進行布間，使基于距離d的目標函數(shù)值最小[3]。近年來研究不斷深入，Kia R等當作多行布局進行研究，建立了一個群組布局設計模型[4]。曹陽華等對相關物流量劃分了物流等級，依據(jù)系統(tǒng)化設施布置（SLP）方法優(yōu)化車間布局[5]。朱永國等充分考慮零件的生產(chǎn)工藝，提出基于加工工藝的連桿類零件柔性制造車間設備布局方法[6]。但歸納起來，以往的解決方案存在兩個問題，一是優(yōu)化目標比較單一，通常只考慮物流成本最小一個因素，忽略了其他目標，如布局規(guī)整程度、空間占用率等的實現(xiàn)；二是由于車間設備布局問題是一種非線性規(guī)劃問題，也是一個NP難問題，用傳統(tǒng)啟發(fā)式算法如圖論法、構造法很難得到最優(yōu)解[7]。

針對這兩方面的問題，本文在構建布局模型時，重點考慮了布局規(guī)整程度等因素，以增強車間的布局冗余能力；在模型求解時，利用遺傳算法突出的尋優(yōu)能力，運用Matlab軟件進行求解[8]。

1 問題描述

本文進行布局優(yōu)化時，重點考慮物流費用以及布局規(guī)整程度。首先，毋庸置疑，物流費用要作為最主要的目標，根據(jù)已知的各產(chǎn)品的工藝路線，合理安排設備的擺放位置使物流成本最?。黄浯?，考慮布局的規(guī)整程度，對于多品種小批量式生產(chǎn)車間，對設備布局的柔性要求較高，布局時應盡可能規(guī)整（最終布局方案近似矩形），以增強車間的布局冗余能力。

假設有n臺設備，生產(chǎn)a種產(chǎn)品，每臺設備形狀均規(guī)則，長寬尺寸各不相同且已知，車間的長寬已知。在生產(chǎn)的過程中，設備與設備之間有不同的當量運輸量和運輸頻次。車間設備布局考慮的就是在生產(chǎn)a種產(chǎn)品的情況下，如何把這n臺設備安放在合理的位置，以滿足在一定的工序流程條件下，整個車間系統(tǒng)的面積利用效率最好。

2 布局模型

2.1 目標函數(shù)

設備布局問題為在布局盡可能規(guī)整的情況下要求物料運輸費用最優(yōu)化問題，即假設車間有n臺設備、a種產(chǎn)品，則問題可描述為以下數(shù)學模型。

式中，k表示產(chǎn)品的種類，一共有a種產(chǎn)品；i、j表示任意單次運輸?shù)那昂髢稍O備，一共有n臺設備；Qkij表示第k種產(chǎn)品從設備i到設備j的當量物流量；fkij表示產(chǎn)品k從設備i到設備j之間物流量發(fā)生的頻次；（xi，yi）、（xj，yj）表示設備i和設備j的中心點坐標；P是單位物流量的運輸成本（常數(shù)）。

2.2 約束條件

2.2.1 布局規(guī)整程度大于60%

布局規(guī)整程度用所有設備面積之和S0與布局占地面積S1之比表示。

其中，S0是所有設備面積和；S1是在最終布局方案中，一個能容納所有設備的最小矩形面積，該矩形的特點是頂點是由最左、最右、最上、最下設備的中心點決定。li、lj表示設備i、j的長；hi、hj表示設備i、j的寬。該約束的效果是最終的布局中，用最外圍設備（最左、最右、最上、最下）所確定的矩形盡可能小。

2.2.2 每臺設備只能出現(xiàn)一次

共有N臺設備，排列成R行，n=1，2，…，N，組成設備集合，r=1，2…，R，組成行數(shù)集合。設一個開關變量為：

滿足Ozr=1的設備構成了第r行的設備集合，則第r行的設備數(shù)為：

r（z）表示第r行的第z個設備，z=1，2，…，S（r），則每臺設備只出現(xiàn)一次表示為：

2.2.3 設備不出現(xiàn)重疊和交叉

行內(nèi)的約束條件為：

xr（i）表示第 r行設備 i中心點的橫坐標；lr（i）表示第r行設備i的長；d表示相鄰兩設備之間必須保持的最小間距，d≥0（常數(shù)）。此時將兩端墻壁視為設備r（0）和r（s（r）+1），則 l0=0，l（s（r）+1）=0，x0=0；x（s（r）+1）=L。

r=1，2…，R；Yr表示第r行對應的y坐標。

同一行中，設備的中心點位于同一水平線上，即中心點的y坐標相同。因此，列方向上不重疊表示為：

r=1，2，…，R；yr+1（i），yr（j）表示相鄰兩行各機床的縱坐標；hr（i）表示第r行設備的寬；h表示相鄰兩行設備之間必須保持的最小間距，h≥0（常數(shù)）。此時，兩端墻壁視為設備，y0=0，yR+1=H，y0和yR+1分別指始端和終端墻壁的y坐標。當r=0時，對于i=1，2，…，s（r），有hr（i）=0；當r=R 時，對于 i=1，2，…，s（r），有 h（r+1）（i）=0。

2.2.4 設備不超出車間范圍

行內(nèi)的約束條件為：

xs（r）表示第 r行中的最后一個的橫坐標；xr（1）表示第r行中的第1個的橫坐標；ls（r）表示第r行中的最后一個的長；lr（1）表示第r行中的第1個的長（r=1，2，…，R）；d表示相鄰兩設備之間必須保持的最小間距，同時也是距離墻壁的x方向最小距離，d≥0（常數(shù)）。

列內(nèi)的約束條件：

R表示所有設備最終布局的行數(shù)；h表示相鄰兩行設備之間必須保持的最小間距，同時也是距離墻壁的y 方向最小距離，h≥0（常數(shù)）；hR（i）表示最后一行中的第i個的寬，h1（i）表示第1行中的第j個的寬。

3 模型求解

遺傳算法是一種通過模擬自然進化過程搜索最優(yōu)解的方法，從多個初始解開始進行優(yōu)化，每個解稱為一個染色體，各染色體之間通過競爭、合作、單獨變異，不斷進化。本文中的車間布局優(yōu)化算法即采用遺傳算法，結合生產(chǎn)數(shù)據(jù)實例，利用MATLAB編寫代碼求解模型。

3.1 染色體編碼

染色體編碼是利用遺傳算法求解車間布局重構問題的關鍵，它不僅影響遺傳算子的設計，還決定了搜索空間基因向解空間轉換的對應關系[9]。本文中，按照設備的編碼如A、B、C、D、E、F等的順序進行編碼，將設備的位置坐標對應為二進制編碼，例如，設備A（2，6）對應的編碼為0010 0110。

3.2 染色體初始化和適應度函數(shù)值

在初始化工作中，首先進行染色體初始化，在MATLAB編碼中，人們設隨機生成的中心位置對應解空間。初始隨機生成各個設備位置點的x、y值，在給定的空間范圍內(nèi)，適應度函數(shù)（Fitness Function）值=成本值+邊緣設備圍成的最大面積值，描述如下：適應度函數(shù)值越低，則種群的適應度越高。初始化種群數(shù)為50。

3.3 選擇算子

遺傳算法中的基因，如果簡單地進行雜交，很可能破壞較好的基因組合，達不到累積較好基因的目的。而精英保留策略可以避免最優(yōu)個體因為雜交操作而被破壞[10]。在本文中，采用排序選擇算子產(chǎn)生下一代，對適應度高的種群進行選擇，適應度最佳的前10%直接進入下一代，并在其中隨機選擇20%進行交叉變異。采用精英保留策略以加快收斂速度。

3.4 交叉算子

交叉時采用多點雜交，設置交叉概率為0.8。根據(jù)算例的數(shù)據(jù)跨度，第一個點與第二個點之間的長度設為10以內(nèi)的數(shù)以增加算法的穩(wěn)定性與魯棒性。比如，第一個點為第17個數(shù)，第二個點為第24個數(shù)，將這兩點之間的片段進行交換，即兩個染色體第3個位置片段交換。這里的位置選擇也是隨機的。交叉過程為：隨機選擇兩條染色體，隨機選擇設備，隨機選擇交叉位置，如選擇設備C的第3個位置進行交叉。

同時，在MATLAB中進行測試，保證交叉后設備不重疊，若交叉后有位置重疊則重新進行交叉過程，直至完成交叉過程。

3.5 變異算子

隨機選擇一條染色體的隨機一個位置進行變異，確保變異位置在編碼范圍內(nèi)。設置變異概率為0.3。

4 算例驗證

4.1 算例背景

以某工廠智慧車間生產(chǎn)情況為數(shù)據(jù)來源。該車間主要負責裝配件A各零件的加工與成品組裝。采用半自動流水線作業(yè)方式，車間長度12m，寬度10m。車間各設備的主要參數(shù)如表1所示。

表1 車間各設備的主要參數(shù)

所有設備在X軸、Y軸方向上需要保持1m的最小間距。各個設備之間的當量物流量如表2所示，單位為（個?次）。

表2 各設備間當量物流流轉量

由于當量物流量已經(jīng)根據(jù)零件A的不同配件搬運難度進行了量綱化處理，所以將所有設備之間的搬運費用設為1元/m。

4.2 目標優(yōu)化

選擇最小物流成本作為車間布局問題評價的依據(jù)，車間規(guī)整度作為可行與否的評價條件。遺傳算法的基本參數(shù)設置包括：種群大小size=50、最大代數(shù)m=1000、變異概率p=0.3、交叉概率o=0.8。在這種變異率和交叉概率中，采用遺傳算法作為求解策略時，目標函數(shù)在100代成本顯著減小，在400代以后成本趨于平穩(wěn)，滿足收斂特性，如圖1所示。

4.3 優(yōu)化前后對比

在MATLAB中設置最大迭代次數(shù)為1000，圖2和圖3為優(yōu)化前和優(yōu)化后的布局結果。

圖1 1000代目標函數(shù)變化曲線

圖2 1000代優(yōu)化前車間設備布局

圖3 1000代優(yōu)化后車間設備布局

優(yōu)化后，設備E、F、A、B、C、D的坐標分別為（6，13）、（14，13）、（18，13）、（6，10）、（10，10）、（18，10），E、F、A擺放在同一行，B、C、D擺放在另一行。目標函數(shù)值即綜合成本降低90時，可以節(jié)約15.2%的物流成本，在車間規(guī)整程度節(jié)省50%的占地面積。構建的數(shù)學模型可以符合組裝式車間的布局要求，優(yōu)化結果可觀。

[1]朱碩，江志剛，張華，等.面向再制造工藝單元重構的設備布局模型研究[J].制造技術與機床，2013，（12）：32-35.

[2]Francis R L，While J A.Facility Layout and Location：an Analytical Approach[J].Prentice Hall，1974，27(2)：112.

[3]Meller R D，Narayanan V，Vance P H.Optimal Facility Layout Design[J].Operations Research Letters，1999，（23）：117-127.

[4]Kia R，Baboli A，Javadian N，et al.Solving a Group Layout Design Model of a Dynamic Cellular Manufacturing System with Alternative Process Routings，Lot splitting and Flexible Reconfiguration by Simulated Annealing[J].Computers & Operations Research，2012，39（11）：2642-2658.

[5]曹陽華，康秀翠.基于SLP思想的車間設備布置改善研究[J].現(xiàn)代制造工程，2015，（8）：75-80.

[6]朱永國，何自璋，孫士平，等.多品種小批量連桿類零件的柔性制造系統(tǒng)構建及其車間設備布局[J].機械制造，2014，52（11）：78-81.

[7]徐雙燕，丁祥海，陶俐言.多目標動態(tài)車間設施布局研究綜述[J].機械研究與應用，2012，（6）：40-45.

[8]V Madhusudanan Pillai，Kankata Subbarao.A robust Cellular Manufacturing System Design for Dynamic Part Population Using a Genetic Algorithm[J].International Journal of Production Research，2008，46（18）：5191-5210.

[9]王正林，龔純，何倩.精通MAT LAB科學計算[M].北京：電子工業(yè)出版社，2007：360-364.

[10]朱燦，梁昔明.一種多精英保存策略的遺傳算法[J].計算機應用，2008，28（4）：939-941.