徐立云, 劉　偉, 樓科文, 李愛平

(同濟(jì)大學(xué) 現(xiàn)代制造技術(shù)研究所，上海 201804)

?

基于改進(jìn)免疫遺傳算法的加工工藝重構(gòu)

徐立云, 劉偉, 樓科文, 李愛平

(同濟(jì)大學(xué) 現(xiàn)代制造技術(shù)研究所，上海 201804)

摘要：針對(duì)產(chǎn)品生命周期內(nèi)不同階段市場(chǎng)需求量不同，通過添加或移除相應(yīng)機(jī)床與裝夾設(shè)備以滿足其產(chǎn)能需求變化.針對(duì)某產(chǎn)品減產(chǎn)情況，基于抽調(diào)原則選擇合適生產(chǎn)設(shè)備進(jìn)行移除以適應(yīng)產(chǎn)能需求；采用一種疫苗自動(dòng)獲取與動(dòng)態(tài)更新的改進(jìn)免疫遺傳算法，通過對(duì)相應(yīng)基因座上基因值的轉(zhuǎn)移調(diào)整替代交叉變異算子，從而實(shí)現(xiàn)可轉(zhuǎn)移操作在不同工位間的轉(zhuǎn)移，并以瓶頸節(jié)拍時(shí)間最短和工位間不平衡度最小為目標(biāo)函數(shù)，對(duì)原有加工工藝轉(zhuǎn)移重構(gòu)從而達(dá)到新構(gòu)形下的工藝平衡與優(yōu)化.最后通過實(shí)例分析與對(duì)比驗(yàn)證方法的有效性.

關(guān)鍵詞：可重構(gòu)制造系統(tǒng)； 工藝重構(gòu)； 生產(chǎn)構(gòu)形； 改進(jìn)免疫遺傳算法

近年來個(gè)性化需求不斷提高，產(chǎn)品市場(chǎng)需求波動(dòng)更為頻繁，可重構(gòu)制造系統(tǒng)(reconfigurable manufacturing system, RMS)應(yīng)運(yùn)而生.該理念由密西根大學(xué)Y. Koren教授[1]首次提出，因其能夠快速調(diào)整系統(tǒng)生產(chǎn)能力大小與生產(chǎn)功能范圍以應(yīng)對(duì)市場(chǎng)的不規(guī)則需求，故受到國(guó)內(nèi)外學(xué)者的普遍關(guān)注.

目前，制造系統(tǒng)重構(gòu)研究主要集中在2個(gè)方面：第一方面是關(guān)于機(jī)床設(shè)備功能模塊的增減研究.如文獻(xiàn)[2-5]均通過對(duì)可重構(gòu)機(jī)床(reconfigurable manufacturing tool, RMT)子模塊的增減而提升或降低機(jī)床的生產(chǎn)能力.Shbaka等[6]通過對(duì)加工特征與機(jī)床模塊的對(duì)應(yīng)關(guān)系來實(shí)現(xiàn)不同零件的加工操作的組合.另一方面則是關(guān)于系統(tǒng)物理構(gòu)形的研究，如增添或移除機(jī)床、更改物流系統(tǒng)等，從而改變生產(chǎn)線的生產(chǎn)范圍與生產(chǎn)能力.如Wang等[7]介紹了添加或移除機(jī)床來調(diào)整制造單元產(chǎn)能以適應(yīng)市場(chǎng)需求，并利用改進(jìn)遺傳算法確定系統(tǒng)最經(jīng)濟(jì)的重構(gòu)方式.EIMaraghy[8]和Azab等[9]都提出可重構(gòu)工藝規(guī)劃(reconfigurable process planning, RPP)的概念，但其RPP模型均是利用零件族的標(biāo)準(zhǔn)工藝規(guī)程建立了面向進(jìn)化零件族的工序，研究對(duì)象是零件族內(nèi)所增添的新特征與新加工操作，針對(duì)這些新內(nèi)容對(duì)原有工藝進(jìn)行增加或刪除部分相關(guān)內(nèi)容.Putnik等[10]對(duì)產(chǎn)能縮放的概念進(jìn)行了詳細(xì)的論述.樓洪梁等[11-12]應(yīng)用排隊(duì)論方法，分別建立了單雙零件族隨機(jī)市場(chǎng)需求模型與RMS的排隊(duì)模型，結(jié)合倉(cāng)儲(chǔ)容量大小研究確定RMS在各需求周期的最優(yōu)產(chǎn)能.Aguilar等[13]研究在設(shè)備選型、混流生產(chǎn)以及隨機(jī)需求等不同情況下產(chǎn)能的確定.段建國(guó)等[14]通過對(duì)生產(chǎn)能力縮放性原理的研究，給出了實(shí)現(xiàn)產(chǎn)能重構(gòu)的實(shí)現(xiàn)思路.綜上所述，現(xiàn)有可重構(gòu)系統(tǒng)產(chǎn)能方面的研究多集中于可重構(gòu)機(jī)床，對(duì)于工藝重構(gòu)方面的研究則多是針對(duì)產(chǎn)品族內(nèi)出現(xiàn)的新特征與新操作，具體到加工工序方面的工藝重構(gòu)研究涉及較少.

