基于遺傳算法的制造單元繼承性生成方法

張炳根，龍偉

?

基于遺傳算法的制造單元繼承性生成方法

張炳根，龍偉

（四川大學 制造科學與工程學院，四川 成都 610065）

為實現(xiàn)多品種變批量生產(chǎn)模式下的制造單元優(yōu)化重構，將車間重布局成本納入優(yōu)化目標，建立了以物流成本和重布局成本為優(yōu)化目標的制造單元需求模型；為了降低重布局成本，提出一種具有繼承性的制造單元生成方法，利用改進遺傳算法中的染色體編碼方式、初始種群生成方法、遺傳算子操作等方法，最大程度上保存了原有制造單元中的資源組織結構，實現(xiàn)具有繼承性的制造單元優(yōu)化重構過程；最后通過一個實例驗證了所提方法的有效性。

制造單元；重布局；遺傳算法；繼承性

當前全球在“德國工業(yè)4.0”、“中國制造2025”、“美國工業(yè)互聯(lián)網(wǎng)”等新興理念強烈沖擊影響下，設備自動化、生產(chǎn)智能化、需求個性化已成為新興工業(yè)發(fā)展的代表性特征[1]。為了適應多樣化及個性化的市場需求，以往的大規(guī)模生產(chǎn)模式紛紛向多品種變批量定制生產(chǎn)模式轉(zhuǎn)變，單元制造系統(tǒng)作為最先進的生產(chǎn)制造方式應運而生，基于單元制生產(chǎn)方式的設備布局所具有的敏捷性、柔性等優(yōu)點為實現(xiàn)精益生產(chǎn)模式奠定了良好的基礎[2]。

單元制造是以成組技術為基礎的一種生產(chǎn)模式，它根據(jù)成組技術將具有工藝相似性的零件進行分組形成零件族，通過相應的制造設備集合對其進行加工，從而提高了生產(chǎn)制造的柔性[3]。在多品種變批量的生產(chǎn)模式下，待加工產(chǎn)品種類繁多且每個種類的批量都有可能發(fā)生改變，同時每種產(chǎn)品的加工路徑都不唯一[4]，當生產(chǎn)任務發(fā)生改變時，就需要對制造單元進行重新構建，以滿足新的生產(chǎn)任務要求。

針對制造單元構建問題，國內(nèi)外學者研究出了各種制造單元生成方法，主要有聚類分析法[5-6]、智能優(yōu)化算法[7-9]、數(shù)學規(guī)劃算法[9]等。例如，文獻[11]以多工藝路線為基礎，通過將遺傳算法用于單元構建技術，提出以單元內(nèi)和單元間的物流量總和為最小優(yōu)化目標的制造單元生成方法。文獻[12]通過分析車間單元布局的可用性，在考慮多階段單元構建問題情況下將原有制造單元的可用性納入優(yōu)化目標，利用改進粒子群算法生成制造單元構建方案。

但是，現(xiàn)有的單元構建方法并未考慮制造單元之間所具有的聯(lián)系性[13]，新的單元構建方法中資源組織的配置形式相對原有制造單元不存在繼承性，而是將現(xiàn)有資源組織形式全部打亂重構，在多品種變批量生產(chǎn)模式下必將極大的增加設備移動等因素所產(chǎn)生的重布局費用。

為此本文在對現(xiàn)有制造單元中組織進行結構分析的基礎上，通過增減現(xiàn)有單元中的設備、互換不同單元間的設備等形式降低原有制造單元內(nèi)設備的變動，使新生成的制造單元能夠在最大程度上保存原有方案中的單元結構，形成具有繼承性的制造單元生產(chǎn)方法；最后建立具有繼承性評價標準的單元構建目標函數(shù)，通過改進遺傳算法求解，輸出單元構建方案。

1 制造單元問題建模

目前的單元構建方法一般是以單元內(nèi)和單元間的總物流成本作為方案的評價標準[14]。然而在多品種變批量生產(chǎn)模式下，僅考慮總物流成本難以符合實際生產(chǎn)需求，尤其在制造設備眾多的重布局過程中，大型設備移動、多階段單元構建、批量變動等實際因素，重布局費用所占比重將隨之增大，為此本文對制造單元問題建模時不僅考慮總物流費用1，還將重布局費用2納入優(yōu)化目標，由此本文提出的單元構建目標函數(shù)為：

