丁穗庭 王智偉 王思揚(yáng)

（南京航空航天大學(xué)，南京 210000）

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

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

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

1 問題描述

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

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

2 布局模型

2.1 目標(biāo)函數(shù)

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

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

2.2 約束條件

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

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

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

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

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

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

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

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

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

xr（i）表示第 r行設(shè)備 i中心點的橫坐標(biāo)；lr（i）表示第r行設(shè)備i的長；d表示相鄰兩設(shè)備之間必須保持的最小間距，d≥0（常數(shù)）。此時將兩端墻壁視為設(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īng)的y坐標(biāo)。

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

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

2.2.4 設(shè)備不超出車間范圍

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

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

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

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

3 模型求解

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

3.1 染色體編碼

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

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

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

3.3 選擇算子

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

3.4 交叉算子

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

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

3.5 變異算子

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

4 算例驗證

4.1 算例背景

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

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

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

表2 各設(shè)備間當(dāng)量物流流轉(zhuǎn)量

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

4.2 目標(biāo)優(yōu)化

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

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

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

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

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

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

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

[1]朱碩，江志剛，張華，等.面向再制造工藝單元重構(gòu)的設(shè)備布局模型研究[J].制造技術(shù)與機(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思想的車間設(shè)備布置改善研究[J].現(xiàn)代制造工程，2015，（8）：75-80.

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

[7]徐雙燕，丁祥海，陶俐言.多目標(biāo)動態(tài)車間設(shè)施布局研究綜述[J].機(jī)械研究與應(yīng)用，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科學(xué)計算[M].北京：電子工業(yè)出版社，2007：360-364.

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