本文針對(duì)市場(chǎng)需求量下降的產(chǎn)品生產(chǎn)線，通過減少設(shè)備量改變其生產(chǎn)構(gòu)形，基于改進(jìn)免疫遺傳算法實(shí)現(xiàn)加工工藝的重構(gòu)，進(jìn)而快速滿足市場(chǎng)生產(chǎn)需求變化.

1問題描述

研究的是具有多個(gè)制造單元的發(fā)動(dòng)機(jī)缸體生產(chǎn)車間，各制造單元間具有相同類型的生產(chǎn)設(shè)備而生產(chǎn)不同型號(hào)產(chǎn)品.假設(shè)有制造單元a和b如圖1所示，單元a所生產(chǎn)的產(chǎn)品量減少，而單元b所生產(chǎn)的產(chǎn)品量增加，此時(shí)從單元a中抽調(diào)部分機(jī)床與夾具設(shè)備到單元b，在降低單元a產(chǎn)能的同時(shí)又滿足了單元b產(chǎn)能提升需求.單元a在特征操作總時(shí)間不變前提下，計(jì)算新的生產(chǎn)節(jié)拍下所需生產(chǎn)設(shè)備數(shù)量以及可移除數(shù)量，在設(shè)備抽調(diào)原則指導(dǎo)下，對(duì)設(shè)備進(jìn)行選取并移除.待所有特征對(duì)應(yīng)的加工操作分類聚類處理后分為固定操作和可轉(zhuǎn)移操作，固定操作固定到指定工位上，而將可轉(zhuǎn)移操作在剩余工位設(shè)備上進(jìn)行轉(zhuǎn)移調(diào)整.在瓶頸節(jié)拍時(shí)間最短與工位間不平衡度最小的綜合優(yōu)化目標(biāo)下，可轉(zhuǎn)移操作在各工位間不斷調(diào)整最終達(dá)到新的工藝平衡.

a 制造單元a

b 制造單元b

2數(shù)學(xué)模型的建立

2.1缸體特征分析

發(fā)動(dòng)機(jī)缸體是典型的復(fù)雜箱體類零件，主要特征種類有平面、凸輪軸孔、主軸承孔、挺柱孔、定位基準(zhǔn)孔、缸(套)孔、螺紋孔、斜油孔、水油道孔、內(nèi)開檔等，缸體零件主要模型如圖2所示.不同特征分別對(duì)應(yīng)不同加工方法，主要特征的加工鏈如表1所示.

a

b

表1　缸體零件主要特征加工鏈

2.2特征約束

約束是指在工藝實(shí)踐中的表現(xiàn)為加工先后順序上的要求，是工藝路線中最重要的要求.必須考慮的幾類關(guān)系有：①先基準(zhǔn)后其他；②先面后孔；③先主后次等.

在特征加工方法和加工工藝參數(shù)已知情況下，制造系統(tǒng)的工藝僅需在上述約束下將選定的加工操作重新組合分配至工位上，即可實(shí)現(xiàn)加工工藝的重構(gòu).在重新分配優(yōu)化前，需將眾多操作進(jìn)行分類與聚類以減少操作數(shù)量，縮小計(jì)算規(guī)模，提高算法效率.

