基于改進量子遺傳算法的重型裝備生產調度研究*

張 琪,楊曉英

(河南科技大學 機電工程學院,河南 洛陽 471003)

0 引 言

重型裝備是典型的單件離散型產品,部件關聯性強,加工與裝配具有很強的并行性。傳統的機械作業車間調度(job-shop scheduling problem,JSSP)通常把零件加工與產品裝配分開,主要針對純加工或純裝配調度進行研究,難以應對產品內在加工與裝配的并行處理關系。綜合作業調度(CJSSP)是具有實際應用背景的生產調度問題,充分考慮產品加工與裝配的并行性,將分階段調度模型轉化為產品制造鏈調度[1]。因此,對重型裝備綜合作業調度問題進行深入研究具有重要意義。

CJSSP研究對象主要為大型復雜產品,其生產調度要遵循嚴格的裝配順序約束,一般以單個產品最小生產周期為優化目標[2-4]。多產品綜合作業調度方面,梁艷杰等[5]的研究以多個產品總完工時間最小為優化目標,未能體現不同產品對交貨期需求的差異性。謝志強等[6]按產品交貨期設置優先級,按優先級順序完成多產品綜合作業調度,該方法可高效求解小規模調度問題,但在大規模調度問題中難以取得最優解。

截止目前,智能算法在JSSP研究上已趨于成熟,但是關于CJSSP的研究尚有不足,由于CJSSP對產品工藝結構依賴過高,智能算法研究重點集中于編碼設計方面。趙詩奎等[7]設計出了一種分區編碼方式,雖能有效求解CJSSP問題,但減少了初始種群的多樣性。石飛等[8]為避免分區編碼方式遺漏解空間問題,采用了鄰接矩陣修復方法,確保了初始解空間的完整性。王福吉等[9]設計了基于可行域搜索的遺傳算法,在可行域內進行了交叉、變異操作,但縮小了搜索范圍,不利于搜索全局最優解。智能算法在CJSSP問題應用上多采用遺傳算法[10-12]。SEIDGAR H等[13]采用帝國競爭算法對裝配作業車間進行了研究。蔣南云等[14]設計混合智能算法對可重入綜合作業調度進行了研究,建立了雙層作業計劃。

上述學者雖對CJSSP問題有一定研究,但在多產品綜合作業調度方面的研究仍有不足,難以實現對各個產品的高效調度;智能算法研究在編碼設計上難以保證解空間的完整性,有時設計過于繁瑣,對CJSSP問題的應用研究尚有欠缺。

針對上述存在的問題,本文以某重型裝備為研究對象,針對不同交貨期下的多產品綜合作業調度問題,以加工成本、精準交付、跨車間轉運次數為優化目標,建立多產品綜合作業調度優化模型,設計改進量子遺傳算法對模型求解;同時設計基于裝配約束的編碼方式,使染色體滿足裝配約束關系,最終確定各工序最佳執行時間,以提高重型裝備生產調度的精益性指標。

1 重型裝備生產調度問題分析

通常，重型裝備是定制化生產的大型產品,由機械工廠(車間)按訂單組織生產,由物料經非連續移動加工裝配而成,生產設備以通用型為主,跨車間生產[15]。由于生產環境復雜多變,零件跨車間生產容易造成生產混亂,應盡量減少零件跨車間的轉運次數。重型裝備各部件關聯性強,一般將產品分解為部件,根據訂單交貨期設定各部件排產優先級,按優先級從高到低進行排產,生成可行的作業計劃。

精益生產強調“消除浪費,降低成本”的理念,上述排產方式只考慮交貨期單一指標,且這種方式生成的作業計劃很難確保訂單精準交付。訂單提前完工會產生庫存,造成浪費;拖期完工又會給企業帶來額外費用,影響客戶滿意度,難以實現生產調度精益性目標。

重型裝備通常在多訂單并行條件下組織生產,由于設備資源有限,產品對設備資源的不良占用會影響到其他產品的生產進度,導致訂單不能按期交付,直接影響企業核心競爭力。多產品綜合作業調度不同于單個產品綜合作業調度,不能以產品完工時間最短為優化目標,需要合理安排各個產品每道工序的最佳執行時間,實現訂單精準交付,對求解精度要求更高。重型裝備生產調度要合理安排每個車間加工任務,使每個產品訂單都能精準交付且成本最低。

2 多產品綜合作業調度優化模型

2.1 模型假設

n個產品需要在多個車間加工裝配,每個產品由o個工件組成,每個工件有q道工序,每道工序根據其工藝特點可在不同車間的設備上加工,工件的加工順序嚴格按照工藝約束。

