金 淳, 冷浕伶, 胡 畔

(大連理工大學(xué) 經(jīng)濟與管理學(xué)院,遼寧 大連 116024)

0 引言

汽車制造業(yè)是制造強國戰(zhàn)略中推動智能制造發(fā)展的重點領(lǐng)域。目前，汽車制造業(yè)正在向高效化、個性化、靈活化方向發(fā)展以有效應(yīng)對客戶的個性化訂單。在汽車制造流程中，涂裝車間作業(yè)是連接車身車間、總裝車間的中間環(huán)節(jié)，其涂裝作業(yè)排序問題十分復(fù)雜，除了作業(yè)順序要盡可能與總裝作業(yè)計劃順序保持一致，還受到噴槍顏色切換條件的限制。噴槍每切換一次顏色都要使用特定溶劑進行清洗，如果頻繁切換顏色，不僅會產(chǎn)生物料和時間上的浪費，而且會對設(shè)備造成一定損耗。因此，如何制定出可盡量減少顏色切換次數(shù)的涂裝作業(yè)排序計劃是涂裝生產(chǎn)中面臨的重要課題。

汽車涂裝作業(yè)排序問題屬于一類生產(chǎn)調(diào)度問題，該問題于2005年被法國運籌及決策支持學(xué)會列為制造業(yè)的挑戰(zhàn)性問題之一[1]。目前國內(nèi)外相關(guān)研究大多是構(gòu)建問題的0-1整數(shù)規(guī)劃模型，以顏色切換次數(shù)最少為目標，采用如遺傳算法[2]、基于規(guī)則的啟發(fā)式算法[3,4]、貪心算法[5,6]等啟發(fā)式算法進行求解。此外，部分研究還考慮了其他因素進行建模求解，如：劉春暉等[7]提出了從涂裝的下線順序開始進行反向計算的倒推排序算法；Celso等人構(gòu)建了具有三個不同權(quán)重目標的優(yōu)化模型，并利用貪心算法第次求解[8]；Estellona等人考慮涂裝輸出順序?qū)傃b作業(yè)的影響，構(gòu)建整數(shù)規(guī)劃模型，并提出了分別適合大規(guī)模問題和小規(guī)模問題的鄰域搜索算法[9]。

生產(chǎn)調(diào)度問題是一類典型的NP-Hard問題，大多研究采用啟發(fā)式算法，如蟻群算法、遺傳算法等給出問題的滿意解[10,11]。由于啟發(fā)式算法的結(jié)構(gòu)較為固定，導(dǎo)致算法的搜索性能受到一定的限制，因此，近年來人們開始嘗試具有強大學(xué)習(xí)能力的機器學(xué)習(xí)算法。機器學(xué)習(xí)算法能夠通過學(xué)習(xí)有效調(diào)節(jié)模型參數(shù)，其搜索性能往往比啟發(fā)式算法更好[12,13]，其中的強化學(xué)習(xí)算法可有效解決序列決策問題，因此被認為是解決生產(chǎn)調(diào)度問題的一種有效方法。而啟發(fā)式強化學(xué)習(xí)通過與啟發(fā)式優(yōu)化方法的結(jié)合，可以進一步提高強化學(xué)習(xí)算法解決實際問題的效果[14～17]，其中啟發(fā)式Q學(xué)習(xí)結(jié)合了強化學(xué)習(xí)的前瞻能力與啟發(fā)式因子的整體評估能力，相比于啟發(fā)式算法，能有效避免初始解質(zhì)量不佳對尋優(yōu)效果的影響。盡管強化學(xué)習(xí)算法已開始應(yīng)用于作業(yè)調(diào)度領(lǐng)域的研究，但目前為止，其在汽車涂裝作業(yè)排序問題中的研究還很少見。

綜上，本文針對汽車涂裝車間作業(yè)排序優(yōu)化問題，同時考慮顏色切換及總裝需求，構(gòu)建多目標整數(shù)規(guī)劃模型，提出啟發(fā)式算法與Q學(xué)習(xí)相結(jié)合的求解方法。本研究為解決涂裝車間作業(yè)排序問題做出新的算法嘗試，并試圖為大數(shù)據(jù)時代基于數(shù)據(jù)驅(qū)動的涂裝車間生產(chǎn)調(diào)度問題提供新的解決方案。

