馮潤暉,董紹華

(北京科技大學(xué) 機械工程學(xué)院,北京 100083)

0 引 言

在通常情況下,制造企業(yè)的生產(chǎn)過程可以分成加工和裝配兩個階段,再由多個加工車間和裝配車間組成一個多車間混合生產(chǎn)系統(tǒng)[1]。

在以往的研究中,將加工和裝配兩個階段獨立考慮,分別考慮每個車間的生產(chǎn)計劃和調(diào)度。首先加工車間加工零部件,然后將半成品進行倉儲,待所有配套零部件就緒后,再進行產(chǎn)成品的裝配[2]。由于生產(chǎn)計劃與調(diào)度的研究對象是單車間環(huán)境,只在車間內(nèi)部實現(xiàn)了制造資源合理配置,無法兼顧制造系統(tǒng)整體效益,導(dǎo)致了產(chǎn)品生產(chǎn)周期增長和零部件庫存費用增加等一系列問題,致使其生產(chǎn)效率較低。因此,對多個有關(guān)聯(lián)的車間進行統(tǒng)一集成優(yōu)化調(diào)度研究十分必要且意義重大,這是生產(chǎn)系統(tǒng)優(yōu)化的關(guān)鍵問題。

在協(xié)同制造環(huán)境下,2個或2個以上具有獨立生產(chǎn)能力的車間,組成了一個相互配合、目標一致的生產(chǎn)共同體,對其合理安排生產(chǎn),在滿足工藝約束的前提下,協(xié)同一致地達到目標函數(shù)最優(yōu)化的過程,稱為協(xié)同調(diào)度[3]。

現(xiàn)階段,國內(nèi)外學(xué)者們對協(xié)同調(diào)度問題的關(guān)注度較高。BHATNAGAR R等人[4]總結(jié)了協(xié)同調(diào)度問題的相關(guān)文獻,為集成的多車間協(xié)同調(diào)度生產(chǎn)計劃建立了數(shù)學(xué)模型,以最適合整個組織的方式,確定了所有工廠的生產(chǎn)決策。BEHNAMIAN J等人[5]將多車間協(xié)同調(diào)度的文獻,根據(jù)車間環(huán)境進行了整理分類,并對綜述文獻進行了對比,以確定有效的調(diào)度可以提高生產(chǎn)率。NADERI B等人[6]研究了最小化完工時間的分布式流水車間調(diào)度問題,設(shè)計了分散搜索算法,并對其進行了求解,結(jié)果表明,該算法比現(xiàn)有算法具有更好的效果。XU Ye等人[7]研究了分布式置換流水車間的調(diào)度問題,設(shè)計了混合免疫算法,并對其進行了求解,證明了該算法的有效性。NA H等人[8]研究了加工與裝配制造車間投產(chǎn)排序問題,并以總延遲時間最小為目標構(gòu)建了模型,以便在設(shè)定的日期之前完成零件。秦金濤[9]采用了多代理和規(guī)則引擎技術(shù),在制造執(zhí)行系統(tǒng)中構(gòu)建了調(diào)度協(xié)同平臺,實現(xiàn)了不同車間生產(chǎn)制造信息共享的目標,提高了制造企業(yè)各車間協(xié)同生產(chǎn)的效率。董義軍[10]建立了面向客戶可承諾(available to promise,ATP)的多工廠生產(chǎn)計劃調(diào)度數(shù)學(xué)混合規(guī)劃模型,設(shè)計了基于遺傳算法的多工廠協(xié)同生產(chǎn)計劃模型的求解算法。孫亞南等人[11]借鑒了面向?qū)ο蟮脑O(shè)計思想,以及基于模糊數(shù)學(xué)的最大隸屬度原則,提出了面向產(chǎn)能瓶頸單元的協(xié)同調(diào)度問題方法,解決了如何在有限資源的情況下,實現(xiàn)復(fù)雜制造系統(tǒng)最優(yōu)化調(diào)度的問題。于曉義等人[12]為求解多協(xié)作車間的計劃調(diào)度問題,提出了并行協(xié)同進化遺傳算法,以滿足多協(xié)作車間并行協(xié)同調(diào)度的要求。梁迪等人[13]提出了一種協(xié)同奔襲策略的狼群優(yōu)化算法,將改進后的狼群優(yōu)化算法應(yīng)用在雙車間協(xié)同調(diào)度問題上,并對此進行了驗證,證明了該算法具有明顯的優(yōu)勢。王艷等人[14]建立了以制造總成本與提前/延期為優(yōu)化目標的分布式多工廠調(diào)度模型,提出了一種融合決策樹的高斯粒子群嵌套尋優(yōu)算法框架,驗證了該算法在尋優(yōu)性、收斂性和CPU時間方面的優(yōu)越性。李修琳等人[15]運用了集成模擬退火算法的混合遺傳算法,求解了具有多品種混流生產(chǎn)特征和作業(yè)車間,及流水車間集成的混流混合車間協(xié)同調(diào)度問題。廖不凡等人[16]提出了一種混合教學(xué)優(yōu)化算法,以完工時間為目標,解決了多車間協(xié)作綜合調(diào)度問題,提高了各車間設(shè)備資源的利用率,并縮短了產(chǎn)品加工的總時間。