傳統(tǒng)的分類聚類是將缸體特征按其類型、大小不同進(jìn)行分類，再將完全相同的特征聚合為一個(gè)特征.本文在特征聚類基礎(chǔ)上對(duì)其加工操作進(jìn)行更進(jìn)一步的聚類：針對(duì)同一特征的加工鏈，若加工鏈中的連續(xù)操作加工基準(zhǔn)相同，則可將該加工鏈聚類為一個(gè)操作.如挺柱孔的擴(kuò)絞操作均以粗銑后的平面作為加工基準(zhǔn)，故在傳統(tǒng)聚類后將擴(kuò)孔與鉸孔合并為一個(gè)操作；缸套孔的粗鏜和半精鏜是以粗銑后的平面作為加工基準(zhǔn)，故粗鏜與半精鏜可聚類為一個(gè)粗鏜操作，而精鏜需精銑后的平面作為加工基準(zhǔn)，故精鏜與聚類后的粗鏜不能進(jìn)行進(jìn)一步聚類.

待操作聚類完成后，檢查每個(gè)操作能否在工位j(j=1,2,…,m)的裝夾姿態(tài)下加工以及其加工基準(zhǔn)是否在工位i(1≤i≤j)上已加工完成.將同時(shí)滿足上述2個(gè)要求的加工操作定義為該工位下的可達(dá)加工操作，根據(jù)操作在各個(gè)工位的可加工與否將每個(gè)操作的可加工工位用s表示.將傳統(tǒng)的前后優(yōu)先約束關(guān)系通過上述操作可達(dá)性判斷而轉(zhuǎn)換成操作可否在該工位上加工.故在對(duì)原有操作進(jìn)行分類聚類等預(yù)處理后可將加工操作信息表示為On=(I,s,o,t)，其中：I為操作編號(hào)；s為該操作的可加工工位集，例如操作On的s為2和3，則表示操作On可在第2工位與第3工位上進(jìn)行加工；o為特征操作內(nèi)容；t為特征操作加工時(shí)間，包括實(shí)際加工時(shí)間與輔助時(shí)間.

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

加工該零件的所有操作總時(shí)間(包括輔助時(shí)間)為Ttotal；市場(chǎng)新需求下產(chǎn)品訂單數(shù)量為Dnew；訂單Dnew下的需求周期為dp；期望節(jié)拍大小為Cexp；生產(chǎn)該零件所需的全部操作為Ototal；固定操作集為Ofix，如加工基準(zhǔn)、定位孔以及一些只能在單一裝夾姿態(tài)下完成的操作；可在不同工位、不同裝夾姿態(tài)下加工的操作集為可轉(zhuǎn)移操作，用Otrans表示；生產(chǎn)線上機(jī)床總量為M；j工位上的機(jī)床數(shù)Mj；新節(jié)拍大小為Cnew；可轉(zhuǎn)移加工操作總數(shù)為N；生產(chǎn)線工位集為S(S=1,2，…，i,…，j,…，m，m為工位總數(shù))；j工位實(shí)際分配操作加工時(shí)間與理論節(jié)拍時(shí)間的差值為Kj；生產(chǎn)線上各工位間的節(jié)拍的不平衡度為U；瓶頸節(jié)拍時(shí)間為CB；j工位上的所有固定操作時(shí)間總和為Tfix(j)；j工位的節(jié)拍時(shí)間為Cj；算法迭代次數(shù)為g.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

式(1)計(jì)算新訂單要求下的期望節(jié)拍時(shí)間；式(2)計(jì)算新的生產(chǎn)任務(wù)下所需機(jī)床數(shù)目，若Ttotal|Cexp，則M=Ttotal/Cexp；式(3)計(jì)算新需求下的新節(jié)拍值；所有操作間的關(guān)系如式(4)所示；式(5)表示操作On的可轉(zhuǎn)移工位集s；式(6)表示任意可轉(zhuǎn)移操作只能分配到其中一個(gè)可轉(zhuǎn)移工位上；式(7)表示工位上所分配的操作的總時(shí)間不能超過該工位上機(jī)床設(shè)備所能提供的總加工時(shí)間；式(8)用以計(jì)算操作分配后工位的實(shí)際生產(chǎn)節(jié)拍與期望節(jié)拍的差值，在分配過程中，若該值大于零，則表示工位上的操作分配過多，超出該工位所能提供的生產(chǎn)能力范圍，此時(shí)需將該工位標(biāo)記為待轉(zhuǎn)出工位.反之，則表示該工位上仍能接受新操作，將該工位標(biāo)記為可轉(zhuǎn)移工位；式(9)為各工位間不平衡度，用以衡量工位間機(jī)床的平衡率；式(10)表示瓶頸節(jié)拍時(shí)間.

目標(biāo)函數(shù)：重構(gòu)工藝方案的目標(biāo)為瓶頸節(jié)拍時(shí)間最短且工位間不平衡度最小，故分別采用瓶頸節(jié)拍時(shí)間CB與工位間不平衡度U值來衡量，采用統(tǒng)一目標(biāo)W表示為

