彭劼?lián)P，王家海，沈 斌

（1.同濟(jì)大學(xué) 機(jī)械學(xué)院，上海 201804；2.同濟(jì)大學(xué) 中德學(xué)院，上海 201804）

0 引言

航天產(chǎn)品加工過(guò)程復(fù)雜，大多數(shù)加工生產(chǎn)都是根據(jù)工藝人員的經(jīng)驗(yàn)進(jìn)行設(shè)施規(guī)劃和加工，生產(chǎn)效率低下。在提高生產(chǎn)效率的方面，設(shè)施布置設(shè)計(jì)被視為提高車(chē)間生產(chǎn)力的關(guān)鍵[1]。研究表明，20%～50%的操作費(fèi)用是用于原料運(yùn)輸費(fèi)用中。而工廠布局屬于NP問(wèn)題，使用數(shù)值計(jì)算方法很難高效地解決，目前大都使用啟發(fā)式算法[2]或使用計(jì)算機(jī)軟件仿真進(jìn)行求解。

對(duì)于布局問(wèn)題，國(guó)外最早于1961年由Richard Muther研究出系統(tǒng)布置設(shè)計(jì)SLP方法，首次提出對(duì)于相互作用的生產(chǎn)單元之間的關(guān)系表示法，對(duì)后續(xù)相關(guān)研究打下堅(jiān)實(shí)的基礎(chǔ)[3]。隨著科技的發(fā)展，SLP的缺點(diǎn)漸漸凸現(xiàn)出來(lái)，科研人員開(kāi)始使用啟發(fā)式算法和SLP相結(jié)合的方式，衍生出改進(jìn)法[4]。Ravi Kothari和Diptesh Ghosh[5]提出使用兩個(gè)禁忌算法對(duì)單行設(shè)施布局進(jìn)行實(shí)現(xiàn)的策略，其中一個(gè)禁忌算法是窮舉搜索的2-opt鄰域，而另一個(gè)涉及插入鄰域的窮盡搜索，能夠加快兩個(gè)鄰域的搜索。齊繼陽(yáng)和竺長(zhǎng)安[6]使用改進(jìn)型模擬退火算法，使用禁忌表的手段，增加了退火算法的記憶能力。龐峰[7]將改進(jìn)SA算法應(yīng)用到板式家具問(wèn)題上，使材料利用率普遍高于95%。

基于以上研究，本文主要對(duì)對(duì)設(shè)備布局算法進(jìn)行研究，提出了混合算法的一般設(shè)計(jì)原則。通過(guò)對(duì)比分析，發(fā)現(xiàn)將模擬退火思想應(yīng)用到遺傳算法中能提升算法的收斂性，減少迭代次數(shù)。并在此基礎(chǔ)上，應(yīng)用Plant Simulation仿真軟件對(duì)某航天大型零件車(chē)間布局進(jìn)行仿真，驗(yàn)證了混合算法的優(yōu)越性。

1 數(shù)學(xué)模型

本文是對(duì)塊狀工位進(jìn)行研究，對(duì)于塊狀的工位，需要考慮到一個(gè)設(shè)備所需的運(yùn)維面積及該工位所需的工位面積。給定長(zhǎng)×寬的時(shí)候，進(jìn)行布局，則每一行的寬度由該行中最大寬度設(shè)備塊決定。布置過(guò)程如圖1所示，其中單行布置可以看成多行布置的特殊形式。

圖1 設(shè)備布局

而相應(yīng)的數(shù)學(xué)模型可以表示如下：

其中：F是目標(biāo)函數(shù)值；Cij為物料運(yùn)輸費(fèi)用；fij為物料運(yùn)輸量；dij為兩個(gè)設(shè)備之間的距離；xixj為兩個(gè)設(shè)備之間x坐標(biāo)值；yiyj為兩個(gè)設(shè)備之間y坐標(biāo)值；lilj為設(shè)備i，j的長(zhǎng)度；wiwj為設(shè)備i，j的寬度；L，H分別為車(chē)間的總長(zhǎng)度和總寬度。