綜上所述,已有的對多車間協(xié)同調(diào)度的研究文獻中,場景大多限定在流水車間,以混合流水車間為原型進行研究的甚少。

混合流水車間一般定義為:流水線上有N個工件依次經(jīng)過M個階段的加工,其中每個階段至少存在一臺機器,并且至少有一個階段存在多臺機器可以進行加工。對同一工件的某個階段,工件可以選取任意一臺并行機來完成相應(yīng)工序,不同并行機處理時間可能存在差異?；旌狭魉囬g調(diào)度問題(hybrid flow shop scheduling problem,HFSP)是一般流水車間調(diào)度問題的擴展,不僅涉及到工件的排序,也涉及到并行機的分配,且該問題已經(jīng)被證明是典型的NP難組合優(yōu)化問題(non-deterministic polynomial problems,NP)。

因此,筆者對多混合流水車間的協(xié)同調(diào)度問題進行研究,以完成所有訂單加工和裝配的總時間為優(yōu)化目標,運用協(xié)同進化思想,采用并行協(xié)同進化遺傳算法對其進行求解,并以某液壓缸生產(chǎn)企業(yè)作為實驗對象,驗證所建模型和采用算法的實用性與有效性。

1 多車間協(xié)同調(diào)度問題建模

1.1 模型描述及假設(shè)

筆者研究的問題是以零件加工車間及產(chǎn)品裝配車間組成的兩階段生產(chǎn)系統(tǒng)為基礎(chǔ),根據(jù)生產(chǎn)數(shù)據(jù),建立模型。

s個相互協(xié)作的加工車間以及一個裝配車間共同完成n種訂單產(chǎn)品的生產(chǎn)裝配任務(wù):

加工車間集S={1…j…s};每個車間的生產(chǎn)階段集P={1…k…p};訂單產(chǎn)品集O={O1…Oi…On},每個產(chǎn)品由w個工件裝配而成,每種產(chǎn)品Oi的數(shù)量xi;每種產(chǎn)品包含的工件W={1…a…w};因此Oiajk,x代表第x個產(chǎn)品Oi的工件a在車間j加工工序k。

各車間加工的工件各不相同,車間j有Mj臺設(shè)備完成工件加工任務(wù),不同加工階段之間運送設(shè)備Vj完成工件運送任務(wù):

加工設(shè)備集為Mj={1…m…Mjall};運送設(shè)備集為Vj={1…v…Vjall},Mjk為車間j階段k的可選加工機器集。

為方便確定裝配關(guān)系,設(shè)置加工和搬運批量均為1,不同批次工件的工序之間沒有先后約束。必須在其子項工件加工完成后,裝配任務(wù)才可以開始進行,每道工序必須在其之前所有工序加工完成后才可開始,每臺加工設(shè)備同一時間只可同時加工一個工件。各工件的工序間是相互獨立的生產(chǎn)任務(wù)單元。

1.2 模型建立

相關(guān)參數(shù)設(shè)計如表1所示。

表1 模型參數(shù)

筆者研究的問題以最小化訂單完工時間為目標的單目標優(yōu)化問題，因此，其目標函數(shù)如下：

minf=max{FAikm,x}

(1)

式中：f—目標函數(shù)。

式(1)中，目標為最小化訂單完工時間，訂單完工時間即為裝配結(jié)束時間。

約束函數(shù)如下：

(1)加工車間約束

任一工件只能在一個車間內(nèi)進行加工，工序之間不可跨車間加工；

(2)

(2)工件加工時間約束

各工件在各工序的完工時間，為該工序開始加工時間與該工序被加工時間之和；

Fiajkm,x=Siajkm,x+Piajkm,xwhenXiajkm,x=1?i,j,a,k，x∈xi，m∈Mjk

(3)

各工序的開始加工時間，為其運輸?shù)皆撾A段的運輸完成時間與該階段加工機器所加工的前一工件的完工時間的較大值；