1 問題描述

涂裝車間的涂裝作業(yè)策略原理如圖1所示。圖中的圓圈表示待涂裝的對象(白車身)，用圓圈的不同填充方式區(qū)分顏色，用不同字母區(qū)分車型。圖例中，一個總裝需求序列包括3種顏色、4種車型、共14個車身，排序前顏色切換共11次，經(jīng)過排序后顏色切換共5次。一個涂裝作業(yè)策略包括兩部分，一是要涂裝的顏色順序，二是各顏色每次涂裝的批量大小。當涂裝某種顏色時，將一輪涂裝的車身數(shù)量稱為該顏色本輪的涂裝批量，該輪涂裝稱為一個涂裝輪次，則每種顏色的車身都會在整個涂裝過程中被分為一個或多個涂裝輪次，一種顏色各個輪次的涂裝批量可以不同。完成涂裝作業(yè)的車身稱為漆車身，它被放入涂裝車間與總裝車間之間的緩沖區(qū)，由總裝車間按其需求從緩沖區(qū)逐個提取。

本研究中的涂裝車間作業(yè)排序問題是指：為涂裝車間找到一個最優(yōu)的作業(yè)序列，既可使涂裝車間輸出車身的順序盡量與總裝車間的需求順序保持一致，同時又可使涂裝作業(yè)過程中噴槍顏色的切換次數(shù)最少。本文涉及的參數(shù)符號及含義如表1所示。

表1 部分參數(shù)符號及含義

本研究假設(shè)如下：

假設(shè)1作業(yè)時間用單位時長度量，單位時長定義為一個車身的涂裝作業(yè)時長。每個車身(各顏色、各車型)的涂裝作業(yè)時間相同；

假設(shè)2各顏色的涂裝批量相互獨立，調(diào)整某一顏色的批量大小不影響其他顏色的涂裝批量；

假設(shè)3一旦開始涂裝一個批次，須將該批次全部涂裝完畢才能開始下一批次，中途不可中斷；

假設(shè)4本文僅考慮涂裝車間與總裝車間之間的緩沖區(qū)，涂裝車間內(nèi)部的緩沖區(qū)忽略不計。

2 模型的構(gòu)建

2.1 目標函數(shù)指標的定義

本問題的目標函數(shù)包括兩個子目標：總裝需求延誤比例和顏色切換比例。具體定義如下。

(1)總裝需求延誤比例

本文衡量兩個序列差異的依據(jù)是總裝需求被延誤的程度。由于實際涂裝序列與總裝需求序列存在不一致，導(dǎo)致總裝車間需要的某些車身被延遲，總裝車間等待這些被延誤車身的時長的總和，就是該涂裝序列造成的總裝需求延誤程度。

定義變量γ和τ共同計算實際涂裝序列與總裝需求序列的差異。用序列變量Π表示一個涂裝序列中各個車身是否發(fā)生延誤，γi∈Π,i=1,2,…,M，表示第i個車身是否被延誤；序列變量Λ表示一個涂裝序列中各個車身的延誤量，τi∈Λ,i=1,2,…,M，表示第i個車身的延誤量。計算總裝需求延誤程度時，指定一個容忍度變量η，η>0，表示允許車身發(fā)生一定的延誤，若某車身的延誤量處于容忍度η內(nèi)，則不計入整個序列的總裝需求延誤程度。

定義變量ψ對總裝需求延誤程度進行歸一化處理，表示一個涂裝序列的總裝需求延誤程度與其序列長度的比值，即總裝需求延誤比例，表示如下。

(1)

(2)顏色切換比例

定義序列變量Ω表示一個涂裝序列的顏色切換次數(shù)，δi∈Ω,i=1,2,…,M-1，表示第i個車身與第i+1個車身的顏色是否相同，若兩者顏色不同，δi記為1，否則記為0。同樣，對顏色切換次數(shù)進行歸一化處理，定義變量χ表示涂裝序列的顏色切換比例，表示如下。

(2)

2.2 優(yōu)化數(shù)學(xué)模型

minΓ=αψ+βχ

(3)

(4)

(5)

(6)

(7)

lmax≤L

(8)

1≤u,d≤K

(9)

1≤v,w≤Z

(10)

α+β=1，0≤α,β≤1

(11)