式(1)中，以物流量為優(yōu)化目標(biāo)，能夠很大程度上達(dá)到對(duì)車(chē)間的布局優(yōu)化；式(2)中，dij作為兩個(gè)設(shè)備之間的距離，設(shè)備之間通常不能直接接觸的，距離的大小是通過(guò)兩個(gè)設(shè)備塊中心之間的直線距離進(jìn)行衡量的；式(3)中主要是對(duì)同一行中兩臺(tái)設(shè)備在X軸方向進(jìn)行限定，保證兩臺(tái)設(shè)備不交；式(4)中則是不同行相鄰設(shè)備之間在Y方向上不能交叉；式(5)是對(duì)車(chē)間長(zhǎng)度方向的約束，不能超過(guò)車(chē)間規(guī)定的總長(zhǎng)；式(6)是在車(chē)間寬度方向進(jìn)行的限制，不能超差?；谝陨瞎降募s束可以保證建模的合理性。

2 混合算法的設(shè)計(jì)

算法間存在多種結(jié)合方式，但是并不是所有的結(jié)合方式都能使新算法優(yōu)于單個(gè)算法，因此對(duì)于兩個(gè)算法的結(jié)合應(yīng)遵循以下原則進(jìn)行：1）算法優(yōu)缺點(diǎn)結(jié)合原則：相結(jié)合的兩個(gè)算法能夠優(yōu)缺點(diǎn)互補(bǔ)，如此混合算法將優(yōu)于獨(dú)立算法?；蛘弑M量減少兩個(gè)算法缺點(diǎn)的相同部分，從而減小了對(duì)混合算法在該部分的進(jìn)一步弱化；2）解形式一致原則：在算法結(jié)合過(guò)程中，注意解的聯(lián)系，兩個(gè)算法的結(jié)合部分注意解的形式的變換，如：遺傳算法中采用的是編碼的方式進(jìn)行計(jì)算的，但是在粒子群算法中采用的是粒子的方式，在形式上有所區(qū)別。3）遵循適用原則：在處理具體問(wèn)題的時(shí)候，有些算法不適合解決該問(wèn)題的時(shí)候，就不能再使用該算法與其他算法進(jìn)行結(jié)合來(lái)解決問(wèn)題。

本文對(duì)于模擬退火遺傳算法進(jìn)行的結(jié)合能夠同時(shí)滿(mǎn)足以上原則，能夠進(jìn)行算法融合，混合算法流程如圖2所示。

圖2 混合算法流程

算法描述如下：

1）首先設(shè)置參數(shù)，種群數(shù)量，迭代次數(shù)，交叉率，變異率，初始溫度等；

2）采用退火原理對(duì)初代進(jìn)行處理；

3）使用遺傳算法進(jìn)行選擇、交叉、變異，方式如上文所述；

4）計(jì)算適應(yīng)度值，進(jìn)行比較，產(chǎn)生下一代種群；

5）產(chǎn)生子代后，若滿(mǎn)足收斂條件則輸出最優(yōu)解，否則繼續(xù)進(jìn)行迭代操作直到找出最優(yōu)解。

3 混合算法的實(shí)例驗(yàn)證

多行布局中在進(jìn)行坐標(biāo)求解時(shí)，按中心點(diǎn)的X坐標(biāo)和Y坐標(biāo)進(jìn)行表示每個(gè)設(shè)備的位置。本算例采用文獻(xiàn)[8]中某機(jī)械加工企業(yè)，車(chē)間內(nèi)設(shè)備的擺放方式是以機(jī)群為主。而且在其中生產(chǎn)的產(chǎn)品的質(zhì)量較大，因此車(chē)間物流量相對(duì)較大。該車(chē)間是一個(gè)長(zhǎng)為20m的正方形形狀車(chē)間，進(jìn)行產(chǎn)品加工的設(shè)備有10臺(tái)，物流成本如下所示：