1.1 物流成本

多品種變批量生產(chǎn)模式下，考慮多工藝路線的單元間及單元內(nèi)的總物流成本1為：

1.2 重布局成本

車間的重布局成本主要與制造設備的位置變動有關，新的制造單元與原有制造單元間的資源組織形式越相似，車間制造設備變動幅度將越小，說明單元構建方法所生成的方案具有的繼承性越高，重布局成本將越低。為了表示制造設備的變動幅度和單元構建方案的繼承性，定義設備變動系數(shù)和繼承性系數(shù)：

重布局成本主要與制造單元組織結構的變動幅度，大小由繼承性系數(shù)決定，由此本文構建重布局成本2為：

式中：為重布局成本與物流成本的比重，其由任務變更頻率、資源調(diào)整幅度等因素決定，本文以物流成本為主要成本，根據(jù)單元構建需求?。?.01；＝0時表示新的單元構建方案與原有的單元構建之間不具有繼承性，此時重布局成本最大，＝1時表示新的單元構建方案具有最大的繼承性，此時不產(chǎn)生重布局成本，由此將單元構建方案的繼承性納入方案的評價指標。

根據(jù)總成本目標函數(shù)進行約束分析，采用文獻[10]中常規(guī)制造約束，一臺設備只能在一個制造單元內(nèi)；一個零件只能屬于一個制造單元，當零件的某道工序需在其他制造單元內(nèi)的設備上加工時則屬于跨單元加工；一個零件只能采用一條工藝路線。參照文獻[11]中的布局約束分析，為簡化計算，定義單元內(nèi)設備的物流距離和單元內(nèi)設備的物流距離分別為：

2 基于改進遺傳算法的繼承性制造單元構建算法設計

在進行制造單元的算法設計時，為了減少原有單元中設備的變動，新的單元生成方法需在最大程度上利用原有方案中的資源組織形式，為此需提取原始制造單元的構建信息，并將其引入新制造單元的構建過程，以保證資源組織結構的繼承性。改進的遺傳算法通過染色體編碼、初始種群選取方式輸入原有單元構建方案的信息，同時利用適應度函數(shù)、交叉算子等遺傳操作最大程度上保證信息的完整性即原有資源組織結構的完整性，從而實現(xiàn)新的單元構建方案對原有方案的繼承。

2.1 染色體編碼方式

在遺傳算法中，通常用一個染色體基因信息代表遺傳算法要求解的問題，依據(jù)本文所構建的單元構建目標函數(shù)，采用文獻[10]中基于整數(shù)序列的染色體編碼方式，如圖1所示。

其中染色體的信息包含制造設備M所屬單元C、零件P所屬單元C及零件P選擇的工藝路線R。

圖1 染色體編碼方式

2.2 初始種群生成方法

在傳統(tǒng)的遺傳算法中，初始種群通常是由算法隨機生成的，由這樣的初始種群進化后產(chǎn)生的最優(yōu)個體，其所對應的制造單元構建方案可能是推倒重排式的構建方法，對原有單元的組織結構具有極大的破壞性，同時搜索效率低下；為了實現(xiàn)新制造單元構建方案對原始方案的繼承，本文構建一組具有繼承性的初始種群，其構建過程為：

（1）根據(jù)原有的單元構建方案，提取制造單元內(nèi)設備零件工藝路線的對應關系，通過染色體編碼的方式將其轉(zhuǎn)化為初始解，如圖2所示；

（2）將新的生產(chǎn)任務隨機分配到制造單元C中，由此產(chǎn)生的編碼插入初始解對應的子段，例如將新增加工任務零件P5隨機分配到制造單元C2中，則新個體染色體編碼方式如圖3所示，同時刪除其中違背約束關系的個體，生成具有繼承性的初始種群。

圖2 初始解染色體編碼方式

2.3 適應度函數(shù)及遺傳算子操作