約束條件(4)表示排序前后車身總數(shù)不變，式(5)和(6)分別表示排序前后各個顏色和車型的車身總數(shù)不變，式(7)表示各顏色各涂裝輪次的批量大小不能超過其對應(yīng)的上限和下限，式(8)表示涂裝序列在緩沖區(qū)中存放的最大車身數(shù)量不能超過緩沖區(qū)容量上限，式(9)和(10)分別表示車身的顏色和車型不能超出給定范圍，式(11)表示兩個權(quán)重參數(shù)值分別處于0～1之間，且其和為1。

3 算法設(shè)計

本文提出一種針對涂裝車間作業(yè)優(yōu)化排序問題的啟發(fā)式Q學(xué)習(xí)算法。由于本文算法是在Q學(xué)習(xí)算法上的改進，為此先介紹本文的Q學(xué)習(xí)算法設(shè)計。

3.1 Q學(xué)習(xí)算法設(shè)計

Q學(xué)習(xí)算法是一種離線策略時序差分強化學(xué)習(xí)(Temporal-Difference Reinforcement Learning)算法，它直接優(yōu)化一個可迭代計算的狀態(tài)-行為對價值函數(shù)，即Q函數(shù)，只要使用訓(xùn)練好的Q函數(shù)，就能得到最佳的動作序列[18,19]。設(shè)計Q學(xué)習(xí)算法時，一般要將問題表述為馬爾可夫過程或半馬爾可夫過程，并根據(jù)實際問題定義狀態(tài)特征、動作及回報函數(shù)，以及算法的迭代方式[20,21]。本研究將涂裝作業(yè)排序問題抽象為一個馬爾可夫過程，認為作業(yè)排序過程是一種序列決策過程，如圖2所示。則使用Q學(xué)習(xí)求解的基本思路是：使強化學(xué)習(xí)agent根據(jù)當前已涂裝情況，預(yù)測接下來涂裝哪種顏色和車型的車身能使收益最大化。

sw=(tc,hn,ro,cv,bt,lt,pv)

(12)

本問題的初始狀態(tài)定義為：

(13)

本問題中，動作被定義為選擇某一種顏色和車型的車身作為下一個要涂裝的車身。具體如下:

(14)

(15)

(16)

采取動作ac獲得的即時獎勵值re由四部分組成，說明如下：

(1)動作ac執(zhí)行后造成的總裝需求延誤量，用變量ψs表示，ψs=γi·τi，i=1,2,…,M；

(2)動作ac執(zhí)行后顏色切換次數(shù)是否增加，用變量χs表示，若增加，將χs置為1，否則為0；

(3)懲罰項ω，反映當前已占用的緩沖區(qū)大小l是否大于L，若大于，將ω置為某個正數(shù)Dp，Dp的值反映了懲罰力度的大小，否則將ω置為0。

(17)

(4)動作ac執(zhí)行后，該車身是否需要在緩沖區(qū)停留，用變量φ表示，若需要，將φ置為1，否則為0。為使緩沖區(qū)得到充分利用，車身需要停留時，給一個較小的獎勵wb，wb>0，與懲罰項ω配合能使緩沖區(qū)的占用量處于合理范圍內(nèi)。

由于Q值將收斂于最大值，因此re定義如下：

re=-(αψs+βχs+ω)+wbφ

(18)

算法主要流程如下(用不同的縮進值來體現(xiàn)算法的循環(huán)結(jié)構(gòu))：

Step1設(shè)置L，Dp，wb等算法參數(shù)；

Step2初始化Q矩陣為零矩陣；

Step3對于每一個世代(episode)：

Step4以初始狀態(tài)sw0開始；

Step6在當前狀態(tài)St下，在所有可能的動作中，選擇一個可能的動作ac；

Step7執(zhí)行ac，到達下一個狀態(tài)St+1；

Step8對下一個狀態(tài)St+1，基于其所有可能的動作，獲得最大Q值；

Step9用Q函數(shù)更新公式計算狀態(tài)-動作對St與ac對應(yīng)的Q值，更新Q矩陣；

Step10設(shè)置下一個狀態(tài)St+1替換為新的St，更新sw，返回Step 5；

Step11重復(fù)Step 3直至Q矩陣收斂或達到最大迭代次數(shù)。

訓(xùn)練結(jié)束后，就可以利用Q矩陣得到最優(yōu)的涂裝作業(yè)策略，即最優(yōu)的涂裝顏色和車型序列。