設(shè)備長(zhǎng)度：{4.3，4.3，4.65，2，5，3.5，1.8，3.85，5，5}；

設(shè)備寬度：{5.6，3.7，7.75，4，4.2，5，2，4，4，4}。

單位成本矩陣如表1所示。

表1 費(fèi)用矩陣

車(chē)間的初始布局為{1，2，3；4，5，6；7，8，9，10}，此時(shí)車(chē)間運(yùn)輸成本為3748.8元。本文選取算法種群大小為10，子代數(shù)目為8的情況下，最大代數(shù)迭代到100，交叉率為0.8，變異率為0.2。

表為三種算法運(yùn)行結(jié)果對(duì)比如表2所示。

表2 算法結(jié)果對(duì)比

多行布局平均值收斂曲線如圖3所示，其中橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為物流運(yùn)輸當(dāng)量值，即是前文所述目標(biāo)函數(shù)值。

圖3 10次平均值迭代曲線

收斂曲線如圖4所示。

求解結(jié)果分析：

1）圖4中可知，10次混合算法平均解的收斂速度明顯高于遺傳算法和模擬退火算法。混合算法的10次解中只有第四次和第五次的解比遺傳算法稍差，其他的解均優(yōu)于遺傳算法，而混合算法十次解中均優(yōu)于模擬退火算法的解。

2）根據(jù)圖3中對(duì)比可以看出，混合算法的結(jié)果明顯優(yōu)于其他另外兩種方式，混合算法在30代左右收斂到最好結(jié)果，而其他兩個(gè)算法在40代以后得到最終結(jié)果，且最優(yōu)解相比混合算法較差，因此，混合算法的收斂特性和最優(yōu)解均優(yōu)于單獨(dú)算法。

圖4 最優(yōu)解收斂曲線

4 基于Plant Simulation的布局算法仿真

航天薄壁結(jié)構(gòu)件生產(chǎn)車(chē)間的情況較為復(fù)雜，涉及多品種小批量的混流生產(chǎn)，本文驗(yàn)證的車(chē)間生產(chǎn)兩種型號(hào)的火箭儲(chǔ)箱，其中產(chǎn)品A是由6個(gè)筒段和2個(gè)箱底組成，而產(chǎn)品B是由6個(gè)筒段和2個(gè)箱底組成，年產(chǎn)量為12個(gè)貯箱。

使用Plantsimulation仿真軟件進(jìn)行二維仿真，由混合算法得出的結(jié)果得出布局方案，如圖5所示，優(yōu)化后的布局為（1，2，3；5，16，4，9，13，7，15，12；14，10，8，11，6），在Plant Simulation構(gòu)建二維及三維仿真模型如圖5所示：

圖5 車(chē)間二維、三維布局圖

圖6 仿真運(yùn)行結(jié)果

由仿真結(jié)果可知，生產(chǎn)相同產(chǎn)品的情況下，經(jīng)過(guò)布局優(yōu)化后的車(chē)間加工時(shí)間大大縮短，圖5所示經(jīng)過(guò)改進(jìn)后的仿真運(yùn)行結(jié)果：

由圖6可知，在生產(chǎn)同樣零件個(gè)數(shù)的情況下，加工時(shí)間由365天縮短到204天左右，生產(chǎn)效率極大的提高了。

5 結(jié)束語(yǔ)

本文主要對(duì)現(xiàn)有航天產(chǎn)品車(chē)間進(jìn)行改造，通過(guò)對(duì)布局算法的研究，分析遺傳算法和模擬退火算法從而設(shè)計(jì)出混合算法，并進(jìn)行了算法驗(yàn)證，得出了算法的有效性。通過(guò)混合算法對(duì)車(chē)間布局進(jìn)行求解，獲得了車(chē)間布局優(yōu)化方案。仿真結(jié)果表明：該混合算法具有很好的收斂特性，同時(shí)能夠得出較為理想的結(jié)果。