遺傳算法的適應度函數(shù)一般由所構建的目標函數(shù)轉(zhuǎn)變而來，當構建的函數(shù)以最小值為優(yōu)化目標時，可將適應度函數(shù)設置為所構建函數(shù)的倒數(shù)。本文根據(jù)模型構建過程中的最低總成本函數(shù)，將適應度函數(shù)設置為()＝1/，個體適應值越大則成本越低，說明個體適應度越好。目標函數(shù)中包含繼承性系數(shù)表明了適應度函數(shù)對個體的繼承性優(yōu)劣有一定的評判能力。采用輪盤賭選擇法確定被選中的個體；然后在染色體中設備、零件、工藝路線三個子段內(nèi)分別通過二進制編碼中的單點交叉方式組合出新的個體；針對新的個體通過改變?nèi)旧w上的數(shù)值進行變異，染色體的基因可突變?yōu)槠淙≈捣秶鷥?nèi)的任何數(shù)值，以此防止遺傳算法陷入局部收斂；最后根據(jù)所定的終止進化代數(shù)來結束算法。

2.4 算法步驟

步驟1：設定改進遺傳算法中的各項參數(shù)，包括初始種群數(shù)量、交叉概率P、變異概率P、進化代數(shù)＝1及算法的終止進化代數(shù)等；

步驟2：根據(jù)模型分析過程中構建的最低總成本函數(shù)設置適應度函數(shù)，提取原有單元構建方案信息，根據(jù)上文所述初始種群生成方法產(chǎn)生具有繼承性的初始種群；

步驟3：對種群中的各個體進行適應度計算；

步驟4：根據(jù)個體的適應度大小，利用輪盤賭選擇法從父代種群中選取兩個個體進行交叉、變異操作，得到子代個體；

步驟5：判斷算法的進化代數(shù)。若＝，則進入步驟6；否則回到步驟3；

步驟6：算法結束，將適應度值最大的染色體作為新的單元構建方案。

3 實例分析

本文以某發(fā)動機生產(chǎn)車間為例，闡述生產(chǎn)任務變動后具有繼承性的制造單元構建方法。某階段該車間的生產(chǎn)任務發(fā)生變動，具體的零件批量變化、工藝路線信息如表1所示，新增大批量生產(chǎn)任務P9和P10如表2所示。

表1 零件加工批量及工藝信息

表2 新增生產(chǎn)任務

運用Matlab軟件編寫遺傳算法運行程序。設定改進遺傳算法中的各項參數(shù)：＝100，P＝0.65，P＝0.03，＝400，依據(jù)表3中原制造單元構建方案對染色體進行編碼并生成具有繼承性的初始種群，運行程序得到改進遺傳算法收斂過程如圖4所示，算法在140代附近進入收斂狀態(tài)，對應的函數(shù)值為3262.11，染色體值為{1,1,3,2,3,1,2,3,2,2,1,3,3,2,1,1,2,3,1,3,2,2,1,1,3, 2,1,2,1,1,1,1}。

為了驗證算法的優(yōu)越性,利用基本遺傳算法對本文所構建的目標函數(shù)進行求解，其收斂過程如圖5所示，算法在250代附近進入收斂狀態(tài)，對應的函數(shù)值為3478.67；通過對比圖4和圖5可知，本文的改進遺傳算法通過繼承性調(diào)整，其收斂速度是基本遺傳算法的近一倍，同時優(yōu)化結果更為理想。

表3 原制造單元構建方案

根據(jù)上文的最優(yōu)染色體，對應的單元構建方案如表4所示。生產(chǎn)任務變化后，單元構建過程如下：將原有制造單元C1中的設備M9分配到新制造單元C2，原有制造單元C1中的M5和C3中的M6進行互換，形成新的制造單元C1和C3，并將新增生產(chǎn)任務P9和P10同時分配到新制造單元C2所對應的零件集合，方案在保證成本最小的同時，最大程度上繼承了原有制造單元的組織結構。

圖4 改進遺傳算法收斂過程

圖5 基本遺傳算法收斂過程

表4 新制造單元構建方案

4 結束語