Siaj(k+1)m,x=max{Fi1aj(k+1)m,x1,FTiajk(k+1),x,v}

whenXiaj(k+1)m,x,Xi1aj(k+1)m,x1,Tiajk(k+1),x,v=1?i,i1,j,a,k,x∈xi,x1∈xi1,m∈Mj(k+1),v∈V

(4)

(3)工序加工順序約束

任一工件若想進入下階段進行加工，必須完成上階段的全部加工任務(wù)；

FTiajk(k+1),x,v+Piaj(k+1)m,x≤Fiaj(k+1)m,x

whenXiaj(k+1)m,x,Tiajk(k+1),x,v=1

?i,j,a,k，x∈xi，m∈Mj(k+1)，v∈V

(5)

(4)搬運設(shè)備運送時間約束

開始搬運時間為上一個工件的結(jié)束搬運時間與兩機器間的運輸時間之和；

STiajk(k+1),x,v=FTi2ajk(k+1),x2,v+MTm1,m2

whenXiajkm2,x,Xiaj(k+1)m1,x,Xi2aj(k+1)m1,x2=1,

Tiajk(k+1),x,v,Ti2ajk(k+1),,x2,v=1

?i,i2,j,a,k,x∈xi,x2∈xi2

m1∈Mj(k+1),m2∈Mjk,v∈V

(6)

搬運結(jié)束時間為工件的開始搬運時間與兩機器間的運輸時間之和；

FTiajk(k+1),x,v=STiajk(k+1),x,v+MTm1,m2

whenXiajkm2,x,Xiaj(k+1)m1,x,Tiajk(k+1),x,v=1

?i,j,a,k,x∈xi,m1∈Mj(k+1),m2∈Mjk,v∈V

(7)

(5)機器加工能力約束

在同一時刻，一個工件只能由一臺加工機器進行加工；

t∈[Siajkm,x,Fiajkm,x],m∈Mjk,?k,j,a

(8)

同一時刻，一臺機器只能加工一個工件；

t∈[Siajkm,x,Fiajkm,x],x∈{1,2,…,xi},?i,k,j,a

(9)

(6)運輸能力約束

同批工件同一時刻只能由一臺運輸工具進行運輸；

t∈[STiajkm,x,v,FTiajkm,x,v],?i,k,j,a,v,x∈xi

(10)

同一臺運輸工具同一時刻只能運輸同一批工件；

t∈[STiajkm,x,v,FTiajkm,x,v],?i,k,j,a,x∈xi

(11)

(7)加工時間約束

所有階段的加工時間為正數(shù)：

Piajkm,x≥0,x∈{1,2,…,xi},m∈Mjk,?i,k,j,a

(12)

所有工序在0時刻均可被加工，即：

Siajkm,x≥0,x∈{1,2,…,xi},m∈Mjk,?i,k,j,a

(13)

2 多車間協(xié)同調(diào)度問題求解

2.1 算法流程

針對上述調(diào)度模型,筆者提出了一種多車間協(xié)同調(diào)度的并行協(xié)同進化遺傳算法(PCE-GA),并采用該算法對上述模型進行求解。

其算法流程如圖1所示。

圖1 并行協(xié)同進化遺傳算法流程圖

圖1中的算法流程表明,種群與種群之間存在協(xié)作關(guān)系,所有種群合并形成一個完整解,種群內(nèi)有競爭,種群間有協(xié)作,各個種群的進化過程并不是相互獨立的,而是協(xié)同進化,更加符合自然界進化的規(guī)律。

2.2 并行協(xié)同進化遺傳算法

2.2.1 染色體編碼

為了同時描述工件的加工順序、加工機器和裝配關(guān)系3種信息,個體的染色體編碼采用三層整數(shù)編碼方式,每一個三層編碼對應(yīng)一個調(diào)度方案,種群初始化采用按工序隨機生成原則,終止準則為預(yù)先設(shè)定的最大迭代次數(shù)。

編碼第一層為基于工件的編碼,工件號出現(xiàn)的次數(shù)代表該工件的工序數(shù);第二層為基于機器的編碼,代表該工序選擇的加工機器的編號;第三層為基于裝配的匹配關(guān)系的編碼,不同種群中裝配碼相同代表具有裝配關(guān)系。

染色體的編碼方式如圖2所示。

圖2 編碼方式

