基于改進(jìn)遺傳算法的可重構(gòu)制造系統(tǒng)快速配置*

洪胡平,張為民,謝樹聯(lián)

(同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院,上海 201800)

0 引言

如今制造企業(yè)面臨著市場(chǎng)需求的快速波動(dòng)與個(gè)性化發(fā)展趨勢(shì),需要通過生產(chǎn)定制化產(chǎn)品來滿足消費(fèi)者的不同需求。在這種情況下,高水平的定制是制造企業(yè)的關(guān)鍵競(jìng)爭(zhēng)力。為此,制造企業(yè)必須擁有快速響應(yīng)市場(chǎng)變化的新型制造系統(tǒng)?？芍貥?gòu)制造系統(tǒng)(reconfigurable manufacturing system,RMS) 由于其可重構(gòu)性[1],能夠通過快速改變其配置,為每個(gè)需求期提供精確的功能和能力,是應(yīng)對(duì)這一問題的有效解決方案。

RMS的流水線配置可以分為兩類:單零件流水線(single-product flow-line,SPFL)配置以及多零件流水線配置[2]。針對(duì)RMS的流水線配置優(yōu)化問題,國(guó)內(nèi)外學(xué)者都進(jìn)行了一定的研究。BORTOLINI等[3]提出了一種具有替代零件布線和多個(gè)需求期的RMS配置優(yōu)化模型,以平衡系統(tǒng)組建成本為目標(biāo),使用遺傳算法進(jìn)行求解。徐修立等[4]針對(duì)大規(guī)模定制生產(chǎn)模式,建立了設(shè)備配置優(yōu)化的0-1混合整數(shù)規(guī)劃模型,并設(shè)計(jì)采用了遺傳模擬退火算法求解。SMEDBERG等[5]針對(duì)多零件流水線的RMS配置,設(shè)計(jì)了一種知識(shí)驅(qū)動(dòng)優(yōu)化的方法,以加速RMS應(yīng)用中的收斂。牟健慧等[6]針對(duì)分布式置換流水車間問題,以最小化調(diào)整加工時(shí)間為目標(biāo),建立流水車間逆調(diào)度數(shù)學(xué)模型,提出了一種混合遺傳優(yōu)化算法進(jìn)行求解。BATTAIA等[7]開發(fā)了一個(gè)混合整數(shù)編程模型,用于配置由可重構(gòu)機(jī)床組成的流水線,以最小化設(shè)備成本。周鵬鵬等[8]針對(duì)柔性作業(yè)車間調(diào)度問題,以最大完工時(shí)間最小為目標(biāo),設(shè)計(jì)了一種混合遺傳算法進(jìn)行求解。杜百崗等[9]構(gòu)建了一個(gè)流水車間柔性分批調(diào)度模型,該模型以最小完工時(shí)間和最小加工成本為目標(biāo),并采用第二代多目標(biāo)遺傳算法進(jìn)行求解。陽光燦等[10]針對(duì)最小化最大完工時(shí)間目標(biāo)的柔性作業(yè)車間調(diào)度問題,提出了一種改進(jìn)編碼方式的遺傳算法。

在關(guān)于大規(guī)模定制背景下RMS的流水線配置問題的現(xiàn)有研究中,大多數(shù)工作僅考慮基于單一成本/時(shí)間的配置尋優(yōu),而同時(shí)考慮多個(gè)優(yōu)化目標(biāo)的研究較少,且所采用的算法也以單一尋優(yōu)算法為主。

