一種混雜制造系統(tǒng)緩沖區(qū)容量分配技術(shù)的研究

趙媛 付杰

【摘 要】在緩沖區(qū)總?cè)萘看_定的約束條件下，以生產(chǎn)線效率最大化為目標(biāo)進(jìn)行研究，針對(duì)線性混合管道的緩沖容量分配問(wèn)題，提出了一種遺傳模擬退火算法。該算法主要以遺傳算法為核心，引入模擬退火算法，具有較好的局部搜索能力和全域搜索能力。最后，證明了算法的收斂性。仿真實(shí)驗(yàn)結(jié)果表明，遺傳模擬退火算法在分配線性混合制造系統(tǒng)緩沖能力時(shí)比傳統(tǒng)算法更為有效。

【Abstract】Under the constraint of the total capacity of the buffer， the goal of maximizing the efficiency of the production line is studied. Aiming at the problem of buffer capacity allocation in linear mixed pipelines， a genetic simulated annealing algorithm is proposed. The algorithm mainly adopts genetic algorithm as the core and introduces simulated annealing algorithm， which has better local search ability and global search ability. Finally， the convergence of the algorithm is proved. The simulation results show that the genetic simulated annealing algorithm is more effective than the traditional algorithm in allocating the buffer capacity of the linear hybrid manufacturing system.

【關(guān)鍵詞】直線型； 遺傳模擬退火算法； 早熟

【Keywords】linear pattern； genetic simulated annealing algorithm； precocious

【中圖分類號(hào)】TB497 【文獻(xiàn)標(biāo)志碼】A 【文章編號(hào)】1673-1069（2018）08-0154-03

1 引言

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

緩沖區(qū)最優(yōu)分配問(wèn)題是一個(gè)np-hard問(wèn)題。對(duì)緩沖區(qū)分配問(wèn)題的研究已經(jīng)有幾十年的歷史，已有的方法可以歸結(jié)為傳統(tǒng)的數(shù)學(xué)規(guī)劃法和啟發(fā)式算法兩種。許多學(xué)者對(duì)此做出了巨大貢獻(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í)控制的要求，而較簡(jiǎn)單的數(shù)學(xué)模型誤差又大。為了更好地解決緩沖區(qū)最優(yōu)分配問(wèn)題，研究人員逐漸把啟發(fā)式算法應(yīng)用于解決緩沖區(qū)最優(yōu)分配問(wèn)題。

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

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

2 模型描述

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

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

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

3.1 評(píng)價(jià)方法

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

3.2 遺傳模擬退火算法

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

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

3.3.1 遺傳算法部分[7]

第1步 初始化種群。

第2步 選擇。

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

第3步 個(gè)體評(píng)價(jià)。

第4步 基因操作。

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

3.3.2 模擬退火算法部分

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

①初始溫度；

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

③接受概率。

具體操作步驟為：

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

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

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

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

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

④計(jì)算更新解XTEMP的函數(shù)值A(chǔ)TEMP，計(jì)算值與當(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。否則停止計(jì)算，輸出當(dāng)前最優(yōu)解。

4 數(shù)值仿真

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

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

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

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

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

5 結(jié)論

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

【參考文獻(xiàn)】

【1】Koenigsberg， E. （1959）. Production lines and internal storage—A review[J]. Management Science， 5，410-433.

【2】Buzacott， J. A.， & Shanthikumar， J. G. Stochastic models of manufacturing systems. New Jersey： Prentice-Hall[M].Production & Operations Management ， 2007.

【3】Dallery Y， Gershwin S B. Manufacturing flow line systems： a review of models and analytical results[J]. Queueing systems， 1992，12（1-2）：3-94.

【4】Gershwin， S. B.， & Schor， J. E.（2000）. Efficient algorithms for bufferspace allocation[J]. Annals of Operations Research，93，117-144.

【5】Aksoy， K. H.， & Gupta， S. M. （2010）. Near optimal buffer allocation in remanufacturing systems with N-policy[J]. Computers，Industrial Engineering， 59，496-508.

【6】Can， B.， & Heavey， C. （2011）. Comparison of experimental designs for simulation-based symbolic regression of manufacturing systems[J].Computers ， Industrial Engineering， 61（3）：447-462.

【7】Z.米凱利維茨.演化程序——遺傳算法和數(shù)據(jù)編碼的結(jié)合[M].北京：科學(xué)出版社，2007.

【8】劉紅，韋穗.遺傳算子的分析[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006（10） ：10-16.

【9】葛洪偉，王銀年.求解VRPSDP問(wèn)題的改進(jìn)模擬退火遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2010（30）：136-137.