一種汽車混流總裝生產(chǎn)線排產(chǎn)的超啟發(fā)式算法研究

盧梓揚，盛步云，王 輝，李曉芳

(1.武漢理工大學 機電工程學院,湖北 武漢 430070;2.湖北省數(shù)字制造重點實驗室，湖北 武漢 430070;3.湖北航天技術研究院 計量測試技術研究所,湖北 孝感 432000)

隨著汽車制造行業(yè)大規(guī)模定制化的演進，混合產(chǎn)品合理高效的產(chǎn)出排序能為車企削減成本。因此混合總裝線排產(chǎn)是汽車企業(yè)制定生產(chǎn)計劃的基礎和關鍵點，它的優(yōu)劣對整個汽車制造企業(yè)的生產(chǎn)周轉有很大的影響[1-2]。在比較不同時間周期(月、季、年)、不同批次的生產(chǎn)數(shù)據(jù)(主要是工序完工時間等工時數(shù)據(jù))后發(fā)現(xiàn)混流總裝生產(chǎn)系統(tǒng)本身具有一致性、穩(wěn)定性，而以往的研究大多聚焦在算法的性能上，沒有對生產(chǎn)系統(tǒng)信息進行記憶學習，這樣在處理不同的批次訂單時，往往就是在解決一個全新的問題，造成了生產(chǎn)系統(tǒng)信息資源的浪費。因此筆者設計了一種以Q-learning強化學習為上層策略，GA(genetic algorithm)、DE(differential evolution)為LLH(low-level heuristics)(底層算法庫)的超啟發(fā)式算法，旨在結合不同算法優(yōu)點，高效解決同一生產(chǎn)系統(tǒng)下的混流總裝排產(chǎn)問題。

1 總裝車間混流總裝線模型分析

汽車混流總裝線如圖1所示，其排序問題通?？梢悦枋鰹椋河衝輛汽車(T1，T2，…,Tm，…,Tn)需要在流水線上進行生產(chǎn)裝配，在生產(chǎn)工藝流程確定的情況下，通過改變車輛的生產(chǎn)順序，使得整個生產(chǎn)過程的目標最優(yōu)化[3]。假設條件如下：①將分裝線體產(chǎn)生的組件作為物料考慮，生產(chǎn)按一個流進行生產(chǎn)，傳送帶以速度vc運動，節(jié)拍為tc；②總裝車間每個生產(chǎn)工位對于既定車型的生產(chǎn)時間為已知，不考慮設備損壞、人員休息等隨機約束；③無限能力排產(chǎn)；④不允許過載操作，即操作工人在自己的工作域內(nèi)不能完成作業(yè)任務就必須停線,直至完成后重新啟動傳送帶[4]。

優(yōu)化目標為：①車型切換調(diào)整費用最小化；②裝配線空閑/停線時間最小化；③物料消耗均衡化[3,5]。

圖1 混流總裝線示意圖

1.1 符號定義

混流總裝車間調(diào)度問題模型中涉及的符號及定義如表1所示。

表1 符號定義表

1.2 目標函數(shù)

(1)車型切換裝配線調(diào)整時間最小化目標f1。當?shù)趍位次車輛與第m-1位次車輛在Wn工位的工藝不相同時，工裝的切換次數(shù)加1,表示為式(1)。v(Pmn,Pm-1,n)為已知的不同工藝間的切換費用系數(shù)，車型切換裝配線調(diào)整時間最小化目標可以表示為式(2)[6]。

(1)

v(Fmn,Fm-1,n))

(2)

(2)裝配線空閑/停線時間最小化目標函數(shù)f2。當工位工作在下一節(jié)拍開始時就被完成，則等待時間bmn為：

(3)

當在作業(yè)域內(nèi)無法完成工作時，生產(chǎn)線停線時間SSmn直至工位任務完成，生產(chǎn)均衡化目標函數(shù)如式(4)所示，權重ω1取值0.87，ω2取值0.13。

