基于遺傳元胞機的多態(tài)性作業(yè)車間布局建模

，，，

(浙江工業(yè)大學 機械工程學院，浙江 杭州 310014)

隨著市場競爭的日益激烈，一類復雜產(chǎn)品大規(guī)模定制企業(yè)和產(chǎn)業(yè)集群下大型代工企業(yè)，其生產(chǎn)過程在訂單、設(shè)備、工藝、批量和瓶頸等層次上越來越凸顯形態(tài)和狀態(tài)的多樣性，對布局的柔性、魯棒性和動態(tài)性需求逐步增強.在當前日益緊張的土地資源背景下，為尋求最佳設(shè)備配比、最低物流耗費、最大空間利用和良好的生產(chǎn)柔性，如何有效進行此類多態(tài)性作業(yè)車間的布局設(shè)計和優(yōu)化，是未來研究的重點和熱點.

現(xiàn)有研究表明：單一優(yōu)化算法已無法滿足多態(tài)性作業(yè)車間這一類復雜性、階梯型車間布局的需求，兩種或兩種以上算法融合成為當前研究的新趨勢.曾議等[1]提出基于遺傳算法雜交策略的連續(xù)粒子群優(yōu)化算法，提高了搜索效率和質(zhì)量，提供了求解設(shè)備單向環(huán)形布置的車間布局問題的新思路；張屹等[2]在多目標遺傳算法的基礎(chǔ)上引入差分演化策略，集成了算法多樣性和差分演化策略在解決復雜問題時收斂性強、覆蓋范圍廣的特點，有效解決了多目標優(yōu)化的生產(chǎn)車間設(shè)備布局問題；余世根等[3]建立了多目標、具有固定約束多態(tài)性車間的布局問題優(yōu)化流程，證明遺傳算法在求解具有固定約束車間多目標設(shè)備布局問題的有效性.Lee K Y等[4]提出一種改進遺傳算法解決了具有內(nèi)部結(jié)構(gòu)墻和通道的多層設(shè)備車間布局問題；YKASO A等[5]提出了一種模擬動態(tài)布局問題的元胞自動機算法，算法引入尺度敏感性分析，增強了作業(yè)布局的自適應(yīng)性.元胞機是一個時間和空間都離散的動力系統(tǒng)，具有強大的空間運算能力，已應(yīng)用于材料、交通運輸、車間調(diào)度等研究領(lǐng)域[6-9]，筆者采用元胞機時空高離散的方法框架模型，利用遺傳算法優(yōu)化元胞機演化規(guī)則，建立多態(tài)性作業(yè)車間布局遺傳元胞機模型以獲得更優(yōu)的布局方案.

1 多態(tài)性作業(yè)車間元胞機框架模型

多態(tài)性作業(yè)車間的布局設(shè)計是指在多品種、多工藝、變批量，對布局多態(tài)性和魯棒性要求高的生產(chǎn)作業(yè)車間內(nèi)將加工設(shè)備、物料運輸設(shè)備和通道等各種制造資源合理地放置在一個具有約束的二維空間當中，并且能夠最大化的降低物料搬運費用、提高車間面積利用率和設(shè)備平均利用率.多態(tài)性作業(yè)車間不僅要滿足產(chǎn)品的產(chǎn)量、產(chǎn)品的加工工藝、加工流程、各制造資源加工能力等要求，還要滿足二維空間的幾何約束條件，包括車間布局各方向長度不超出給定車間各方向長度、各制造資源間距必須滿足最小緩沖要求等.元胞機模型是對客觀世界抽象的結(jié)果，按照一定的局部演化規(guī)則進化，結(jié)合元胞機自身的結(jié)果特點，構(gòu)建多態(tài)性作業(yè)車間布局元胞機模型，其表達式為

A={L2，Sf，N，R，F(xiàn)}

(1)

式中：A為多態(tài)性作業(yè)車間布局元胞機模型；L2為二維網(wǎng)格空間結(jié)構(gòu)；Sf為中心設(shè)備元胞的狀態(tài)；N為領(lǐng)域元胞的狀態(tài)；R為布局約束條件；F為布局演化規(guī)則.

1.1 二維網(wǎng)格空間結(jié)構(gòu)

如圖1所示，多態(tài)性作業(yè)車間布局的元胞機模型由設(shè)備元胞、緩沖元胞及通道元胞組成.圖1中的空間網(wǎng)格的大小是根據(jù)實際所要進行布局的車間大小按一定比例縮小后進行劃分，對車間當中的設(shè)備、設(shè)備之間的緩沖空間以及通道進行標準化，均為單位網(wǎng)格的整數(shù)倍.

圖1 多態(tài)性作業(yè)車間布局元胞機模型圖