針對(duì)上述問題,本文以RMS中的SPFL配置為研究對(duì)象,基于3個(gè)優(yōu)化目標(biāo):設(shè)備負(fù)載均衡度、產(chǎn)品生產(chǎn)時(shí)間以及產(chǎn)品生產(chǎn)成本,來建立系統(tǒng)制造資源配置模型,并構(gòu)建了一種多目標(biāo)遺傳-鄰域搜索(non-dominated sorting genetic algorithm-neighborhood search,NSGA-NS)混合算法對(duì)其優(yōu)化求解。NSGA-NS算法中,針對(duì)遺傳算法局部搜索能力較差以及易受初始種群優(yōu)劣影響等問題,受鄰域概念啟發(fā),對(duì)每一次交叉變異后的個(gè)體進(jìn)一步進(jìn)行鄰域搜索,以充分發(fā)揮不同算法各自的優(yōu)勢(shì),獲得更好的求解效果。最后通過與歸檔式多目標(biāo)模擬退火算法(archived multi-objective simulated annealing,AMOSA)[11]、第三代多目標(biāo)遺傳算法(non-dominated sorting genetic algorithm-Ⅲ,NSGA-Ⅲ)、多目標(biāo)粒子群優(yōu)化算法(multiple objective particle swarm optimization,MOPSO)以及一種在MOPSO基礎(chǔ)上改進(jìn)的多目標(biāo)退火式粒子群算法(multiple objective annealing particle swarm optimization,MOAPSO)進(jìn)行比較,驗(yàn)證其效果。

1 問題描述

對(duì)于一個(gè)確定的產(chǎn)品,可以將其劃分為一系列加工特征的集合,產(chǎn)品的每一個(gè)加工特征由一道工序完成,一道工序僅使用一種工藝類型、設(shè)備與刀具,全部工序?qū)?yīng)的工藝類型、設(shè)備與刀具的集合是該問題的一個(gè)配置解。工序所采用的工藝、設(shè)備以及刀具存在多種選擇,一個(gè)產(chǎn)品所對(duì)應(yīng)的配置解空間十分龐大。本文所關(guān)注的問題是針對(duì)新的產(chǎn)品,從配置解空間中選擇適當(dāng)?shù)呐渲觅Y源,以用于制造系統(tǒng)的搭建或重構(gòu),并完成新產(chǎn)品的生產(chǎn)。

基于以上描述,主要以機(jī)加工行業(yè)為參考,進(jìn)行如下假設(shè):

(1)產(chǎn)品的加工特征劃分可能存在不同的方案,即可行操作順序[12]?？山Y(jié)合可選設(shè)備的加工能力范圍、專家知識(shí)等制定,這些方案是已知的且本文僅對(duì)其中一種操作順序進(jìn)行配置優(yōu)化;

(2)一道工序所需刀具的數(shù)量與加工時(shí)長(zhǎng)相關(guān),向上取整;刀具的安裝時(shí)間、磨損更換時(shí)間、安裝或磨損更換的單位時(shí)間成本均為常量,與設(shè)備無關(guān);

(3)若相鄰工序所選設(shè)備相同,仍用不同的圖例表示,但計(jì)算優(yōu)化目標(biāo)時(shí)視為共用設(shè)備;

(4)不考慮設(shè)備和物料運(yùn)輸系統(tǒng)的故障與維護(hù)問題;所有設(shè)備在制造系統(tǒng)運(yùn)行過程中均開機(jī),不考慮物料運(yùn)輸系統(tǒng)的待機(jī)成本;

(5)物料運(yùn)輸成本與運(yùn)輸距離成正比,運(yùn)輸距離由設(shè)備正常工作所需最小空間決定,最小空間對(duì)設(shè)備而言為定值;

(6)物料運(yùn)輸系統(tǒng)的運(yùn)輸能力足夠,不會(huì)導(dǎo)致生產(chǎn)節(jié)拍緩滯,生產(chǎn)節(jié)拍的快慢只與加工特征、工藝、設(shè)備和刀具有關(guān);

制造系統(tǒng)配置在滿足新產(chǎn)品的生產(chǎn)需求的同時(shí),還應(yīng)盡可能提高生產(chǎn)效率、降低產(chǎn)品的生產(chǎn)成本和避免轉(zhuǎn)換時(shí)的時(shí)間浪費(fèi)。設(shè)備負(fù)載均衡度直接關(guān)系到整個(gè)制造系統(tǒng)的生產(chǎn)效率,如果機(jī)床設(shè)備的負(fù)載均衡度較高,就會(huì)出現(xiàn)某些設(shè)備空閑,而另外一些設(shè)備過度負(fù)荷的情況,進(jìn)而導(dǎo)致生產(chǎn)效率低下,資源利用率不充分。因此本文對(duì)最優(yōu)配置的評(píng)價(jià)除了考慮產(chǎn)品生產(chǎn)時(shí)間與生產(chǎn)成本外,還需考慮到設(shè)備的負(fù)載均衡度。