(11)

式中：λ為權(quán)重系數(shù)，通過調(diào)節(jié)該值可調(diào)整在目標(biāo)函數(shù)W中U和CB所占比例的不同.該目標(biāo)函數(shù)中已包含物流搬運(yùn)的影響，因縮量生產(chǎn)通過移除設(shè)備來體現(xiàn)，重構(gòu)成本可以忽略.

3算法設(shè)計(jì)

3.1抽調(diào)原則的確定

市場(chǎng)需求減少，產(chǎn)能應(yīng)相應(yīng)降低，應(yīng)先完成生產(chǎn)線物理構(gòu)形的重構(gòu)，即計(jì)算確定要移除的機(jī)床數(shù)，選取抽調(diào)工位后將多余設(shè)備從該生產(chǎn)線上移除，然后通過算法完成新構(gòu)形下的工藝重構(gòu).因此，選取移除的機(jī)床設(shè)備是工藝重構(gòu)的基礎(chǔ).為盡快完成工藝重構(gòu)，盡量不涉及太多變動(dòng)，包括裝夾方案應(yīng)保持不變.具體的抽調(diào)原則規(guī)定如下.

(1)選擇具有并聯(lián)機(jī)床的工位作為移除機(jī)床工位，工位上的所有固定加工操作總時(shí)間應(yīng)不大于工位上剩余機(jī)床所能提供的加工能力，如式(12)所示：

(12)

式中：q為將被抽調(diào)走的機(jī)床數(shù).若各工位的固定加工操作時(shí)間均沒有超過新節(jié)拍時(shí)間，則進(jìn)入條件(2)的選擇.

(2)選擇沒有固定加工操作的工位，即該工位上的加工操作均能轉(zhuǎn)移至生產(chǎn)線上其他工位進(jìn)行加工.如果生產(chǎn)線上各工位均不滿足該條件，則進(jìn)入條件(3)進(jìn)行選擇.

(3)統(tǒng)計(jì)各工位的可轉(zhuǎn)移操作數(shù)目，選取該數(shù)目值最多者作為抽調(diào)工位.

3.2改進(jìn)免疫遺傳算法簡(jiǎn)介

傳統(tǒng)遺傳算法是一種隨機(jī)生成后檢測(cè)滿足與否的不斷迭代搜索算法，其本質(zhì)是一種通過目標(biāo)函數(shù)的限制實(shí)現(xiàn)定向制導(dǎo)的隨機(jī)搜索技術(shù).然而，交叉和變異2個(gè)算子卻是在一定概率下隨機(jī)地沒有指導(dǎo)的迭代搜索[15]，這使得遺傳算法收斂速度緩慢，甚至出現(xiàn)退化現(xiàn)象.為了彌補(bǔ)遺傳算法的不足，引入生物免疫機(jī)制，使用一種有指導(dǎo)性的轉(zhuǎn)移方法替代交叉和變異算子，給出一種基于疫苗自動(dòng)獲取與動(dòng)態(tài)更新的改進(jìn)免疫遺傳算法，利用先驗(yàn)知識(shí)構(gòu)造疫苗，并利用免疫檢測(cè)實(shí)現(xiàn)自我調(diào)節(jié)，防止算法退化，提高算法收斂效率.

采用改進(jìn)免疫遺傳算法對(duì)染色體進(jìn)行進(jìn)化操作以實(shí)現(xiàn)種群的進(jìn)化，從而生成更優(yōu)秀的新種群，不斷迭代尋求最優(yōu)解.主要改進(jìn)部分的思想是：在下一代種群的生成過程中，要求每次轉(zhuǎn)移都能實(shí)現(xiàn)工位間不平衡度的減少，有針對(duì)性地實(shí)現(xiàn)種群的進(jìn)化.具體種群更新進(jìn)化實(shí)現(xiàn)步驟如下：

(1)計(jì)算各工位K值，分別選定最大與最小K所在工位為轉(zhuǎn)出工位和轉(zhuǎn)移目標(biāo)工位.

(2)檢查轉(zhuǎn)出工位與轉(zhuǎn)移目標(biāo)工位間有無可轉(zhuǎn)移操作，有則記錄所有可轉(zhuǎn)移操作并轉(zhuǎn)至步驟(3)；否則，轉(zhuǎn)至步驟(4).