其中設(shè)備元胞在多態(tài)性作業(yè)車間布局元胞機模型當中需要占據(jù)多個網(wǎng)格，由中心設(shè)備元胞、輔助設(shè)備元胞組成，設(shè)備元胞的模型如圖2所示.中心設(shè)備元胞控制周圍的輔助設(shè)備元胞，從而確定設(shè)備元胞在空間網(wǎng)格當中的位置.

圖2 設(shè)備元胞模型圖

(2)

(3)

(4)

對于任意一行i上(j+z)列有

(5)

因此可得

(6)

式中Bz為其他元胞不同時刻狀態(tài)值向量的綜合.

中心設(shè)備元胞t時刻的狀態(tài)屬性表示為

(7)

式中：fn為設(shè)備的名稱，靜態(tài)屬性；fs為設(shè)備擺放狀態(tài)，動態(tài)屬性，fs∈{0，1}，0表示橫向擺放，1表示縱向擺放；vq為該中心設(shè)備元胞所在設(shè)備元胞的占用的縱軸網(wǎng)格數(shù)，動態(tài)屬性，vq∈{vq，hq}；hq為該中心設(shè)備元胞所在設(shè)備元胞的占用的橫軸網(wǎng)格數(shù)，動態(tài)屬性，hq∈{vq，hq}；fo為設(shè)備元胞所需占用的網(wǎng)格數(shù)，靜態(tài)屬性，fo=vqhq；fl為中心設(shè)備元胞當前所在空間網(wǎng)格當中的所在位置(i，j)，動態(tài)屬性；fc為設(shè)備的加工能力，靜態(tài)屬性；fr為設(shè)備的安裝要求，靜態(tài)屬性，fr∈{0，1}，0表示設(shè)備可移動，1表示設(shè)備不可移動；fb為設(shè)備所需緩沖空間，靜態(tài)屬性.

緩沖元胞t時刻的狀態(tài)屬性表示為

(8)

式中：bs為緩沖元胞當前所在空間網(wǎng)格當中的所在位置(i，j)，動態(tài)屬性；bf為緩沖元胞鄰近網(wǎng)格(i+1，j)的元胞類別，動態(tài)屬性；bb為緩沖元胞鄰近網(wǎng)格(i-1，j)的元胞類別，動態(tài)屬性；bl為緩沖元胞鄰近網(wǎng)格(i，j+1)的元胞類別，動態(tài)屬性；br為緩沖元胞鄰近網(wǎng)格(i，j-1)的元胞類別，動態(tài)屬性；bf，bb，bl，br∈{0，1，2}，0為設(shè)備元胞，1為緩沖元胞，2為通道元胞.

通道元胞t時刻的狀態(tài)屬性表示為

(9)

式中：ps為通道元胞當前所在空間網(wǎng)格當中的所在位置(i，j)，動態(tài)屬性；pf為通道元胞鄰近網(wǎng)格(i+1，j)的元胞類別，動態(tài)屬性；pb為通道元胞鄰近網(wǎng)格(i-1，j)的元胞類別，動態(tài)屬性；pl為通道元胞鄰近網(wǎng)格(i，j+1)的元胞類別，動態(tài)屬性；pr為通道元胞鄰近網(wǎng)格(i，j-1)的元胞類別，動態(tài)屬性；pf，pb，pl，pr∈{0，1，1}，0為設(shè)備元胞，1為緩沖元胞，2為通道元胞.

1.2 模型演化規(guī)則

演化規(guī)則是模型的關(guān)鍵部分，多態(tài)性作業(yè)車間布局元胞機演化規(guī)則有三條，即移位觸發(fā)規(guī)則、緩沖控制規(guī)則和通道選擇規(guī)則，具體如表1所示.

表1 多態(tài)性作業(yè)車間布局元胞機模型局部演化規(guī)則表

模型的演化規(guī)則當中的移位觸發(fā)規(guī)則主要依據(jù)車間生產(chǎn)產(chǎn)品的工藝順序和物流路線；緩沖控制規(guī)則主要是根據(jù)設(shè)備間的最小間隔；通道選擇是根據(jù)物流路線.

2 基于遺傳算法的元胞機演化規(guī)則優(yōu)化

在模型中，利用遺傳算法優(yōu)化局部演化規(guī)則嵌套于元胞機模型，通過算法的反復迭代，直到滿足終止條件，得到最優(yōu)布局方案，下面利用遺傳算法對局部演化規(guī)則進行優(yōu)化.

2.1 染色體編碼與解碼

根據(jù)設(shè)備在網(wǎng)格內(nèi)的位置和設(shè)備所需的緩沖空間，將布局編碼分為位置選擇染色體和緩沖染色體兩個部分.根據(jù)兩行設(shè)備布局編碼方案，結(jié)合設(shè)備元胞在多態(tài)性作業(yè)車間中二維布置的特點，采用如下染色體編碼方式：

(10)

