，，，

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

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

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

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

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

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

(1)

式中：A為多態(tài)性作業(yè)車間布局元胞機(jī)模型；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è)車間布局的元胞機(jī)模型由設(shè)備元胞、緩沖元胞及通道元胞組成.圖1中的空間網(wǎng)格的大小是根據(jù)實(shí)際所要進(jìn)行布局的車間大小按一定比例縮小后進(jìn)行劃分，對(duì)車間當(dāng)中的設(shè)備、設(shè)備之間的緩沖空間以及通道進(jìn)行標(biāo)準(zhǔn)化，均為單位網(wǎng)格的整數(shù)倍.

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

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

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

(2)

(3)

(4)

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

(5)

因此可得

(6)

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

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

(7)

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

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

(8)

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

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

(9)

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

1.2 模型演化規(guī)則

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

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

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

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

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

2.1 染色體編碼與解碼

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

(10)

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

2.2 初始種群的獲取

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

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

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

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

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

(11)

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

2.4 選 擇

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

(12)

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

2.5 交 叉

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

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

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

2.6 變 異

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

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

3 多目標(biāo)函數(shù)

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

前述三個(gè)目標(biāo)的目標(biāo)函數(shù)如下：

1) 物料搬運(yùn)費(fèi)用最小，即

(13)

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

(14)

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

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

(15)

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

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

(16)

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

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

1) 邊界約束

(17)

(18)

2) 緩沖約束

(19)

4 實(shí)例驗(yàn)證

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

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

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

圖6 車間布局初始解

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

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

表5 目標(biāo)函數(shù)值

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

5 結(jié) 論

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

參考文獻(xiàn)：

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

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

[3] 余世根，魯建廈.基于GA的固定約束條件下多目標(biāo)車間設(shè)備布局問(wèn)題研究[J].浙江工業(yè)大學(xué)學(xué)報(bào)，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] 陳勇，阮興聰，魯建廈，等.基于元胞機(jī)和改進(jìn)GA的大型零件柔性作業(yè)車間調(diào)度算法[J].中國(guó)機(jī)械工程，2012,23(21):177-184,190.

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

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

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