2 模型構(gòu)建

2.1 三元組合集

表1表示的是三元組合集的示例。一個(gè)三元組合包括一道工序所選擇的工藝類型、設(shè)備類型以及刀具類型,這道工序的執(zhí)行可以由該三元組合唯一確定。例如,第二列顯示,特征J2的操作工藝P1由包含刀具T2的設(shè)備M2來執(zhí)行。為每一個(gè)特征選擇一個(gè)可行的三元組合,便構(gòu)成三元組合集,即配置優(yōu)化問題的一個(gè)配置解。

表1 三元組合集示例

2.2 優(yōu)化目標(biāo)計(jì)算

2.2.1設(shè)備負(fù)載均衡度

通過對(duì)SPFL進(jìn)行分析,可計(jì)算出設(shè)備m的負(fù)載率Wm,式(1)表示設(shè)備負(fù)載率[13]的計(jì)算方式,其中,TMm表示設(shè)備m的所有加工工時(shí),NP表示待加工產(chǎn)品數(shù)量,TJi表示i號(hào)三元組合對(duì)應(yīng)的加工時(shí)間,THm表示設(shè)備m的所有準(zhǔn)備工時(shí),包括切換刀具的時(shí)間以及刀具磨損后更換刀頭所需的時(shí)間;T表示總加工時(shí)間,由式(6)給出。

SPFL的負(fù)載均衡度W體系生產(chǎn)線設(shè)備負(fù)載率的平衡程度,用數(shù)學(xué)模型表示為:

(1)

(2)

(3)

(4)

(5)

式中:TT表示安裝一次刀具所需時(shí)間,TT′表示刀具磨損后更換刀頭所需要的時(shí)間,kj表示加工j特征需要的刀具易耗件數(shù)量,由式(5)給出;TSt表示t型刀具的磨損更換加工時(shí)長(zhǎng)。

(6)

2.2.2 產(chǎn)品生產(chǎn)時(shí)間

在生產(chǎn)出第一件產(chǎn)品后,之后的產(chǎn)品將按照一定的生產(chǎn)節(jié)拍TA產(chǎn)出。由于制造系統(tǒng)可能存在設(shè)備共用的情況,因此本文中生產(chǎn)節(jié)拍TA可按照在不同型號(hào)設(shè)備上的生產(chǎn)流程中的瓶頸時(shí)間來確定。

T=TP+(NP-1)·TA

(7)

式中:TP表示單件產(chǎn)品的生產(chǎn)時(shí)間,MSm表示m型設(shè)備所需的最小運(yùn)行空間,TV表示物料運(yùn)輸?shù)钠骄\(yùn)輸速度。

(8)

(9)

2.2.3 產(chǎn)品生產(chǎn)成本

產(chǎn)品的總生產(chǎn)成本C主要由工序加工成本、設(shè)備待機(jī)成本、刀具磨損更換成本、物料運(yùn)輸成本、原材料成本等組成。其中,CJi表示i號(hào)三元組合的加工成本,CTt表示t型刀具的價(jià)格,CWm表示m型設(shè)備的單位待機(jī)時(shí)間成本,CD表示單位運(yùn)輸距離的物料運(yùn)輸成本,CP表示單件產(chǎn)品的原材料成本。

(10)

本模型的優(yōu)化目標(biāo)函數(shù)為:

(11)

3 模型求解方法

RMS的制造資源配置問題屬于典型的NP-Hard問題,考慮通過啟發(fā)式算法來解決。