由圖2可知:種群1中某條染色體編碼為[1,2,1,3,2,1,3,3,2,1,2,3,1,4,5,3,6,5,1,2,1,3,2,1,3,3,2];其中,前三分之一[1,2,1,3,2,1,3,3,2]為工件碼,代表工序{O11,O21,O12,O31,O22,O13,O32,O33,O23};其中,Oij代表第i個工件的第j道工序,機器碼為中間三分之一部分[1,2,3,1,4,5,3,6,5],代表工件某工序選擇的機器號,即工序O11選擇機器1,工序O21選擇機器2,裝配碼為最后三分之一部分,如圖2箭頭所示,種群1的工件1與種群2的工件3具有相同裝配碼,因此,具有裝配關(guān)系,同理種群1的工件2和種群2的工件2、種群1的工件3和種群2的工件1具有裝配關(guān)系。

2.2.2 協(xié)同適應(yīng)度值計算

采用PCE-GA算法計算個體適應(yīng)度值時,需要計算兩次適應(yīng)度值。

協(xié)同適應(yīng)度值計算流程如圖3所示。

圖3 協(xié)同適應(yīng)度值計算流程

首先,筆者分別單獨計算每個種群中每條染色體的適應(yīng)度值,即每條染色體對應(yīng)的調(diào)度方案的加工完工時間,作為該個體的臨時適應(yīng)度值;然后計算協(xié)同適應(yīng)度值,方法為對于任一種群中的每一條染色體,與其他每個種群中的一條染色體合并作為一個完整解,根據(jù)物料清單(bill of material,BOM)表中的零件裝配關(guān)系,計算該完整解的裝配完工時間,作為該條染色體的協(xié)同適應(yīng)度值。

2.2.3 選擇交叉變異操作

為了將最優(yōu)個體保留,筆者采用精英保留策略,將每一代中最好的個體保留至下一代,不進行交叉變異操作。選擇操作采用錦標賽選擇策略,每次從種群中取2個個體(放回抽樣),選擇其中完工時間較小的個體進入子代種群。重復(fù)該操作直到種群規(guī)模和原來的種群規(guī)模一樣。

交叉操作采用工件層的單點交叉法,父代在工件碼中隨機選擇交叉點,在交叉點前的基因互換,之后比較父子代染色體,將子代中多余的工件號替換成缺失的工件號,以此保證子代染色體為可行的調(diào)度方案,保證子代每道工序所分配的機器與父代一致,最后裝配碼則根據(jù)交叉完的工件碼重新生成。

個體交叉示意圖如圖4所示。

圖4 個體交叉示意圖

圖4中,父代交叉點為第4個基因,交叉完成后子代保留父代的機器基因。

變異操作主要針對機器碼,隨機選取多個變異點,將機器變?yōu)樵摴ば驒C器可選集中的其他機器。

3 實驗及結(jié)果分析

為了驗證PCE-GA算法的優(yōu)越性,筆者以某液壓缸制造企業(yè)為實驗對象,對多車間協(xié)同調(diào)度算法進行研究。液壓缸的加工零部件包含外罩、外缸、缸筒和末級。

各個車間之間的協(xié)作關(guān)系如圖5所示。

圖5 液壓缸生產(chǎn)車間協(xié)作關(guān)系

圖5中,液壓缸的各個零部件在不同的車間分別進行加工,加工完成后的各個零部件和外購的零件集中在一起進行裝配,得到液壓缸產(chǎn)品。該企業(yè)的每個生產(chǎn)車間可被抽象為混合流水車間。

外缸加工車間的設(shè)備如表2所示。

不同車間的加工機器不同,根據(jù)表2可知:該車間共有26臺加工設(shè)備,8個加工階段,每個階段都包含并行機。

表2 外缸加工車間設(shè)備表

現(xiàn)對4個訂單19件產(chǎn)品進行排產(chǎn),產(chǎn)品信息及裝配關(guān)系如圖6所示。

圖6 產(chǎn)品信息及裝配關(guān)系圓圈代表裝配件,方框代表加工零部件,括號內(nèi)是訂單數(shù)量。

因為模型假設(shè)中定義的加工批量為1,因此,每個產(chǎn)品都有不同的裝配碼,對19個產(chǎn)品編號為1～19,每個零件與所屬產(chǎn)品具有相同的裝配碼編號。不同訂單的相同零件因具有不同的裝配碼編號,因此,是分開依次進行排產(chǎn)的,且不同訂單的優(yōu)先級相同,所有訂單按BOM表分解后有76個零件加工生產(chǎn)任務(wù),19個組合件裝配生產(chǎn)任務(wù)。

為了驗證上述模型與求解方法的實用性和有效性,筆者設(shè)置2組實驗。