要求工件各工序對應合適的機床,確定最優調度方案,在生產中滿足以下假設:

(1)工件的每道工序只能在一臺設備上加工;

(2)在工件的緊前工件加工完成后才可開始加工;

(3)一臺設備同時只能加工一道工序;

(4)加工過程中設備沒有故障發生;

(5)零件的轉運時間忽略不計。

2.2 相關符號定義

相關符號及定義如表1所示。

表1 符號定義

2.3 優化模型

綜合考慮產品內部加工裝配約束關系,筆者以加工成本、精準交付、跨車間轉運次數為優化目標,建立多產品綜合作業調度優化模型。

目標函數表示為:

f=λ1f1+λ2f2+λ3f3

(1)

式中:λi—目標函數加權系數;fi—第i個目標函數。

(1)加工成本。重型裝備生產要考慮生產成本,以成本最低為目標,最小加工成本表示為:

(2)

(2)精準交付。產品訂單應滿足交貨期要求,提前或拖期完工都會給企業帶來損失。設置提前/拖期懲罰函數,若產品訂單實際完工時間與交貨期出現偏差會產生懲罰值,通過減小懲罰值實現產品精準交付,提前/拖期懲罰函數表示為:

(3)

(3)跨車間轉運次數。重型裝備生產過程復雜多變,應盡量減少零件跨車間轉運次數,避免造成生產混亂,最小跨車間轉運次數表示為:

(4)

為使多產品綜合作業調度優化模型有效求解,設置約束條件如下:

(5)

Sik1j≥Civ(v∈Bik)

(6)

(7)

(Sikrj,Cikrj)∩(Sxyzj,Cxyzj)=φ

(8)

式(5)限制了工件i的每道工序,要求其只能在一臺設備上加工;

式(6)限制了工件i第一道工序的開工時間,要求其不小于工件i緊前工件集的完工時間;

式(7)限制了工件的后道工序開始時間,要求其不早于前道工序的完工時間;

式(8)限制了每臺設備,要求其同時只能加工一個工件。

3 改進量子遺傳算法

量子遺傳算法(QGA)在遺傳算法(GA)的基礎上融入量子計算,量子位編碼方式增加了解空間的多樣性。但是種群通過量子旋轉門向最優個體逼近時,若沒有更好的解出現,易陷入局部最優。模擬退火算法(SA)有很好的局部優化效果,以一定概率接受劣解。

改進量子遺傳算法(SQGA)將SA與QGA結合,在種群迭代時易跳出局部最優,提高了算法全局搜索能力。同時,設計基于裝配約束的編碼方式和自適應旋轉角,使其可以更平穩求解綜合作業調度問題。

3.1 編碼設計

CJSSP問題編碼的關鍵是保證染色體在解碼時滿足裝配約束,避免不可行解產生。本文設計基于裝配約束的工序-設備-父節點3層編碼方式,確保解碼時染色體的可行性和解空間的完整性。

一條量子位編碼染色體表示如下:

工序編碼中,將十進制數值從小到大依次排列,將原位置索引值填入排列后的位置即得到工序編碼。設工序i轉化后對應的十進制數值為yi,可選設備的數量為wi,則工序i的設備編碼為mod(yi,wi)+1。父節點編碼為每道工序對應所屬工件的緊后工件編號,根節點的父節點編碼記為0。

設某產品由3個工件組成,每個工件1道工序,工序可選設備數均為2,在2臺設備上加工。

產品結構如圖1所示。

圖1 產品結構

假設基于該產品設計的某條染色體在進行量子位測定時,量子位編碼根據概率幅轉換為二進制串101101,以此為例:

解碼時,首先通過三層編碼結構轉換確保染色體的可行性,使其滿足產品內部裝配順序約束。

具體操作如圖2所示。

圖2 三層編碼轉換操作

圖2中,對工序編碼從左至右進行遍歷,若在第三層父節點編碼中含有該工序對應編碼信息則跳過,否則刪除該工序編碼對應索引位置的三層編碼信息,并將刪除的三層編碼信息重新依次記錄在新集合中。重復以上操作直至三層編碼為空,即可得到符合裝配約束的新染色體。

由于染色體轉換前的編碼是隨機的,通過三層編碼結構轉換為滿足裝配約束染色體的解空間是完整的。根據新染色體序列從左至右進行解碼,即可得到符合裝配約束的各工序執行時間。

3.2 量子位更新策略

