金 淳, 冷浕伶, 胡 畔

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

0 引言

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

汽車涂裝作業(yè)排序問題屬于一類生產(chǎn)調(diào)度問題，該問題于2005年被法國運(yùn)籌及決策支持學(xué)會(huì)列為制造業(yè)的挑戰(zhàn)性問題之一[1]。目前國內(nèi)外相關(guān)研究大多是構(gòu)建問題的0-1整數(shù)規(guī)劃模型，以顏色切換次數(shù)最少為目標(biāo)，采用如遺傳算法[2]、基于規(guī)則的啟發(fā)式算法[3,4]、貪心算法[5,6]等啟發(fā)式算法進(jìn)行求解。此外，部分研究還考慮了其他因素進(jìn)行建模求解，如：劉春暉等[7]提出了從涂裝的下線順序開始進(jìn)行反向計(jì)算的倒推排序算法；Celso等人構(gòu)建了具有三個(gè)不同權(quán)重目標(biāo)的優(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)致算法的搜索性能受到一定的限制，因此，近年來人們開始嘗試具有強(qiáng)大學(xué)習(xí)能力的機(jī)器學(xué)習(xí)算法。機(jī)器學(xué)習(xí)算法能夠通過學(xué)習(xí)有效調(diào)節(jié)模型參數(shù)，其搜索性能往往比啟發(fā)式算法更好[12,13]，其中的強(qiáng)化學(xué)習(xí)算法可有效解決序列決策問題，因此被認(rèn)為是解決生產(chǎn)調(diào)度問題的一種有效方法。而啟發(fā)式強(qiáng)化學(xué)習(xí)通過與啟發(fā)式優(yōu)化方法的結(jié)合，可以進(jìn)一步提高強(qiáng)化學(xué)習(xí)算法解決實(shí)際問題的效果[14～17]，其中啟發(fā)式Q學(xué)習(xí)結(jié)合了強(qiáng)化學(xué)習(xí)的前瞻能力與啟發(fā)式因子的整體評(píng)估能力，相比于啟發(fā)式算法，能有效避免初始解質(zhì)量不佳對尋優(yōu)效果的影響。盡管強(qiáng)化學(xué)習(xí)算法已開始應(yīng)用于作業(yè)調(diào)度領(lǐng)域的研究，但目前為止，其在汽車涂裝作業(yè)排序問題中的研究還很少見。

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

1 問題描述

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

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

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

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

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

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

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

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

2 模型的構(gòu)建

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

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

(1)總裝需求延誤比例

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

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

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

(1)

(2)顏色切換比例

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

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

3 算法設(shè)計(jì)

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

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

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

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

(12)

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

(13)

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

(14)

(15)

(16)

采取動(dòng)作ac獲得的即時(shí)獎(jiǎng)勵(lì)值re由四部分組成，說明如下：

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

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

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

(17)

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

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

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

(18)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(19)

該適應(yīng)度函數(shù)由四部分組成，設(shè)當(dāng)前已涂裝序列的長度為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ù)值實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

表2 部分車身詳情

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

4.2 實(shí)驗(yàn)結(jié)果

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

如表3所示，QL和HQL的運(yùn)行時(shí)間分為兩個(gè)部分，首先通過一段時(shí)間的訓(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í)的各個(gè)指標(biāo)值，其中設(shè)置α=β=0.5，η=20。圖3～5給出了三個(gè)指標(biāo)隨著L變化的曲線。從以上結(jié)果可得，L與上述三個(gè)指標(biāo)在一定范圍內(nèi)呈反比關(guān)系，適當(dāng)?shù)卦龃驦能提高解的質(zhì)量。過小的L成為瓶頸因素，限制了算法的尋優(yōu)能力；當(dāng)L過大，L足夠滿足需要，此時(shí)解的質(zhì)量取決于算法本身的尋優(yōu)能力。實(shí)際應(yīng)用中可以根據(jù)曲線的拐點(diǎn)確定最優(yōu)L值。

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

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

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

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

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

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

(4)算法方案對比

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

5 結(jié)論

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

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

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

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

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