其中,遺傳算法的參數(shù)為:種群數(shù)量為500,交叉概率為0.8,變異概率為0.1,迭代次數(shù)為20。用QT 4.11.1進行編程,算法運行環(huán)境為Intel(R) Core(TM) i7-8565U CPU @ 1.80 GHz 1.99 GHz,16.0 GB運行內(nèi)存,Window10 64位操作系統(tǒng)。

3.1 實驗一

接下來，筆者進行并行協(xié)同進化遺傳算法(PCE-GA)的求解。

通過運用上述PCE-GA算法,在調(diào)度起始時間t=0、設(shè)備初始能力充足的情況下,對該企業(yè)的上述實際訂單進行運算。

進化過程中每一代的最優(yōu)解如圖7所示。

圖7 協(xié)同進化收斂曲線

由圖7可知:在20次迭代過程中,最優(yōu)解的值不斷下降,在第17代趨于平穩(wěn)地收斂到最終的優(yōu)化解。其中,最大值為517 min,最小值為448 min,優(yōu)化率13.3%。

最優(yōu)解調(diào)度方案對應(yīng)的訂單中,產(chǎn)品的各個部件完工時刻以及裝配完工時刻,如表3所示。

表3 完工時刻表

由表3可以看出:外缸為瓶頸部件,因為0時刻為該組訂單的開始加工時刻,因此,該組訂單的最終完工時間為448-0=448 min。

3.2 實驗二

接下來，筆者進行3種算法求解效果的對比。

為了進一步體現(xiàn)算法的優(yōu)勢,筆者將PCE-GA算法與單車間作業(yè)調(diào)度遺傳算法(JSP-GA)及并行協(xié)同進化模擬退火算法(PCE-SA)進行比較。

單車間作業(yè)調(diào)度即分別對每個車間單獨進行優(yōu)化,將最晚完工的車間結(jié)束時間作為裝配的起始時間,對裝配車間進行優(yōu)化,得到最終的完整解,即訂單完工時間。

PCE-SA算法也采用并行協(xié)同進化思想進行求解(模擬退火算法的參數(shù)設(shè)置為:初始溫度為500,停止迭代溫度為0.1,降溫速度為0.75,在每個溫度下設(shè)置內(nèi)部蒙特卡洛循環(huán)迭代次數(shù)為10)。

3種算法求解結(jié)果如表4所示。

表4 3種算法的求解結(jié)果

由表4可知:對于單個車間,JSP-GA算法求解的每個車間的調(diào)度方案完工時間,都比PCE-GA算法和PCE-SA算法求解的完工時間要短,但應(yīng)用并行協(xié)同進化算法求解的訂單完工時間卻要比單車間調(diào)度算法求解的訂單完工時間短,即在整體層面上,PCE-GA算法產(chǎn)生的調(diào)度方案,其構(gòu)成完整解的質(zhì)量比單車間遺傳算法產(chǎn)生的解優(yōu)越,優(yōu)化率為11.5%。

單車間遺傳算法僅實現(xiàn)了車間局部的優(yōu)化,未能實現(xiàn)企業(yè)整體最優(yōu)。雖然PCE-SA算法的訂單完工時間比PCE-GA算法的結(jié)果要長,但仍比JSP-GA算法求解結(jié)果略好,再次證明了PCE-GA算法的優(yōu)越性。

4 結(jié)束語

傳統(tǒng)企業(yè)在實際生產(chǎn)中,其多個關(guān)聯(lián)車間之間的生產(chǎn)計劃與調(diào)度存在難以協(xié)作的問題。為此,針對該多混合流水車間的協(xié)同調(diào)度問題,筆者以完成所有訂單加工和裝配的總時間為優(yōu)化目標,運用協(xié)同進化思想,采用并行協(xié)同進化遺傳算法對其進行了求解,并以某液壓缸生產(chǎn)企業(yè)作為實驗對象,驗證所建模型和采用算法的實用性與有效性。

研究結(jié)論如下:

(1)在實驗一中,采用PCE-GA算法求解得到的優(yōu)化率為13.3%,說明該算法在解決該類復(fù)雜組合優(yōu)化問題時是有效的;

(2)采用PCE-GA算法比JSP-GA算法求解的數(shù)據(jù)優(yōu)化了11.5%,該結(jié)果表明,運用協(xié)同進化思想能夠有效地協(xié)調(diào)各協(xié)作車間的生產(chǎn)活動,可以明顯提高企業(yè)的整體生產(chǎn)效率。

在目前的研究中,筆者所采用的優(yōu)化目標為訂單完工時間。在后續(xù)的研究過程中,筆者將會增加研究目標,例如搬運時間等,并且在此基礎(chǔ)上,針對不同訂單交貨期設(shè)置優(yōu)先級。