QGA中采用量子旋轉門作用于染色體,通過改變量子位編碼的概率幅更新染色體,實現種群進化,其更新如下:

(9)

式中:U—量子旋轉門;θ—量子旋轉角。

θ值影響種群收斂速度,太大會導致早熟,反之導致收斂過慢。θ取值一般為0.01π～0.05π,為使種群收斂速度更平緩,本文設計自適應調整θ為:

(10)

式中:fitnessn—個體n的適應度值;fmin—種群中最小適應度值,也是文中最佳個體適應度值;fmax—種群中最大適應度值;Δθ—0.05π。

與最佳個體適應度值越接近的個體,說明其性能優良,采用較小的θ值,降低收斂速度;反之,采用較大θ值。

3.3 模擬退火策略

量子位更新結束后,筆者取適應度值較好的前20%個體進行退火操作,以加快收斂速度;采用Pauli-X門互換αi和βi的概率幅,從而改變量子位測量值,完成鄰域搜索。

設每個量子位進行Pauli-X門轉換的概率為0.1,轉換過程如下:

(11)

式中:X—Pauli-X門。

將鄰域搜索后的最佳個體與之前最佳個體進行對比,按照Metropolis準則確定新個體接受概率,即:

(12)

式中:P—新個體接受概率;f(a)—鄰域搜索前最佳個體適應度值;f(b)—鄰域搜索后最佳個體適應度值;T—退火溫度,T=D×T0;D—溫度衰減參數;T0—初始溫度。

3.4 適應度函數

模型求解過程中,依據適應度函數去評定個體的好壞,適應度函數一般由目標函數進行尺度變換演變生成。由于目標函數式(1)是由3個目標加權組合而成,單位不統一,在加權組合前要進行標準化處理,化為無量綱形式,適應度函數式為:

(13)

(14)

3.5 算法流程

改進量子遺傳算法(SQGA)將量子遺傳算法(QGA)與模擬退火算法(SA)結合,具體算法流程如下:

Step1初始化量子位編碼,產生隨機初始種群Q0;

Step2將Q0進行測定、轉化,得到種群S0;

Step4進行適應度計算,保留最佳個體Pb;

Step5量子門旋轉,得到新的種群S;

Step6將S經染色體轉換,進行適應度計算,保留新的最佳個體Pb;

Step8判斷是否滿足終止條件,如果滿足轉向Step9,否則種群迭代次數加1,轉向Step5;

Step9算法搜索結束,輸出最優解。

改進量子遺傳算法的算法流程圖如圖3所示。

圖3 算法流程圖

4 實驗仿真與分析

筆者采用MATLAB R2014a進行實驗。算法參數設置如下:種群規模100,迭代次數200,GA交叉概率Pc=0.85,變異概率Pm=0.2,QGA固定旋轉角,SQGA溫度衰減參數D=0.95,初始溫度T0=100,終止溫度Tmin=1。

實例驗證首先對標準算例仿真,驗證SQGA算法性能,再將算法應用到重型機械企業的生產實例中。

4.1 算例測試

目前,對CJSSP基準測試問題研究較少,為驗證改進量子遺傳算法的有效性,筆者采用文獻[11]中的10個算例測試,以makespan為優化目標,使產品完工時間最短。

產品結構如圖4所示。

圖4 算例產品結構

筆者采用GA、QGA、AQGA、SQGA算法進行實驗且都采用本文設計的基于裝配約束的編碼方式,其中,AQGA在QGA的基礎上加入自適應旋轉角,算法其余部分相同。

每個算例仿真實驗次數為10次,以最優解(Optimal)、最優解占比(Ratio)、平均收斂代數(Gen)為衡量指標。

具體數據如表2所示。

由表2可知:

表2 不同算法數據對比

(1)Optimal指標上,SQGA效果最好,求解精度最高,10個算例均能取得最優解;QGA和AQGA尋優效果接近,僅在Orb3C算例沒能收斂至最優;GA尋優效果最差,但大部分算例也能收斂至最優。可知本文設計基于裝配約束的編碼方式在CJSSP問題上具有非常好的效果;

(2)Ratio指標上,SQGA在Orb3C、Orb4C、Orb6C 3個算例上分別為0.8、0.9、0.8,其余算例為1,均優于GA、QGA、AQGA,說明SQGA求解過程平穩,該算法有較好的穩定性;

(3)Gen指標上,SQGA僅在Orb3C算例沒取得最小值,但尋優效果均優于其余3種算法。整體上,SQGA算法收斂速度最快。此外,AQGA僅在Orb2C和Orb3C兩個算例上的平均收斂代數大于QGA;在Orb3C算例上,AQGA尋優效果優于QGA,說明QGA采用自適應旋轉角可以提高收斂速度。