(4)

更一般的有式(5)和式(6)。

(5)

Pmn=max{Pm-1,n+vcCm-1,n-Ln,0}

(6)

此時若m車發(fā)生超載停線，則此時(Pm,n+vcCmn-Ln)>0，由Omn(事件m型車在n號工位上加工)導致的停線時間SSmn由式(7)，Sm+1,n由式(8)，Pm+1,n由式(9)可得。

(7)

(8)

Pm+1,n=(vc·(Smn+Cmn-Sm+1,n))=

Ln-Pm,n-vctc

(9)

若RPTjk≤SSmm則有Pj+1,k=0;SSjk=0。

(10)

Pj+1,k=(vc·(Sjk+Cjk-SSmn-Sj+1,n))=

2Ln-Pj,k-vc(tc+Cmn)-Pm,n

(11)

特別的，若RPTjk>SSmn，且有Pi-1,j+vc(Cij+SSmn)-Ln≤0，則有Pj+1,k=0;SSjk=0。

(3)物料消耗均衡化目標函數(shù)f3[6]。設總物料為Q共有q種,CSin為車型i(i=1,2,…,M)在工位Wn的加工過程所需物料表，CSin=(bomin,P),其中bomin是CSin所需物料編碼集合，bomin={Qr,…,Qr1}，Pinr是Qr類零件在該加工過程的數(shù)量，則CSin可由式(12)[6]確定。

(12)

一個投產(chǎn)批次內(nèi)的M種車型對物料Qr(r=1,2,…,q)的需求量RNi可由車型數(shù)量di(i=1,2,…,M)和車型i(i=1,2,…,M)所需物料Qr(r=1,2,…,q)的數(shù)量Pinr計算出。

(13)

(14)

(15)

(16)

則優(yōu)化目標f3為：

(17)

(4)整體目標函數(shù)f。多目標函數(shù)優(yōu)化問題求其帕累托前沿是復雜的，而單純使用經(jīng)驗權重因子法，其解空間不一定能覆蓋最優(yōu)解，因此筆者采用先求解帕累托前沿的一個子集Q再設置k1,k2,k3的值的方式，使得式(18)的解空間R與Q存在關系?α∈Q,?β∈R,α=β。

f=k1f1+k2f2+k3f3

(18)

2 基于Q-learning算法的總體設計

筆者采用Q-learning作為高層策略，建立包含GA和DE的LLH(低層算法庫)，依據(jù)LHH構建action表。在每次迭代后，以評估函數(shù)的值為依據(jù)，選擇最有潛力的搜索策略[7-9]?；赒-learning的算法流程如圖2所示，步驟參見表2。

圖2 Q-learning算法流程圖

表2 Q-learning算法步驟表

2.1 染色體編碼

若采用常規(guī)編碼方式如整數(shù)編碼則解空間大小為829=1.547 4e+26，相差了8個數(shù)量級嚴重滯后了尋優(yōu)速度。因此筆者利用排列組合本身的性質(zhì)設計了一種染色體-基因編碼方式，如圖3所示。該染色體包含兩個基因，基因A中含有的信息劃分方案是對車型數(shù)量P的劃分方式，以可空方式將P輛車劃分到x+1個空位中?；駼中是將劃分方案填充到空位的方式以整數(shù)編碼表示。這樣在進行交叉、變異操作時，能夠保證生成的新個體仍然在解空間中。

圖3 個體編碼方式圖

2.2 狀態(tài)描述

狀態(tài)是Q-learning算法中agent所理解的一種環(huán)境特征，agent需要借助這種環(huán)境特征，同最佳行為建立起穩(wěn)固的聯(lián)系，從而作為一種有價值的經(jīng)驗而得到存儲。狀態(tài)平均偏差率fa1可由式(19)和式(20)描述，即每次迭代后解的目標值的平均偏差，如果偏離值較低，說明產(chǎn)生的相似解較多，后續(xù)迭代將趨向于收斂；如果偏離值較高，表示解的差異性較大，算法正在進行積極的全局搜索。