(3)從可轉(zhuǎn)移操作中隨機(jī)抽出一個(gè)操作進(jìn)行轉(zhuǎn)移，將操作轉(zhuǎn)移后得到的個(gè)體作為中間個(gè)體.

(4)保持轉(zhuǎn)出工位不變，剔除已檢查的轉(zhuǎn)移目標(biāo)工位后，選取K最小值所在工位為轉(zhuǎn)移目標(biāo)工位，轉(zhuǎn)至步驟(2).

加工操作在工位間轉(zhuǎn)移后，各工位的操作集需進(jìn)行及時(shí)更新.該操作集將作為中間種群進(jìn)行免疫算子操作，經(jīng)免疫算子操作后選擇出新個(gè)體組成下一代種群，實(shí)現(xiàn)種群的更新.

3.3求解過程

(1)令g=1，將選出的抽調(diào)工位作為轉(zhuǎn)出工位，隨機(jī)生成初始轉(zhuǎn)移方案.每個(gè)轉(zhuǎn)移方案由1條染色體表示；創(chuàng)建含有r個(gè)疫苗的疫苗庫(kù)，設(shè)其值均為100 000(無窮大值).

(2)根據(jù)轉(zhuǎn)移方案，更新各工位的操作集合.

(3)計(jì)算Kj(j=1,2,…,m)，U和CB，選定轉(zhuǎn)出工位與轉(zhuǎn)移目標(biāo)工位.計(jì)算各染色體目標(biāo)函數(shù)的適應(yīng)度值，提取該代解的疫苗并與疫苗庫(kù)內(nèi)的疫苗進(jìn)行比較，將最優(yōu)的r個(gè)疫苗保存下來，實(shí)現(xiàn)疫苗庫(kù)的動(dòng)態(tài)更新.

(4)種群的更新進(jìn)化.

(5)將得到的中間個(gè)體作為父代個(gè)體，按比例抽取進(jìn)行疫苗接種，轉(zhuǎn)至步驟(6).

(6)對(duì)接種疫苗的個(gè)體進(jìn)行免疫檢測(cè)，計(jì)算其適應(yīng)度值，若接種后適應(yīng)度低于父代個(gè)體，則取消接種；否則，接受接種結(jié)果.經(jīng)檢測(cè)后的個(gè)體組成新種群.轉(zhuǎn)至步驟(7).

(7)若g≤gmax，令g=g+1，轉(zhuǎn)至步驟(2)；否則轉(zhuǎn)至步驟(8).

(8)結(jié)束.

4案例分析

某柴油機(jī)廠發(fā)動(dòng)機(jī)缸體生產(chǎn)車間共有4個(gè)制造單元,即1，2，3，4，每個(gè)單元分別生產(chǎn)一款產(chǎn)品.各單元內(nèi)均有7臺(tái)完全相同的四軸加工中心組成粗加工島；另外共有8臺(tái)加工中心組成精加工島.加工車間區(qū)域分布如圖3所示.

現(xiàn)根據(jù)市場(chǎng)需求情況了解到，1號(hào)單元生產(chǎn)的缸體正處于成長(zhǎng)階段，產(chǎn)量需求不斷增大；而2號(hào)單元生產(chǎn)的缸體已處于衰退階段，產(chǎn)品訂單下降.故現(xiàn)計(jì)劃提高1號(hào)單元的產(chǎn)能，而降低2號(hào)單元產(chǎn)能.

圖3　加工車間示意

2號(hào)單元所生產(chǎn)的發(fā)動(dòng)機(jī)缸體模型信息如圖4所示，加工所需總工時(shí)為3 369.9 s，共有5個(gè)工位，除工位1為單工位外，其余工位均為并行工位(各2臺(tái)設(shè)備).工廠機(jī)床設(shè)備1年有270 d進(jìn)行加工作業(yè)，實(shí)行兩班制，每天工作時(shí)間為16 h；原生產(chǎn)綱領(lǐng)為每年40 000臺(tái)，現(xiàn)計(jì)劃減產(chǎn)至每年35 000臺(tái).各工位的裝夾定位方式分別如下：①以底面600面作為粗基準(zhǔn)，以缸套孔定位，600面向下.②以左側(cè)面300面為基準(zhǔn)，結(jié)合兩水悶孔進(jìn)行一面兩銷定位，300面朝下.③以底面600面作為基準(zhǔn)面，一面兩銷定位.④以前端面200面及其面上兩銷進(jìn)行定位，利用工作臺(tái)旋轉(zhuǎn)加工特殊工位特征——斜孔，精加工600面作為后續(xù)工位的精加工基準(zhǔn).⑤以600面為精加工基準(zhǔn)，一面兩銷進(jìn)行定位.