綜合以上3項指標,可見4種算法中性能最好的為SQGA,其次為AQGA、QGA、GA;綜合10個算例,SQGA相比QGA,平均收斂代數減少18.6%,平均最優解占例增加26%,SGQA具有更好的收斂效果和求解精度。

筆者以Ft10C為例進行說明,其最優結果甘特圖如圖5所示。

圖5 Ft10C甘特圖數字—工件號;橫坐標—加工時間;縱坐標—機器號

由圖5可知:4種算法均能取得Ft10C,其中算例最優完工時間1 985。

算法最優收斂曲線如圖6所示。

圖6 Ft10C不同算法收斂曲線

由圖6可知:SQGA算法在11代收斂至最優,GA、QGA、AQGA分別在25、20、16代收斂至最優;由此可見,SQGA收斂效果最好,驗證了改進機理的合理性和有效性。

4.2 實例驗證

4.2.1 實例數據

現有Φ7×3.5 m半自磨機1臺,Φ5.5×1.8 m半自磨機2臺,以二班制方式生產,每班8 h,交貨期分別為25 d和35 d。

半自磨機產品結構如圖7所示。

圖7 半自磨產品結構

半自磨機由主軸承、筒體、大齒輪3大零部件構成,產品拖期一天扣除合同金額千分之一,拖期懲罰系數FC1取450,FC2、FC3取350;產品提前完工會占用庫存、設備資源。經綜合考慮,筆者設置提前懲罰系數ECi為200。

實例中設備信息如表3所示。

表3 設備信息

由表3可知:M1～M6屬于數一車間,M7～M11屬于數二車間,M12～M14屬于粗加車間,半自磨機在數一、數二、粗加3個車間進行生產。

工序可選擇機床和加工時間如表4所示。

表4 工序信息

4.2.2 實例仿真

實例仿真以式(13)為適應度函數,根據目標重要程度設置權重λ1=0.4,λ2=0.4,λ3=0.2,以保證相應指標達到最優,采用SQGA算法對多產品綜合調度模型進行求解。

半自磨機排產調度甘特圖如圖8所示。

圖8 半自磨機排產調度甘特圖

圖8中,A代表7 m×3.5 m半自磨機,B和C代表5.5 m×1.8 m半自磨機,字母后的數字代表工件,如:A2表示7 m×3.5 m半自磨機的第2個部件主軸承。

SQGA算法的收斂曲線如圖9所示。

圖9 SQGA收斂曲線

4.2.3 效果分析

目前,該企業采用APS制定作業計劃,將產品分解為部件,每個部件根據交貨期緊迫度設定排產優先級,按照排產優先級進行排產。即當某個部件排產完成后,才開始為優先級低的部件排產,這樣使得解空間縮小,很難排出較好的調度結果。采用綜合調度對產品進行排產,可以將產品分階段調度變為產品鏈調度,有效縮短產品生產周期。

筆者將SQGA+綜合作業調度與企業采用的APS+部件優先級調度進行對比,結果如表5所示。

表5 數據對比

由表5可見:SQGA+綜合調度方法使加工成本減少了7.8%,跨車間轉運次數減少了30.4%,產品達到精準交付,提高了機械工廠(車間)的生產調度精益性指標。

5 結束語

針對重型裝備加工與裝配集成調度精益性不足的問題,綜合考慮加工成本、精準交付、跨車間轉運次數等目標,筆者建立了多產品綜合作業調度優化模型;為使模型得到有效求解,筆者設計了改進量子遺傳算法;針對量子遺傳算法易陷入局部最優的缺點,將其與模擬退火算法相結合,提高了算法的搜索精度;在編碼方式上設計了一種基于裝配約束的工序-設備-父節點三層編碼結構,使染色體在解碼時,既能夠滿足裝配約束關系,又能夠滿足解空間的完整性;最后,通過算例和生產實例對算法和模型的效果進行了驗證。

研究結果表明:與傳統量子遺傳算法相比,改進量子遺傳算法具有更好的尋優效果,收斂速度和求解精度更優,可高效求解綜合作業調度問題。此外,該模型和算法可以提高重型裝備精益化生產調度指標,為重型裝備精益化生產提供理論依據。

在接下來的研究中,筆者將以魯棒性為目標,對多產品綜合作業調度進行研究,以應對重型裝備生產過程中的突發情況對調度計劃帶來的不良影響。