趙媛 ，付杰

（1.中國人民解放軍原68070部隊(duì)自動化站，蘭州 730000；2.蘭州理工大學(xué)，蘭州 730000）

1 引言

緩沖區(qū)被臨時設(shè)計用來存儲半成品和成品，以減少隨機(jī)事件或影響和破壞其他設(shè)備乃至整個系統(tǒng)的性能。緩沖區(qū)容量分配問題一直是制造系統(tǒng)設(shè)計者們面臨的一個重要的優(yōu)化問題。

緩沖區(qū)最優(yōu)分配問題是一個np-hard問題。對緩沖區(qū)分配問題的研究已經(jīng)有幾十年的歷史，已有的方法可以歸結(jié)為傳統(tǒng)的數(shù)學(xué)規(guī)劃法和啟發(fā)式算法兩種。許多學(xué)者對此做出了巨大貢獻(xiàn)，例如：Koenigsberg(1959)[1]，Buzacott and Hanifin(1978)[2]，Dallery and Gershwin(1992)[3],Gershwin(1994)[4],Aksoy and Gupta[5]。

傳統(tǒng)的數(shù)學(xué)規(guī)劃法依賴于精確的數(shù)學(xué)模型，但精確的數(shù)學(xué)模型較復(fù)雜，難以適應(yīng)實(shí)時控制的要求，而較簡單的數(shù)學(xué)模型誤差又大。為了更好地解決緩沖區(qū)最優(yōu)分配問題，研究人員逐漸把啟發(fā)式算法應(yīng)用于解決緩沖區(qū)最優(yōu)分配問題。

Can和Heavey[6]提出了用遺傳算法來解決連續(xù)生產(chǎn)線的緩沖區(qū)分配問題以使得生產(chǎn)線的效率最大化。研究提出了一種通過實(shí)驗(yàn)設(shè)計經(jīng)驗(yàn)的分析方法，這個方法使用遺傳算法解決基于模擬的直線型生產(chǎn)線的緩沖區(qū)問題，但該方法容易陷入局部最優(yōu)解且比較耗時。Spinellis和Papadopoulos[7]提出了用模擬退火算法來實(shí)現(xiàn)生產(chǎn)線效率的最大化。

本文通過利用模擬退火算法對遺傳算法進(jìn)行改進(jìn)，先通過一定的策略生成種群，然后用遺傳算法進(jìn)行求解，在遺傳算法結(jié)束后再利用模擬退火算法進(jìn)行一次局部搜索，嘗試在當(dāng)前求得的最優(yōu)解的前提下獲取更優(yōu)解。

2 模型描述

圖1 非相似生產(chǎn)線模型

圖1所示為一由K臺設(shè)備，K-1個緩沖(B1，B2,…,BK-1)組成的相似型生產(chǎn)線模型。原材料從外部到設(shè)備M1，再進(jìn)入緩沖B1，進(jìn)而到設(shè)備M2，直到設(shè)備MK,最終退出生產(chǎn)線系統(tǒng)。Ci為生產(chǎn)線中各個緩沖區(qū)最大緩沖區(qū)容量，pi與ri分別為設(shè)備故障率和維修率，且服從指數(shù)分布，則其平均故障時間為1/pi，Ti為設(shè)備加工時間。

本文研究的緩沖區(qū)分配問題數(shù)學(xué)模型如下所示：

3 緩沖區(qū)分配問題的研究

緩沖區(qū)容量分配技術(shù)主要由評價方法和生成方法兩部分組成。評價方法是對生產(chǎn)線成產(chǎn)效率進(jìn)行預(yù)測，生成方法是來尋找最優(yōu)的緩沖區(qū)容量分配方案。

3.1 評價方法

評價方法主要分為精確法和近似法兩類。由于精確法只是用于較為簡單的生產(chǎn)線模型，故本文采用近似法中的分解方法來評價成產(chǎn)線的生產(chǎn)效率。

3.2 遺傳模擬退火算法

遺傳模擬退火算法可視為在遺傳算法中引入了模擬退火算法的思想，有效地緩解了遺傳算法的選擇壓力，避免了早熟，增強(qiáng)了遺傳算法的全局收斂能力。遺傳模擬退火算法以遺傳算法控制尋優(yōu)方向，用模擬退火算法解決局部收斂性的問題，具有較高的效率和廣泛的適用性。

3.3 遺傳模擬退火算法參數(shù)流程

3.3.1 遺傳算法部分[7]

第1步初始化種群。

第2步選擇。

采用輪盤賭選擇法。輪盤賭選擇法是從染色體群體中選擇一些個體的方法，被選中的機(jī)率和它們的適應(yīng)度成比例，染色體的適應(yīng)度數(shù)愈高，被選中的概率也愈大。

第3步個體評價。

