基于并行協同的多車間協同調度問題研究*

馮潤暉,董紹華

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

0 引 言

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

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

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

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

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

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

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

1 多車間協同調度問題建模

1.1 模型描述及假設

筆者研究的問題是以零件加工車間及產品裝配車間組成的兩階段生產系統為基礎,根據生產數據,建立模型。

s個相互協作的加工車間以及一個裝配車間共同完成n種訂單產品的生產裝配任務:

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

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

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

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

1.2 模型建立

相關參數設計如表1所示。

表1 模型參數

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

minf=max{FAikm,x}

(1)

式中：f—目標函數。

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

約束函數如下：

(1)加工車間約束

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

(2)

(2)工件加工時間約束

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

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

(3)

各工序的開始加工時間，為其運輸到該階段的運輸完成時間與該階段加工機器所加工的前一工件的完工時間的較大值；

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)工序加工順序約束

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

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)搬運設備運送時間約束

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

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)

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

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)加工時間約束

所有階段的加工時間為正數：

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 多車間協同調度問題求解

2.1 算法流程

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

其算法流程如圖1所示。

圖1 并行協同進化遺傳算法流程圖

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

2.2 并行協同進化遺傳算法

2.2.1 染色體編碼

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

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

染色體的編碼方式如圖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具有相同裝配碼,因此,具有裝配關系,同理種群1的工件2和種群2的工件2、種群1的工件3和種群2的工件1具有裝配關系。

2.2.2 協同適應度值計算

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

協同適應度值計算流程如圖3所示。

圖3 協同適應度值計算流程

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

2.2.3 選擇交叉變異操作

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

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

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

圖4 個體交叉示意圖

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

變異操作主要針對機器碼,隨機選取多個變異點,將機器變為該工序機器可選集中的其他機器。

3 實驗及結果分析

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

各個車間之間的協作關系如圖5所示。

圖5 液壓缸生產車間協作關系

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

外缸加工車間的設備如表2所示。

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

表2 外缸加工車間設備表

現對4個訂單19件產品進行排產,產品信息及裝配關系如圖6所示。

圖6 產品信息及裝配關系圓圈代表裝配件,方框代表加工零部件,括號內是訂單數量。

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

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

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

3.1 實驗一

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

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

進化過程中每一代的最優解如圖7所示。

圖7 協同進化收斂曲線

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

最優解調度方案對應的訂單中,產品的各個部件完工時刻以及裝配完工時刻,如表3所示。

表3 完工時刻表

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

3.2 實驗二

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

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

單車間作業調度即分別對每個車間單獨進行優化,將最晚完工的車間結束時間作為裝配的起始時間,對裝配車間進行優化,得到最終的完整解,即訂單完工時間。

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

3種算法求解結果如表4所示。

表4 3種算法的求解結果

由表4可知:對于單個車間,JSP-GA算法求解的每個車間的調度方案完工時間,都比PCE-GA算法和PCE-SA算法求解的完工時間要短,但應用并行協同進化算法求解的訂單完工時間卻要比單車間調度算法求解的訂單完工時間短,即在整體層面上,PCE-GA算法產生的調度方案,其構成完整解的質量比單車間遺傳算法產生的解優越,優化率為11.5%。

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

4 結束語

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

研究結論如下:

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

(2)采用PCE-GA算法比JSP-GA算法求解的數據優化了11.5%,該結果表明,運用協同進化思想能夠有效地協調各協作車間的生產活動,可以明顯提高企業的整體生產效率。

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