根據(jù)訂單需求，計(jì)算期望節(jié)拍時(shí)間為Cexp=3 600×16×270÷35 000=444.34 s，所需設(shè)備數(shù)M=(3 369.9/444.34)+1=8臺(tái)，即可從2號(hào)制造單元抽調(diào)9-8=1臺(tái)設(shè)備轉(zhuǎn)移至1號(hào)制造單元，支持1號(hào)單元產(chǎn)能提升.則2號(hào)單元實(shí)際新節(jié)拍時(shí)間為Cnew=3 369.9÷8≈421.2 s.

原工藝方案整理如表2左側(cè)部分所示，其中黑體表示該操作從原工藝中其他工位上轉(zhuǎn)移而來；×符號(hào)表示該操作為固定加工操作，如工位1上加工的水悶孔將作為工位2的定位基準(zhǔn)，故其加工操作必須作為固定操作在工位1上.原方案中各工位的固定加工操作的總工時(shí)分別為252.13，217.21，0，495.12，624.66 s.根據(jù)移除機(jī)床選擇原則，工位4和工位5必須保證有2臺(tái)機(jī)床以確保固定加工操作能夠分配；根據(jù)抽調(diào)原則(2)，工位3必然選定為抽調(diào)工位且為初始解中的轉(zhuǎn)出工位.

b

4.1編碼與譯碼

編碼：本文采用實(shí)數(shù)制編碼方式.由表2左側(cè)原有工藝可知，工位1至工位5上總計(jì)有5+8+22+6+1=42個(gè)可轉(zhuǎn)移操作，故需生成具有42個(gè)基因位的染色體.每個(gè)基因位上的基因值均從操作的可轉(zhuǎn)移工位s中隨機(jī)抽取.如圖5所示的染色體方案示例，該方案包含原有5個(gè)工位的42個(gè)可轉(zhuǎn)移操作，其中原工位1的5個(gè)可轉(zhuǎn)移操作的初始轉(zhuǎn)移方案是分別轉(zhuǎn)移至工位1、工位4、工位4、工位1和工位2，所以可轉(zhuǎn)移操作的基因值均為各自s中的可轉(zhuǎn)移工位，則可確定該染色體對(duì)應(yīng)的轉(zhuǎn)移方案為可行解.按此方法，隨機(jī)生成Ps個(gè)染色體作為初始種群.

表2　重構(gòu)前后的工藝方案

(續(xù)表2)

圖5　染色體示例

譯碼：譯碼針對(duì)染色體每個(gè)基因位上的基因值，通過基因值可找到對(duì)應(yīng)操作轉(zhuǎn)移到的工位號(hào).如圖5染色體上第1個(gè)基因位上基因值為1，表明該操作將由原工藝方案中的工位1轉(zhuǎn)移至重構(gòu)方案中的工位1，即保持不變；而第2個(gè)基因位的基因值為4，表示該操作將轉(zhuǎn)移至重構(gòu)方案中的工位4，以此類推，則可得到新工藝方案中各個(gè)工位上的所有操作.

4.2免疫算子的執(zhí)行

(1)疫苗提取.根據(jù)目標(biāo)函數(shù)計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值，若前5優(yōu)解中包含1個(gè)共同信息e，則可認(rèn)為包含信息e的解理論上有更多的可能達(dá)到最優(yōu)，故將信息e作為疫苗進(jìn)行提取并存儲(chǔ)于疫苗庫(kù)內(nèi).因每個(gè)疫苗都只是利用某一局部信息來探求全局最優(yōu)解，故應(yīng)通過迭代算法實(shí)現(xiàn)對(duì)求解問題的動(dòng)態(tài)疫苗提取，根據(jù)每代解的不同情況，將每一代的前5優(yōu)解中共同信息提取出來作為疫苗，建立動(dòng)態(tài)疫苗庫(kù).僅當(dāng)當(dāng)前代的前5優(yōu)解中有比疫苗庫(kù)中的疫苗適應(yīng)度高時(shí)，則取代疫苗庫(kù)中的現(xiàn)有疫苗成為新疫苗.