對(duì)于多目標(biāo)優(yōu)化問題,目標(biāo)之間往往量綱不同、互相沖突,難以像單目標(biāo)優(yōu)化問題一樣直接比較目標(biāo)值來確定兩個(gè)解之間的優(yōu)劣。因此通過帕累托非支配排序算法來進(jìn)行最優(yōu)解的選擇,解空間中所有非劣解的集合即帕累托前沿解集。

3.1 編碼與解碼

待加工產(chǎn)品所需的加工工序數(shù)量n=len(J),通過一個(gè)n維向量來表示解,如表2所示。位置分量Xi表示工序i所選的三元組合。其值為0～1之間的實(shí)數(shù),即工序i所選的三元組合在可選三元組合集中的位置。

表2 解向量示例

圖1所表示的是前兩個(gè)分量的解碼過程,由一個(gè)解向量到一個(gè)配置的解碼主要基于工序可選三元組合集。工序可選三元組合集在尋優(yōu)之前生成,其主要基于車間現(xiàn)有的設(shè)備和刀具,可隨設(shè)備和刀具的增減同步更新。由位置分量Xi,可以通過等概率輪盤賭算法唯一確定第i道工序選用的三元組合,得到對(duì)應(yīng)的一個(gè)配置。

圖1 解向量到配置的解碼

3.2 多目標(biāo)遺傳-鄰域搜索算法

遺傳算法參考的是生物界的自然選擇規(guī)律,不同個(gè)體之間通過染色體交叉以及變異產(chǎn)生新的個(gè)體,并以一定的生存規(guī)則對(duì)所有個(gè)體進(jìn)行選擇,這里的生存規(guī)則即為算法中的目標(biāo)函數(shù)。NSGA-Ⅲ與其他多目標(biāo)遺傳算法的區(qū)別在于最后一個(gè)帕累托前沿的選擇機(jī)制,其使用基于參考點(diǎn)的選擇,相較于擁擠度而言,在3個(gè)以上優(yōu)化目標(biāo)的情況下仍然能夠很好地保持種群的多樣性。

遺傳算法具有隨機(jī)搜索能力,利用適當(dāng)?shù)慕徊孀儺惒僮髂軌蛴行П苊饩植孔顑?yōu)乃至獲得全局最優(yōu)。但正是由于其全局隨機(jī)性,導(dǎo)致其收斂速度較慢。而鄰域搜索算法具有快速的局部最優(yōu)搜索能力,因此考慮結(jié)合鄰域搜索對(duì)遺傳算法進(jìn)行改進(jìn),提高搜索效率,以實(shí)現(xiàn)制造資源的快速配置?；贜SGA-Ⅲ對(duì)每一次交叉變異后的個(gè)體進(jìn)行鄰域搜索,鄰域搜索算法與模擬退火中使用的一致,依賴于特征可選三元組合集。隨機(jī)選取當(dāng)前解中一個(gè)特征的三元組合,在該特征的特征可選三元組合集中,隨機(jī)選取一個(gè)除當(dāng)前組合以外的組合,替換該三元組合,以此作為當(dāng)前解的鄰域解。在本文中,命名為NSGA-NS算法,算法流程如圖2所示。

圖2 NSGA-NS流程

4 配置案例

4.1 配置案例描述

本節(jié)通過一個(gè)案例對(duì)前述問題與算法模型進(jìn)行探討。目前有一批待生產(chǎn)的液壓閥閥塊,需要從供應(yīng)商能夠提供的且滿足制造商需求的設(shè)備、刀具中選擇合適的配置搭建制造系統(tǒng)以完成生產(chǎn)。

液壓閥閥塊的加工特征已通過交鑰匙工程平臺(tái)中的特征提取功能模塊獲取,采用傳統(tǒng)機(jī)加工工藝,可以得到可行的加工特征劃分方案,如圖3所示。

圖3 液壓閥閥塊加工特征

可供選擇的設(shè)備、刀具的型號(hào)數(shù)量分別為30、50。設(shè)備和刀具供應(yīng)量是充足的。除案例涉及的各項(xiàng)數(shù)據(jù)及配置計(jì)算結(jié)果[14]外,各項(xiàng)全局參數(shù)的取值如表3所示。