解碼就是編碼的一個逆向過程，先根據(jù)位置染色體確定設(shè)備的網(wǎng)格位置，再根據(jù)緩沖染色體判斷設(shè)備間的緩沖間距大小.根據(jù)每類產(chǎn)品的工藝順序調(diào)整、推進布局方案的更新.

2.2 初始種群的獲取

目前在研究車間布局問題的諸多算法中，廣泛采用隨機產(chǎn)生初始解的方式，但是這樣無法保證所產(chǎn)生初始解的合理性和尋優(yōu)過程的高效性，并且容易使尋優(yōu)過程進入局部最優(yōu)化，從而導致無法產(chǎn)生最優(yōu)解.因此本文先通過使用SLP法(System layout planning，系統(tǒng)布置設(shè)計)進行分析計算，得到初步的布局方案，再對布局方案進行網(wǎng)格化和標準化，作為多態(tài)性作業(yè)車間布局的初始解，如圖3所示.

圖3 SLP法布局方案元胞模型化

2.3 適應(yīng)度函數(shù)

鑒于適應(yīng)度函數(shù)單值、連續(xù)及最小化等要求，將多態(tài)性作業(yè)車間布局多目標函數(shù)設(shè)為適應(yīng)度函數(shù)如下：

F=min[ω1C+ω2(1-Ua)+ω3(1-Uf)]

(11)

式中：ω1，ω2，ω3分別為各個子目標的權(quán)重值；C為物料搬運費用；Ua為車間面積利用率；Uf為設(shè)備平均利用率.在不同作業(yè)車間的布局設(shè)計當中可根據(jù)決策者對各個子目標的重視程度不同，從而設(shè)定各個子目標的權(quán)重值(ω1+ω2+ω3=1)，即采用優(yōu)先權(quán)值設(shè)定法，事先對各個子目標的權(quán)重值進行設(shè)定，將多目標優(yōu)化問題轉(zhuǎn)化為單目標優(yōu)化問題.

2.4 選 擇

選擇方法采用輪盤賭選擇法，在該方法中每個染色體個體都有機會被選中，而選擇概率取決于群體中個體的適應(yīng)度：

(12)

式中：i為種群中某一個染色體的編號；N為種群中所有染色體的數(shù)量，1≤i≤N；Pi為該染色體的選擇概率.在這個過程，首先通過初始布局方案解的進化得到新的解集，比較各布局方案解的適應(yīng)度函數(shù)值，適應(yīng)度低的布局方案將被淘汰，適應(yīng)度較高的布局方案得以進化尋求更優(yōu)的布局結(jié)果.

2.5 交 叉

適應(yīng)度較高的布局方案得以交叉進化，在交叉時根據(jù)染色體的不同采用不同的方法.位置選擇染色體的交叉采用部分匹配交叉(PMX)的方法，先隨機選取兩個交叉點，然后交換兩個父代個體中交

叉點的中間段，最后根據(jù)基因之間的映射關(guān)系來生成子代染色體，具體操作如圖4中的案例所示；緩沖染色體直接采用兩點交叉，隨機的選擇兩個交叉點，然后交換他們之間的基因.

圖4 位置選擇染色體PMX交叉示意圖

2.6 變 異

布局方案解除了進行交叉進化還可以利用變異獲得更優(yōu)的布局方案解，變異是種群按照變異概率Pm任選若干基因位改變其位置，它決定了遺傳算法的局部搜索能力.變異分為兩種：1)位置選擇染色體采用交換變異方法，即隨機選擇兩個變異位，然后交換兩個位的基因；2)緩沖染色體采用實數(shù)變異方法.首先在[0，5]區(qū)間內(nèi)建立一個2×n(n為設(shè)備數(shù))階矩陣作為初始化矩陣，上下兩行對應(yīng)位相減得到一個新的1×n階矩陣，將該矩陣的每個位基因乘以一個1到變異長度的隨機值，與Δ中相應(yīng)的變異位相加并絕對值，產(chǎn)生一個新的實數(shù)來取代原來位的基因，具體操作如圖5中的案例所示.

圖5 緩沖染色體變異示意圖

3 多目標函數(shù)

多態(tài)性車間布局當中由于產(chǎn)品的多樣性和更新?lián)Q代，導致產(chǎn)品工藝的不同，影響了布局設(shè)備的利用率.因此，在多態(tài)性車間布局的目標不僅是使物流費用最低，并且考慮到車間布局的美觀性、投資成本以及布局設(shè)備的利用率，目標函數(shù)將車間面積利用率和車間設(shè)備平均利用率也考慮進去.

前述三個目標的目標函數(shù)如下：

1) 物料搬運費用最小，即

(13)

2) 車間面積利用率最大，即

(14)

式中：Ua為車間面積利用率；St為車間實際占地面積；Se為布局方案最終確定的布局結(jié)果總面積.