(2)接種疫苗.種群中個(gè)體總數(shù)為Ps，經(jīng)轉(zhuǎn)移操作后形成中間種群，設(shè)置抽取接種疫苗概率為α，則從中間種群中選擇出αPs個(gè)個(gè)體，對(duì)該部分被選中個(gè)體進(jìn)行疫苗接種操作，即將該部分個(gè)體的染色體上對(duì)應(yīng)的基因位的基因值更改為記錄下來的值.

(3)免疫檢測(cè).免疫檢測(cè)算子是指在種群接種疫苗后計(jì)算其適應(yīng)度值，若接種后的適應(yīng)度值比接種前的適應(yīng)度值低，則放棄此次的接種，保持原染色體值不變；反之，則接受.

4.3參數(shù)設(shè)置

利用Matlab軟件進(jìn)行編程計(jì)算，分別設(shè)置參數(shù)為不同數(shù)值，經(jīng)過多次試驗(yàn)，綜合收斂速度和收斂結(jié)果后得到各自最佳參數(shù)值為：種群大小Ps=40，迭代次數(shù)gmax=200，抽取疫苗比例α=5%，權(quán)重系數(shù)λ=1/40.試驗(yàn)采用計(jì)算機(jī)配置如下：i5-4200U雙核處理器，4G DDR3內(nèi)存，采用上述參數(shù)進(jìn)行程序?qū)?yōu)時(shí)耗時(shí)359 s.算法尋優(yōu)過程如圖6所示，求得最優(yōu)解的工位間不平衡度U=9.29 s，瓶頸工位節(jié)拍時(shí)間CB=422.35 s.重構(gòu)工藝方案如表2右側(cè)所示，并在表中列出各操作重構(gòu)前所在工位號(hào).

圖6　IIGA算法尋優(yōu)

圖7為傳統(tǒng)遺傳算法(GA)與改進(jìn)免疫遺傳算法(IIGA)的收斂情況對(duì)比.前者因交叉變異操作的隨機(jī)盲目性，在第32代解時(shí)產(chǎn)生退化現(xiàn)象；而后者可有效避免退化現(xiàn)象，收斂速度更快，結(jié)果更優(yōu).

圖7　GA與IIGA收斂情況

5結(jié)語(yǔ)

針對(duì)產(chǎn)品生產(chǎn)需求減小的情況，對(duì)系統(tǒng)工藝重構(gòu)進(jìn)行了研究.通過對(duì)加工操作的預(yù)處理，將傳統(tǒng)先后約束關(guān)系轉(zhuǎn)換成操作能否在工位上加工.基于生產(chǎn)線上機(jī)床設(shè)備選取抽調(diào)原則，選取并移除適當(dāng)?shù)臋C(jī)床設(shè)備，構(gòu)建了系統(tǒng)工位間不平衡度與瓶頸節(jié)拍時(shí)間最小的綜合優(yōu)化模型，將免疫算子嵌入遺傳算法中，并使用轉(zhuǎn)移操作替代交叉變異算子設(shè)計(jì)改進(jìn)免疫遺傳算法來完成模型求解.該算法不僅繼承了遺傳算法的強(qiáng)大搜索能力，還結(jié)合了疫苗的局部最優(yōu)性質(zhì)，使收斂速度加快.最后以某企業(yè)的缸體生產(chǎn)線為例，有效地驗(yàn)證了本文所給方法的可行性，可供箱體類零件的工藝規(guī)劃借鑒.

參考文獻(xiàn):

[1]Koren Y, Heisel U, Jovane F,etal. Reconfigurable manufacturing systems[J]. CIRP Annals-Manufacturing Technology, 1999, 48(2): 527.

[2]Landers R G, Min B K, Koren Y. Reconfigurable machine tools[J]. CIRP Annals-Manufacturing Technology, 2001, 50(1): 269.

[3]Spicer P, Koren Y, Shpitalni M,etal. Design principles for machining system configurations[J]. CIRP Annals-Manufacturing Technology, 2002, 51(1): 275.

[4]Goyal K K, Jain P K, Jain M. Multiple objective optimization of reconfigurable manufacturing system[C]∥ Proceedings of the International Conference on Soft Computing for Problem Solving. Roorkee: Springer India, 2012:453-460.

[5]Goyal K K, Jain P K, Jain M. A novel methodology to measure the responsiveness of RMTs in reconfigurable manufacturing system[J]. Journal of Manufacturing Systems, 2013, 32(4):724.

[6]Shabaka A I, ElMaraghy H A. A model for generating optimal process plans in RMS[J]. International Journal of Computer Integrated Manufacturing, 2008, 21(2): 180.