3.2 啟發(fā)式Q學(xué)習(xí)算法設(shè)計

在大規(guī)?；驈?fù)雜問題的求解中，強化學(xué)習(xí)算法會遭遇“維度爆炸”難題。對此難題，在算法設(shè)計時，一方面可從狀態(tài)空間入手，用降維的方法降低狀態(tài)空間的復(fù)雜度[14,15]；另一方面可通過給強化學(xué)習(xí)模型注入先驗知識的方式，起到加快收斂速度和一定的降維作用，主要采用兩種途徑：一是使用啟發(fā)式強化學(xué)習(xí)模型，使啟發(fā)式函數(shù)與值函數(shù)一起作為獎勵函數(shù)，共同指導(dǎo)訓(xùn)練[16]，二是利用強化學(xué)習(xí)幫助啟發(fā)式算法提升搜索性能，避免陷入局部最優(yōu)[17]。本文提出的啟發(fā)式Q學(xué)習(xí)算法是基于第一種途徑，在Q函數(shù)中引入啟發(fā)式因子，可在一定程度上引導(dǎo)Q學(xué)習(xí)的搜索方向，具有更好的實用價值。

本文在傳統(tǒng)Q學(xué)習(xí)算法方案的基礎(chǔ)上，加入了遺傳算法中適應(yīng)度的概念。在更新Q函數(shù)時，不僅考慮動作ac帶來的期望獎勵，同時在整體上評估已涂裝序列的適應(yīng)度，共同引導(dǎo)Q學(xué)習(xí)的搜索方向，以加快搜索效率。

定義啟發(fā)式Q學(xué)習(xí)中的適應(yīng)度函數(shù)為：

(19)

該適應(yīng)度函數(shù)由四部分組成，設(shè)當前已涂裝序列的長度為M′:

(1)已涂裝序列的總裝需求延誤比例ψh，即

(20)

(2)已涂裝序列發(fā)生的顏色切換比例χh，即

(21)

(22)

因此在啟發(fā)式Q學(xué)習(xí)算法方案中，Q函數(shù)的更新公式為:

Q(St,At)←Q(St,At)+σ(Rt+1+υQ(St+1,A′-

(23)

其中，σ和υ分別表示Q學(xué)習(xí)算法中的學(xué)習(xí)率和衰減系數(shù)，ρ表示啟發(fā)式因子的權(quán)重，ρ越大表示啟發(fā)式因子的影響力越大。

4 數(shù)值實驗及分析

4.1 實驗設(shè)計

本研究在企業(yè)調(diào)研實際數(shù)據(jù)基礎(chǔ)上生成兩個算例，分別包含650個和1300個涂裝作業(yè)，包含6個車型和10種顏色。部分作業(yè)詳情如表2所示。

表2 部分車身詳情

本實驗將本研究提出的啟發(fā)式Q學(xué)習(xí)算法與遺傳算法、傳統(tǒng)Q學(xué)習(xí)算法方案進行對比，以證明本研究算法的有效性。求解算法采用Java和Python編寫，實驗環(huán)境配置如下：Intel i7-7700處理器(3.60GHZ)，8G內(nèi)存，Windows 10操作系統(tǒng)。

4.2 實驗結(jié)果

表3 平均計算結(jié)果

如表3所示，QL和HQL的運行時間分為兩個部分，首先通過一段時間的訓(xùn)練得到Q函數(shù)，再使用Q函數(shù)得到優(yōu)化結(jié)果。從表中結(jié)果可知：QL和HQL比GA表現(xiàn)更優(yōu)，HQL比QL表現(xiàn)更優(yōu)。在M=650算例上，本文算法得到的ψ比GA低15.54%，比QL低4.58%，得到的χ比GA低13.19%，比QL低6.78%。在M=1300算例上，本文算法得到的ψ比GA低13.08%，比QL低2.91%，得到的χ比GA低16.81%，比QL低4.55%。

4.3 結(jié)果分析

(1)緩沖區(qū)容量L對涂裝作業(yè)排序結(jié)果的影響

表4給出了本文算法在L分別取25、50、100、150時的各個指標值，其中設(shè)置α=β=0.5，η=20。圖3～5給出了三個指標隨著L變化的曲線。從以上結(jié)果可得，L與上述三個指標在一定范圍內(nèi)呈反比關(guān)系，適當?shù)卦龃驦能提高解的質(zhì)量。過小的L成為瓶頸因素，限制了算法的尋優(yōu)能力；當L過大，L足夠滿足需要，此時解的質(zhì)量取決于算法本身的尋優(yōu)能力。實際應(yīng)用中可以根據(jù)曲線的拐點確定最優(yōu)L值。

表4 L對涂裝作業(yè)排序結(jié)果的影響

(2)容忍度變量η對涂裝作業(yè)排序結(jié)果的影響

表5給出了本文算法在η分別取10、30、50、70時的各個指標值，設(shè)α=β=0.5，L=200。圖6～8給出了三個指標隨著η變化的曲線。從以上結(jié)果可知，隨著η的上升，一方面ψ有較大幅度的減少，另一方面由于對延誤情況的懲罰力度降低，agent在訓(xùn)練過程中對延誤情況不敏感，因此會為了進一步降低χ而增加對緩沖區(qū)的利用。然而當η增加到一定程度時，由于算法本身尋優(yōu)能力的限制，χ和φmax都會趨于穩(wěn)定。

表5 η對涂裝作業(yè)排序結(jié)果的影響

(3)權(quán)重α、β對涂裝作業(yè)排序結(jié)果的影響

圖9～11給出了本文算法在M=650，L=100且兩個權(quán)重變量滿足α+β=1時，ψ、χ、φmax的變化曲線。由結(jié)果可得，α和β的關(guān)系為算法搜索起到了導(dǎo)向作用，當α=1，β=0，算法只有一個優(yōu)化目標，ψ會盡可能降至最低，而χ則被忽略，反之亦然。

(4)算法方案對比

由以上實驗結(jié)果可得，本文算法比傳統(tǒng)Q學(xué)習(xí)算法表現(xiàn)更優(yōu)，強化學(xué)習(xí)算法方案比遺傳算法方案表現(xiàn)更優(yōu)。強化學(xué)習(xí)算法方案訓(xùn)練時間長，得到的解更優(yōu)，問題規(guī)模越大啟發(fā)式因子對解的質(zhì)量和搜索效率的提升作用越明顯。

5 結(jié)論

本文針對涂裝車間作業(yè)排序優(yōu)化問題開展研究，結(jié)論如下：

(1)構(gòu)建了以降低總裝需求延誤和顏色切換次數(shù)為目標的多目標整數(shù)規(guī)劃模型。將問題抽象為馬爾可夫過程，提出了基于啟發(fā)式Q學(xué)習(xí)算法的解決方案。

(2)通過對本文算法、遺傳算法、Q學(xué)習(xí)算法的比較實驗結(jié)果表明：強化學(xué)習(xí)算法方案比遺傳算法方案表現(xiàn)更優(yōu)，本文算法比傳統(tǒng)Q學(xué)習(xí)算法表現(xiàn)更優(yōu)。本文算法能夠有效求解汽車涂裝車間作業(yè)優(yōu)化排序問題，其優(yōu)勢在于：結(jié)合強化學(xué)習(xí)算法的前瞻能力與啟發(fā)式因子的整體評估能力，相比遺傳算法能降低對初始解質(zhì)量的依賴。

(3)本算法的特點在于：在訓(xùn)練階段，如果數(shù)據(jù)充分，雖然訓(xùn)練時間更長，但算法訓(xùn)練效果更好，可以得到更優(yōu)的解；問題規(guī)模越大啟發(fā)式因子對解的質(zhì)量和搜索效率的提升作用越明顯；在優(yōu)化階段，可以用比遺傳算法更短的時間得到更好的求解結(jié)果。其意義在于：在大數(shù)據(jù)和智能制造時代，利用高性能計算資源和海量數(shù)據(jù)，采用線下充分訓(xùn)練，線上快速求解的方式實現(xiàn)比啟發(fā)式算法方案更為滿意的優(yōu)化結(jié)果。

今后的研究可以繼續(xù)深入考慮以下兩個問題：一是建模中考慮作業(yè)過程可能出現(xiàn)的返修情況；二是嘗試將強化學(xué)習(xí)算法與其他優(yōu)化方法相結(jié)合，以進一步提升求解質(zhì)量和搜索效率。