(19)

(20)

表3 狀態(tài)分類表

2.3 行為定義

行為是Q-learning算法對當前狀態(tài)環(huán)境做出的響應。充分迭代后，agent會趨向于選擇對當前狀態(tài)環(huán)境而言未來回報最高的行為[10]。通過GA和DE兩種算法的不同算子進行組合，從而獲得4種搜索方法，即Q-learning的4種行為，如表4所示。

表4 4種行為表

2.4 行為選擇策略

在迭代初期，嘗試盡量多的選擇有助于agent學習到更多的歷史經(jīng)驗，也有助于避免算法陷入局部最優(yōu)。為避免算法過早地收斂，采用隨機輪盤賭策略，選擇概率P(Si,Ai)公式如下：

(21)

式中：Q(Sj,Ai)為每一對狀態(tài)Sj和動作Ai的獎勵期望值。

采用選擇概率P(Sj,Ai)來選擇每一候選行為Ai(i=1,2,……,NA)，其中NA為行為的數(shù)目。

2.5 行為獎勵及Q值更新

行為獎勵將鞏固agent對當前行為A(l)決策的記憶，并且在下次遇到相似狀態(tài)時，agent將會以更高的概率選擇同一行為。將本次迭代結果同歷史最優(yōu)結果的比較結果作為行為獎勵的依據(jù)，若當前迭代結果優(yōu)于歷史最優(yōu)結果，則設置獎勵值r(l)=2，否則r(l)=0。更新Q值矩陣意味著對當前環(huán)境的行為決策經(jīng)驗進行記錄，也是對歷史經(jīng)驗的再更新。通過Q-learning的學習機制，每一對狀態(tài)-行為Q(S(l-1),A(l-1))的Q值矩陣將由式(22)得到更新：

Q(S(l-1),A(l-1))=(Q-α)(S(l-1),A(l-1))+

(22)

2.6 適應度函數(shù)

適應度函數(shù)都是由目標函數(shù)轉化而來，適應度函數(shù)由式(18)表示。

3 算例結果與分析

以某汽車生產(chǎn)排產(chǎn)計劃為算例，對所提出的總裝車間混流排產(chǎn)模型及基于Q-learning的超啟發(fā)式算法的求解進行驗證。該算例擁有30個批次訂單、包含T1、T2、T3、T44種車型配置，及100種物料，進行總裝裝配的有10個工位。Q-learning算法、GA算法和DE算法的參數(shù)設置如表5～表7所示，不同迭代次數(shù)統(tǒng)計結果如表8所示。

表5 Q-learning算法的參數(shù)設置表

表6 GA參數(shù)設置表

表7 DE參數(shù)設置表

表8 不同迭代次數(shù)統(tǒng)計結果表

在求解質(zhì)量方面，將 30個批次訂單隨機劃分為訓練組20個和對照組10個，利用隨機選取訂單的策略訓練Q-learning超啟發(fā)式算法1 500次。同時觀察Q矩陣的值，當其趨于穩(wěn)定后，對對照組的10個訂單進行各10次求解并與標準GA算法和DE算法進行對照比較，結果如表9所示。通過對比可知，綜合考慮平均偏差、最大偏差、優(yōu)解比例，本文所提算法性能有明顯提升。

表9 本文算法與標準GA、DE比較表

4 結論

實現(xiàn)基于現(xiàn)場混流車間的排產(chǎn)是一項龐大復雜的工程，所涉及的領域多、約束多、例外情況多。筆者聚焦于混流生產(chǎn)線排產(chǎn)，合理地建立了目標模型，通過問題特性分析建立實用的染色體編碼方式，通過基于學習的超啟發(fā)式算法有效地結合不同啟發(fā)式算法提高了對同一系統(tǒng)下不同訂單的收斂速度。