表3 全局參數(shù)取值

4.2 配置結(jié)果比較

為驗(yàn)證本文所構(gòu)建的NSGA-NS的效果,開發(fā)了AMOSA、NSGA-Ⅲ、MOPSO、MOAPSO四種算法用于比較。其中,AMOSA的算法流程與文獻(xiàn)[11]中所述一致。MOAPSO是基于MOPSO改進(jìn)的一種優(yōu)化算法。

MOPSO的一個(gè)突出特點(diǎn)是收斂速度快的同時(shí)容易陷入局部最優(yōu)解,而模擬退火算法由于其基于溫度系統(tǒng)的劣解保留策略,能夠在一定程度上跳出局部最優(yōu)。因此考慮在粒子群優(yōu)化算法中引入溫度條件,根據(jù)溫度來調(diào)整速度更新的慣性權(quán)重,同時(shí)在個(gè)體最優(yōu)解的更新中以一定概率接受劣解,所形成的算法即為MOAPSO。

為便于比較,將不同算法相同性質(zhì)的參數(shù)設(shè)為一致:對(duì)每一次計(jì)算,保證初始種群/粒子群一致,鄰域解/子代數(shù)量均為100,總體最大迭代次數(shù)均為300,歷史最優(yōu)種群/解集持續(xù)未變化的最大迭代次數(shù)均為50。各算法參數(shù)設(shè)置如表4所示。

表4 算法參數(shù)設(shè)置

4.2.1 配置結(jié)果的評(píng)估指標(biāo)

除運(yùn)算時(shí)長(zhǎng)CT外,本文通過兩個(gè)指標(biāo)來對(duì)不同算法得到的帕累托前沿解的尋優(yōu)性、收斂性和多樣性進(jìn)行評(píng)估,以比較多目標(biāo)優(yōu)化算法的質(zhì)量。超體積HV[15-16]涵蓋了各算法的尋優(yōu)性、收斂性與多樣性特征,能夠較為全面的評(píng)價(jià)目標(biāo)算法的優(yōu)劣。DPO表示各算法最后一代前沿解未被其他算法的前沿解支配的比例,直觀地顯示了各算法的解之間的支配性,體現(xiàn)算法尋得的前沿解的質(zhì)量。

(12)

(13)

式中:Q表示所評(píng)估的算法得到的非支配解的集合,δ為勒貝格測(cè)度,vi為Q中的第i個(gè)帕累托解與參考點(diǎn)間構(gòu)成的超體積,參考WHILE等[17]提出的方法計(jì)算;|PS(Q)|表示Q中未被任意其他算法獲得的解支配的解的數(shù)量。計(jì)算超體積的參考點(diǎn)取所有算法得到的帕累托解在各優(yōu)化目標(biāo)上的極值。在計(jì)算之前,對(duì)所有帕累托解進(jìn)行規(guī)范化處理。

4.2.2 配置結(jié)果分析

算法程序采用Python3編寫,程序運(yùn)行環(huán)境為Windows 11,處理器為AMD Ryzen 75800H8-Core Processor 3.2 GHz,進(jìn)行4次計(jì)算。各優(yōu)化算法結(jié)果指標(biāo)如表5和圖4所示。

表5 不同算法比較

結(jié)合各算法運(yùn)算時(shí)長(zhǎng)以及超體積參數(shù),觀察與分析如下:

(1)就各算法的前沿解質(zhì)量而言,從各算法最后一代前沿解未被其他算法的前沿解支配的比例可以看出,NSGA-Ⅲ與NSGA-NS的前沿解質(zhì)量相對(duì)于其他3種算法有巨大優(yōu)勢(shì)。其中NSGA-NS相較于NSGA-Ⅲ有一定提升,MOAPSO相較MOPSO有微小的領(lǐng)先。