[7]Wang W, Koren Y. Scalability planning for reconfigurable manufacturing systems[J]. Journal of Manufacturing Systems, 2012, 31(2): 83.

[8]ElMaraghy H A. Reconfigurable process plans for responsive manufacturing systems[C]∥Digital Enterprise Technology. Boston: Springer US, 2007:35-44.

[9]Azab A, ElMaraghy H A. Mathematical modeling for reconfigurable process planning[J]. CIRP Annals-Manufacturing Technology, 2007, 56(1): 467.

[10]Putnik G, Sluga A, Elmaraghy H,etal. Scalability in manufacturing systems design and operation: State-of-the-art and future developments roadmap[J]. CIRP Annals-Manufacturing Technology, 2013, 62(2):751.

[11]樓洪梁, 楊將新, 林亞福,等. 單零件族可重構(gòu)制造系統(tǒng)的生產(chǎn)能力優(yōu)化設(shè)計(jì)[J]. 農(nóng)業(yè)機(jī)械學(xué)報(bào), 2007, 38(2):125.

LOU Hongliang, YANG Jiangxin, LIN Yafu,etal. Optimal capacity design of reconfigurable manufacturing system for single part family[J]. Transactions of the Chinese Society for

Agricultural Machinery, 2007, 38(2):125.

[12]樓洪梁, 楊將新, 林亞福,等. 雙零件族隨機(jī)環(huán)境下可重構(gòu)制造系統(tǒng)的生產(chǎn)能力設(shè)計(jì)[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2007, 13(1):13.

LOU Hongliang, YANG Jiangxin, LIN Yafu,etal. Capacity design of RMS for double product families under stochastic demand[J].Computer Integrated Manufacturing Systems, 2007, 13(1):13.

[13]Aguilar A, Roman-Flores A, Huegel J C. Design, refinement, implementation and prototype testing of a reconfigurable lathe-mill[J]. Journal of Manufacturing Systems, 2013, 32(2):364.

[14]段建國(guó), 李愛平, 謝楠,等. 可重構(gòu)制造系統(tǒng)生產(chǎn)能力擴(kuò)展性重構(gòu)方法[J]. 同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版, 2012, 40(9):1357.

DUAN Jianguo, LI Aiping, XIE Nan,etal. Reconfiguration method on production capacity expansion in RMS [J].Journal of Tongji University: Natural Science, 2012, 40(9):1357.

[15]韓學(xué)東, 洪炳熔, 孟偉. 基于疫苗自動(dòng)獲取與更新的免疫遺傳算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2005, 42(5): 740.

HAN Xuedong, HONG Bingrong, MENG Wei. An immune genetic algorithm based on vaccine autonomous obtaining and updating[J]. Journal of Computer Research and Development, 2005, 42(5): 740.

收稿日期：2015-06-29

基金項(xiàng)目：上海市科技創(chuàng)新行動(dòng)計(jì)劃(15111105502)；上海市經(jīng)信委產(chǎn)學(xué)研項(xiàng)目(滬CXY-2013-31).

中圖分類號(hào)：TH162

文獻(xiàn)標(biāo)志碼：A

Reconfigurable Process Planning Based on Improved Immune Genetic Algorithm

XU Liyun, LIU Wei, LOU Kewen, LI Aiping

(Institute of Advanced Manufacturing Technology, Tongji University, Shanghai 201804, China)

Abstract：According to the demand changes from the competitive market, machine tools and other resources could be added or removed from manufacturing or assembling lines to meet different outputs. In the case of production reduction, appropriate equipment were selected and removed to change the capacity of the existing manufacturing line based on the removing principle. An improved immune genetic algorithm based on vaccine autonomous obtaining and updating was proposed, crossover and mutation operation in traditional genetic algorithm were changed to transfer and adjustment between different gene locations and transfer of operations between different stations can be realized. The objectives of reconfigurable process planning was to minimize the bottleneck cycle time and imbalance among stations. Finally, a cylinder block case was illustrated to verify the effectiveness of the given method.

Key words：reconfigurable manufacturing system； reconfigurable process planning； configuration; improved immune genetic algorithm

第一作者： 徐立云(1973—)，男，教授,博士生導(dǎo)師，工學(xué)博士，主要研究方向?yàn)橹悄苤圃?、系統(tǒng)建模與優(yōu)化、產(chǎn)品數(shù)字化設(shè)計(jì)與管理等.

E-mail：Lyxu@#edu.cn