針對傳統(tǒng)單元構建方法存在的不足，本文提出的具有繼承性的制造單元生成方法，通過將繼承性系數(shù)引入目標優(yōu)化函數(shù)，實現(xiàn)算法對制造單元方案繼承性優(yōu)劣的判別，并且由具有繼承性的單元構建方法得到的單元構建方案，能減小制造單元中設備的頻繁變動，降低重布局時間，可在一定程度上提高車間的生產(chǎn)效率。

[1]蘇誠，許朋剛，代志良. 智能倉儲系統(tǒng)設計與開發(fā)應用[J]. 機械，2017，44（10）：65-71.

[2]Nima Safaei，Reza Tavakkoli-Moghaddam. Integrated multi-period cell formation and subcontracting production planning in dynamic cellular manufacturing systems [J]. International Journal of Production Economics，2009（20）：301-314.

[3]王曉晴，唐加福. 基于分散搜索的零部件跨單元生產(chǎn)的單元管理方法[J]. 機械工程學報，2009，45（10）：125-131.

[4]牛力. 資源布局可變條件下的開放車間柔性制造單元構建技術研究[J]. 科學技術與工程，2011，11（25）：6054-6059.

[5]King JR. Machine-component grouping in production flow analysis: an approach using a rank order clustering algorithm[J]. International Journal of Production Research，1980，18（2）：213-32.

[6]李杰，王云峰，朱昭賢，徐勇. 基于模糊技術的制造單元構建方法研究[J]. 計算機集成制造系統(tǒng)，2004，10（12）：1561-6.

[7]鄭玉彬，韓峰，何宇，曲植. 基于遺傳算法的可重構制造單元布局研究[J]. 機械設計與制造，2009（9）：193-4.

[8]Rezazadeh H，Mahini R，Zarei M. Solving a dynamic virtual cell formation problem by linear programming embedded particle swarm optimization algorithm[J]. Applied Soft Computing，2011，11（3）：3160-9.

[9]王國新，閻艷，寧汝新，王愛民. 模糊神經(jīng)網(wǎng)絡與啟發(fā)式算法相結合的制造單元構建方法[J]. 計算機集成制造系統(tǒng)，2008，14（11）：2175-83.

[10]TSAICC，LEECY. Optimization of manufacturing cell formation with a multi-functional mathematical programming model [J]. International Journal of Advanced Manufacturing Technology，2006，30（3）：309-318.

[11]劉雪梅，朱麗君，李愛平，黃君政. 基于遺傳算法的生產(chǎn)車間制造單元構建技術研究[J]. 制造技術與機床，2013（2）：57-61.

[12]陶俐言，聶清，王志鋒，梁滿棠. 面向變批量生產(chǎn)的制造單元構建方法[J]. 計算機集成制造系統(tǒng)，2014（10）：2411-2418.

[13]李京生. 面向多品種變批量生產(chǎn)的重構調(diào)度方法[D]. 北京：北京理工大學，2015.

[14]ADIL G K. The trade-off between intracell and intercell moves in group technology cell formation[J]. Journal of Manufacturing Systems，2000，19（5）：305-317.

Inherited Methodology of Manufacturing Cell Formation Based on Genetic Algorithm

ZHANG Binggen，LONG Wei

(School of Manufacturing Science and Engineering, Sichuan University, Chengdu 610065, China)

In order to achieve manufacturing cell optimized reconfiguration in the production mode of multi variety and variable batch, this article introduced the cost of shop layout to the optimization goal, and established the demand model of manufacturing cell with the cost of logistics and the cost of shop layout. In order to reduce the cost of reconfigure, a method of generating unit with inherited was proposed. By using the improved genetic algorithm, such as chromosome coding, initial population generation and genetic operator operation, the resource organization structure of the original manufacturing cell was maximum saved, and realized the succession of the new manufacturing cell to the original cell. Finally, the effectiveness of the proposed method is verified by a numerical example.

manufacturing cell；reconfigure；genetic algorithm；inheritance

TH165

A

10.3969/j.issn.1006-0316.2018.01.004

1006－0316 (2018) 01－0018－06

2017－05－15

張炳根（1989－），男，江西婺源人，碩士研究生，主要研究方向為現(xiàn)代控制工程與計算機應用；龍偉（1956－），男，重慶人，工學博士，教授，主要研究方向為機械制造及自動化。