3) 設(shè)備平均利用率最大，即

(15)

通過權(quán)重加和法得到車間布局的多目標函數(shù)：

F=min[ω1C+ω2(1-Ua)+ω3(1-Uf)]

(16)

式中：ω1，ω2，ω3分別為各個子目標的權(quán)重值.

在多態(tài)性作業(yè)車間布局元胞機模型當中，通過設(shè)備元胞、緩沖元胞和通道元胞的調(diào)整和局部演變從而獲得最優(yōu)的布局方案.在模型當中，這三類元胞必須在布局網(wǎng)格以內(nèi)，同時設(shè)備元胞之間滿足最小緩沖空間要求，因此提出如下兩條約束條件：

1) 邊界約束

(17)

(18)

2) 緩沖約束

(19)

4 實例驗證

表2 產(chǎn)品的工藝流程

表3 設(shè)備的外形尺寸和數(shù)量

表4 設(shè)備間物流量

圖6 車間布局初始解

使用遺傳元胞機算法進行車間布局優(yōu)化，首先對布局初始解進行網(wǎng)格化和標準化，單位網(wǎng)格0.5 m×0.5 m，各設(shè)備單元化后的尺寸如表3所示.然后進行相關(guān)參數(shù)設(shè)定，遺傳算法優(yōu)化部分取迭代次數(shù)N=100，交叉概率Pc=0.7，變異概率Pm=0.001，將布局總目標作為適應(yīng)度函數(shù)，設(shè)定權(quán)重ω1=0.4，ω2=0.3，ω3=0.3.獲得適應(yīng)度值最大解作為最終的布局方案如圖7所示.對應(yīng)三個子目標和一個總目標值如表5所示.

圖7 車間布局最優(yōu)解

表5 目標函數(shù)值

從表5中的各函數(shù)值可以看出：最終布局方案較初始方案能夠有效的降低物料搬運費用，提高車間面積利用率和平均設(shè)備利用率，獲得更優(yōu)的布局總目標，因此所提出的遺傳元胞機模型在解決多態(tài)性作業(yè)車間布局問題方面可行、有效.

5 結(jié) 論

作業(yè)車間布局是車間設(shè)計規(guī)劃中的重要一環(huán)，其結(jié)果直接影響生產(chǎn)系統(tǒng)的經(jīng)濟性、安全性和整體效率.將元胞機與遺傳算法相結(jié)合用于求解多態(tài)性作業(yè)車間布局優(yōu)化問題，通過布局實例的初始解和最優(yōu)解相比較，驗證了元胞機和遺傳算法相結(jié)合的算法在求解多態(tài)性作業(yè)車間布局問題具有可行性和有效性，能夠提高布局性能，為解決多態(tài)性作業(yè)車間布局問題提供了一種新方法.但目前關(guān)于多態(tài)性作業(yè)車間布局問題的研究還不完整，在考慮布局因素時只提及了物料搬運費用、車間面積利用率和設(shè)備利用率，在今后的研究中，希望將更多的不確定因素加入模型進行探討.

參考文獻：

[1] 曾議，竺長安，沈連嬉，等．基于群智能算法的設(shè)備布局離散優(yōu)化研究[J].計算機集成制造系統(tǒng)，2007,13(3):542-549.

[2] 張屹，盧超，張虎，等.基于差分元胞多目標遺傳算法的車間布局優(yōu)化[J].計算機集成制造系統(tǒng)，2013,19(2):727-734.

[3] 余世根，魯建廈.基于GA的固定約束條件下多目標車間設(shè)備布局問題研究[J].浙江工業(yè)大學學報，2010,38(4):401-405.

[4] LEE K Y， ROH M I， JEONG H S. An improved genetic algorithm for multi-floor facility layout problems having inner structure walls and passages[J]. Computers and Operations Research，2005,150(32):879-899.

[5] YKASO A， NABIL N， GIND Y. A simulated cellular automata algorithm for the dynamic layout problem [J]. Computers and Operations Research，2010,155(28):1403-1426.

[6] 陳勇，阮興聰，魯建廈，等.基于元胞機和改進GA的大型零件柔性作業(yè)車間調(diào)度算法[J].中國機械工程，2012,23(21):177-184,190.

[7] 陳勇，阮興聰，王亞良.基于元胞機的大型機械構(gòu)件生產(chǎn)車間柔性調(diào)度求解[J].浙江工業(yè)大學學報，2011,39(4):433-439.

[8] 陳勇，潘益菁，王亞良，等.多態(tài)性作業(yè)車間魯棒調(diào)度CA-GA建模[J].浙江工業(yè)大學學報，2014,42(2)：124-131.

[9] 陳向東，金先龍，張曉云，等.基于元胞自動機的路面車流荷載[J].上海交通大學學報，2008,42(6)：870-873.