根據(jù)分解方法得出適應(yīng)度函數(shù)為[8]：

第4步基因操作。

變異操作需要每個個體的基因位置，并根據(jù)突變概率計算其值以產(chǎn)生新個體。

3.3.2 模擬退火算法部分

用模擬退火算法模擬熱力學(xué)系統(tǒng)[9]中的退火過程。在退火過程中，目標(biāo)函數(shù)被用作能量函數(shù)。主要參數(shù)設(shè)置包括：

①初始溫度；

②領(lǐng)域函數(shù)；

③接受概率。

具體操作步驟為：

步驟1初始化。選擇初始解x＝parent，最優(yōu)值為極小值。初始溫度為T。

步驟2通過隨機(jī)擾動產(chǎn)生新的解決方案如下：

①在當(dāng)前解向量中，隨機(jī)選擇兩個位置POS來計算剩余空間的總MM。

②對于第一選擇位置POS（1），在剩余松弛區(qū)域的空間范圍內(nèi)隨機(jī)地產(chǎn)生占據(jù)的松弛空間的大小，并且更新所占用的松弛區(qū)域的大小。

③對于所選擇的第二位置POS（2），由給定空間占用的空間不大于松弛區(qū)域的總和的上界。

④計算更新解XTEMP的函數(shù)值A(chǔ)TEMP，計算值與當(dāng)前最優(yōu)函數(shù)值DF＝AtEMP-MIAES之間的差值。

步驟3更新當(dāng)前解決方案：

①如果DF＜0，則以1的概率更新當(dāng)前最優(yōu)解。

②如果DF大于0，則用概率EXP（-）更新當(dāng)前最優(yōu)解。窗體頂端

步驟4若T>0,更新溫度T=T-0.1，返回步驟2。否則停止計算，輸出當(dāng)前最優(yōu)解。

4 數(shù)值仿真

仿真環(huán)境：雙核心英特爾第二代核心處理器（OpTIPLEX 3010型號戴爾計算機(jī)）、Win 7最終 32位系統(tǒng)和 Matlab 2010A軟件的主頻率為3.30GHZI3 2120。

它分別對五條裝備生產(chǎn)線和十條裝備生產(chǎn)線進(jìn)行了試驗(yàn)?zāi)M。在實(shí)驗(yàn)中，給出了平均工作時間（MTTF）和平均修復(fù)時間（MTTR），假設(shè)每個器件失效后的連續(xù)工作時間和修復(fù)時間滿足指數(shù)分布。

在五設(shè)備小型生產(chǎn)線中，緩沖區(qū)總量B=31，其余參數(shù)見表1。將混合算法與Diomidis提出的模擬退火算法、傳統(tǒng)遺傳算法進(jìn)行比較，通過比較生產(chǎn)率的大小來說明算法的優(yōu)劣性。

表1 設(shè)備參數(shù)

表2生產(chǎn)效率

可以看出，對于直線型生產(chǎn)線緩沖區(qū)優(yōu)化問題，遺傳模擬算法下的生產(chǎn)效率最高，其次是遺傳算法，模擬退火算法較差。兩種算法較好的原因在于它們均為采用了遺傳算法的種群生成，每個種群中基因數(shù)較多，因此可以在產(chǎn)生新種群的同時產(chǎn)生大量信息。

模擬退火算法的本質(zhì)是串行算法。當(dāng)生成新的解決方案時，只能使用一個解決方案信息。仿真結(jié)果表明，遺傳算法被困在局部最優(yōu)解中，通過引入模擬退火算法來跳出局部最優(yōu)解，找到最優(yōu)解。遺傳模擬退火算法采用模擬退火代替遺傳算法中的變異操作，從而增加了算法的搜索空間，提高了遺傳算法中變異操作的能力差，產(chǎn)生新的解，從而使遺傳算法更具魯棒性。E性能大大提高。

5 結(jié)論

在建立線性生產(chǎn)線模型的基礎(chǔ)上，將模擬退火算法引入遺傳算法，設(shè)計了遺傳模擬退火算法。在保留遺傳算法的全域搜索能力的基礎(chǔ)上，提高了局部搜索能力，得到了近似最優(yōu)值。原因是交叉操作是產(chǎn)生新的解決方案的主要步驟，并且突變操作由于突變率的大小常常被忽略，導(dǎo)致搜索范圍小。為了解決這一問題，引入了模擬退火算法的攝動運(yùn)算，因?yàn)樵撨^程所產(chǎn)生的解較大，將以一定的概率接受，從而提高了遺傳算法的搜索能力。采用遺傳模擬退火算法對線性生產(chǎn)線的緩沖容量進(jìn)行分配。與傳統(tǒng)的遺傳算法和模擬退火算法相比，其產(chǎn)率有了很大的提高。