(2)就各算法計(jì)算速度而言,在保證各算法每次迭代生成的領(lǐng)域解/種群數(shù)量一致的前提下,NSGA-NS的速度最快,相較NSGA-Ⅲ速度提升接近一倍;其次是AMOSA、MOPSO與MOAPSO的計(jì)算速度相較于其他算法有大幅降低,MOAPSO略快于MOPSO。主要原因在于本文中開發(fā)的算法均未進(jìn)行并行計(jì)算,粒子群算法的多粒子并行搜索下對(duì)計(jì)算速度的提升是巨大的。

(3)通過超體積對(duì)算法收斂性進(jìn)行觀察,在收斂性方面,各算法均表現(xiàn)較好;在收斂迭代次數(shù)方面,MOAPSO表現(xiàn)最好,在40～50代內(nèi)達(dá)到收斂,相較MOPSO有一定提升;NSGA-NS收斂迭代次數(shù)相較NSGA-Ⅲ有明顯提升;AMOSA收斂迭代次數(shù)相對(duì)較差,在迭代末期仍保持緩慢上升趨勢(shì)。

(4)通過超體積對(duì)算法尋優(yōu)性能進(jìn)行觀察,NSGA-NS與NSGA-Ⅲ相較于其他3種算法有明顯優(yōu)勢(shì),其帕累托前沿明顯比AMOSA、MOPSO和MOAPSO更靠近全局最優(yōu)前沿。MOPSO在尋優(yōu)性能方面與AMOSA類似,MOAPSO相較MOPSO有較大提升。

通過以上配置結(jié)果可知,NSGA-NS與NSGA-Ⅲ在前沿解質(zhì)量上相對(duì)其他算法有顯著優(yōu)勢(shì),相較于NSGA-Ⅲ,NSGA-NS在大幅縮短運(yùn)行時(shí)長(zhǎng)的情況下,收斂速度略有提升,同時(shí)尋優(yōu)性能沒有劣勢(shì);MOAPSO相較MOPSO,在略微縮短運(yùn)行時(shí)長(zhǎng)的情況下,顯著提高了算法的尋優(yōu)性能,兩種混合相對(duì)于原算法均取得了比較好的效果。比較MOAPSO與NSGA-NS兩種算法,NSGA-NS在收斂速度略微低于MOAPSO的情況下,尋優(yōu)性能顯著強(qiáng)于MOAPSO。

5 結(jié)束語

本文針對(duì)RMS的SPFL快速配置問題,開展了配置模型構(gòu)建與求解方法的研究。成果總結(jié)如下:

(1)建立了一套用于可重構(gòu)系統(tǒng)快速配置的模型,綜合考慮了產(chǎn)品加工特征、工藝、設(shè)備和刀具等多個(gè)配置因素,以設(shè)備負(fù)載均衡度、產(chǎn)品生產(chǎn)成本和產(chǎn)品生產(chǎn)時(shí)間作為優(yōu)化目標(biāo),并應(yīng)用于一個(gè)液壓閥閥塊加工案例。

(2)開發(fā)了混合啟發(fā)式算法以求解上述模型:結(jié)合鄰域搜索對(duì)NSGA-Ⅲ進(jìn)行改進(jìn), 對(duì)交叉變異后的個(gè)體進(jìn)一步進(jìn)行鄰域搜索,構(gòu)建了NSGA-NS算法。

(3)對(duì)上述5種優(yōu)化算法進(jìn)行比較,結(jié)果表明,NSGA-NS和NSGA-Ⅲ在前沿解質(zhì)量上顯著優(yōu)于其他算法。在計(jì)算速度方面NSGA-NS最優(yōu),其次是AMOSA與NSGA-Ⅲ;MOPSO與MOAPSO的計(jì)算速度相較其他3種算法表現(xiàn)較差。MOAPSO在收斂迭代次數(shù)方面最優(yōu),但結(jié)合計(jì)算時(shí)間來看,收斂速度并不理想?？傮w而言,NSGA-NS解決了NSGA-Ⅲ收斂速度慢的問題,使得NSGA-NS既能夠保持NSGA-Ⅲ的全局尋優(yōu)性能,又能夠顯著提高其運(yùn)行效率,在5種算法中表現(xiàn)最佳。