譚遠(yuǎn)良，呂佑龍，左麗玲，張 潔

(東華大學(xué)a.機(jī)械工程學(xué)院；b.人工智能研究院，上海 201620)

0 引言

隨著航天產(chǎn)品迎來新一輪的發(fā)展，其種類大幅增加，呈現(xiàn)出多品種、小批量的生產(chǎn)特點。各產(chǎn)品類型在工位上的裝配時間存在差異，使得總裝線上的產(chǎn)品投產(chǎn)排序難以依靠人工計劃實現(xiàn)工位負(fù)荷均衡，出現(xiàn)負(fù)荷過大的瓶頸工位，難以滿足航天產(chǎn)品嚴(yán)格按時交付的特殊性要求?；炝餮b配線排序問題通過安排多類型產(chǎn)品在裝配線的投產(chǎn)順序，可實現(xiàn)裝配線工位負(fù)荷均衡，對提高航天產(chǎn)品制造效率具有重要意義[1-3]。

啟發(fā)式算法由于通用性好、搜索能力強(qiáng)等優(yōu)點，被廣泛應(yīng)用在車間調(diào)度問題中[4-6]，如針對混流裝配線投產(chǎn)排序問題，劉瓊等[7]提出了一種遺傳算法和粒子群算法結(jié)合的混合算法，解決多目標(biāo)混流裝配線排序問題。孫寶鳳等[8]提出了一種基于遺傳算法的雙目標(biāo)混流裝配線投產(chǎn)排序決策模型，實現(xiàn)物料消耗方差和換裝成本最小化。魯建廈等[9]以最小化總調(diào)整時間和最小化超載時間與空閑時間為優(yōu)化目標(biāo)，提出了一種混合人工蜂群算法，解決混流汽車裝配線排序問題。ZHAO等[10]提出了一種混沌差分進(jìn)化算法，解決混流裝配線的多目標(biāo)排序問題。KIM等[11]提出了一種最小化效用工作和空閑時間的快速排序算法，解決多工位混流裝配線排序問題。ZHONG等[12]提出了一種改進(jìn)粒子群優(yōu)化算法，解決船體裝配線多目標(biāo)排序問題。但是上述算法也存在收斂不穩(wěn)定，收斂速度受種群初始化影響等缺點，當(dāng)產(chǎn)品需求比例發(fā)生變化時，需重新訓(xùn)練，使得難以快速搜索到合理的產(chǎn)品投產(chǎn)序列。

由于深度強(qiáng)化學(xué)習(xí)集成了深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)的優(yōu)點，能解決復(fù)雜高維狀態(tài)空間中的感知決策問題，也逐漸被應(yīng)用于車間調(diào)度問題中，例如鐘敬偉等[13]提出了結(jié)合新的復(fù)合調(diào)度規(guī)則和深度強(qiáng)化學(xué)習(xí)的調(diào)度方法，解決作業(yè)車間調(diào)度問題。ZHAO等[14]提出了一種基于Deep Q-Network(DQN)深度強(qiáng)化學(xué)習(xí)的工件裝配順序規(guī)劃算法，提高裝配規(guī)劃系統(tǒng)效率。LIU等[15]基于Actor-Critic架構(gòu)的深度確定性策略梯度算法，結(jié)合異構(gòu)更新方法，解決了隨機(jī)動態(tài)事件影響下的作業(yè)車間調(diào)度問題。以上研究工作表明，DQN、Actor-Critic等強(qiáng)化學(xué)習(xí)算法能有效解決車間調(diào)度問題。但是針對混流裝配線投產(chǎn)排序這類動作空間和狀態(tài)空間復(fù)雜的感知決策問題，算法難以在較短時間內(nèi)搜索到一個合理的產(chǎn)品投產(chǎn)序列。

本文結(jié)合航天產(chǎn)品總裝生產(chǎn)特點，構(gòu)建混流裝配線投產(chǎn)排序問題的數(shù)學(xué)模型，并針對現(xiàn)有混流裝配線投產(chǎn)排序方法存在的缺點、深度強(qiáng)化學(xué)習(xí)方法在車間調(diào)度問題中的研究現(xiàn)狀，提出了一種具有記憶功能的改進(jìn)Actor-Critic算法，綜合基于Critic網(wǎng)絡(luò)的on-policy和基于較好實例的off-policy，實現(xiàn)排序策略快速學(xué)習(xí)，增強(qiáng)算法的搜索效率，以快速獲得合理的產(chǎn)品投產(chǎn)序列。

1 航天產(chǎn)品混流裝配線投產(chǎn)排序問題

1.1 問題描述

隨著航天產(chǎn)品種類的增加，過去批量輪番生產(chǎn)的方式難以滿足變化的訂單需求，裝配過程呈現(xiàn)出多品種、小批量的生產(chǎn)特點。針對上述生產(chǎn)特點，將待裝配產(chǎn)品集合劃分為若干個可循環(huán)重復(fù)的最小生產(chǎn)集合(minimum part set，MPS)，MPS表示為n1/h,…,nt/h,…,n|T|/h，其中nt為產(chǎn)品t的需求量，h為各產(chǎn)品需求量的最大公約數(shù)[16]，循環(huán)投產(chǎn)MPS，完成訂單交付。上述生產(chǎn)特點使得航天產(chǎn)品裝配線投產(chǎn)排序問題也屬于NP-Hard問題。航天產(chǎn)品混流裝配線投產(chǎn)排序問題基于以下假設(shè)條件：

①工件由輸送帶以恒定速率R在|S|個工位上進(jìn)行傳輸；

②每個裝配工位長度固定為ls，工位與工位之間相互封閉，工人只能在指定工位內(nèi)作業(yè)；

③工件以固定投產(chǎn)時間節(jié)拍C進(jìn)行投產(chǎn)；

④忽略工人的行走時間；

⑤未完成的工件任務(wù)由線旁工人補(bǔ)充完成；

航天產(chǎn)品屬于備料式生產(chǎn)，物料等待會造成工期緊張、生產(chǎn)節(jié)拍過短，工人無法完成裝配作業(yè)會產(chǎn)生工位過載，需要線旁工人補(bǔ)充完成。這將會造成額外的工人成本，且存在一定的質(zhì)量隱患。因此，航天產(chǎn)品混流裝配線投產(chǎn)排序問題旨在實現(xiàn)最小化工位過載時間目標(biāo)。

1.2 數(shù)學(xué)模型

根據(jù)如表1所示的數(shù)學(xué)符號，航天產(chǎn)品混流裝配線投產(chǎn)排序問題的數(shù)學(xué)模型如下[17]：

(1)

s.t.

(2)

(3)

Os1=0,?s

(4)

(5)

(6)

式(1)給出了最小化工位過載時間的優(yōu)化目標(biāo)。在約束條件方面：式(2)保證一次只有一種產(chǎn)品類型被投放；式(3)保證MPS中所有產(chǎn)品均被投放；式(4)定義第一個產(chǎn)品在工位s上的裝配開始位置；式(5)計算產(chǎn)品投產(chǎn)序列第d個產(chǎn)品在工位s上的裝配開始位置；式(6)計算產(chǎn)品投產(chǎn)序列中第d個產(chǎn)品在工位s上的工位過載時間。

表1 排序問題中的數(shù)學(xué)符號

2 航天產(chǎn)品混流裝配線投產(chǎn)排序方法

2.1 具有記憶功能的Actor-Critic算法

Actor-Critic算法旨在最大化獎勵目標(biāo)，通過Actor和Critic之間的相互迭代，實現(xiàn)馬爾科夫決策過程(markov decision process，MDP)優(yōu)化。針對航天產(chǎn)品混流裝配線投產(chǎn)排序問題，將裝配過程要素與MDP要素進(jìn)行映射，具體設(shè)定如表2所示。

表2 航天產(chǎn)品混流裝配線投產(chǎn)排序過程的MDP模型

由于存在多種產(chǎn)品類型和工位狀態(tài)，導(dǎo)致動作和狀態(tài)空間過大，Actor-Critic算法難以在較短時間內(nèi)搜索到較優(yōu)排序策略。結(jié)合航天產(chǎn)品混流裝配線實際特點，本節(jié)提出一種改進(jìn)的Actor-Critic算法?；诤教飚a(chǎn)品混流裝配線投產(chǎn)排序過程的MDP模型，設(shè)計了綜合基于Critic網(wǎng)絡(luò)的on-policy和基于較好實例的off-policy的兩種Actor網(wǎng)絡(luò)學(xué)習(xí)機(jī)制。

Actor根據(jù)當(dāng)前工位狀態(tài)Osd，通過排序策略選擇產(chǎn)品次序d上的產(chǎn)品類型Xtd，并將其投放到混流裝配線上，如圖1所示；待完成該產(chǎn)品的裝配任務(wù)后，各工位狀態(tài)轉(zhuǎn)移為Os(d+1)。接著Critic估計當(dāng)前工位狀態(tài)Osd和下一個工位狀態(tài)Os(d+1)的獎勵期望值，通過上述獎勵期望值以及工位過載時間isd計算時序差分誤差(temporal-difference error，TD error)，on-policy基于TD error值的正負(fù)和大小，利用Adam算法更新Critic網(wǎng)絡(luò)權(quán)重參數(shù)和排序策略，不斷循環(huán)上述排序過程，直至產(chǎn)品次序d等于|D|。過程中所選產(chǎn)品類型Xtd、工位狀態(tài)Osd等歷史數(shù)據(jù)存儲在歷史記憶功能中。

圖1 MAC算法結(jié)構(gòu)

重復(fù)循環(huán)上述過程，直至滿足個體數(shù)要求，接著歷史記憶功能篩選出較好實例，off-policy以較好實例為對象，基于總工位過載時間以及實例全序列狀態(tài)-動作對進(jìn)行離線學(xué)習(xí)，考慮在各狀態(tài)下選擇產(chǎn)品類型Xtd對總工位過載時間的影響，利用總工位過載時間計算在工位狀態(tài)Osd下選擇產(chǎn)品類型Xtd的實例時序差分誤差，以此形成較好實例的時序差分序列，優(yōu)化Actor網(wǎng)絡(luò)權(quán)重參數(shù)，提升算法學(xué)習(xí)和搜索效率；基于歷史記憶功能，綜合兩種排序策略學(xué)習(xí)機(jī)制，由此形成了具有記憶功能的Actor-Critic(memory-based actor-critic，MAC)算法。

2.2 算法步驟

在傳統(tǒng)Actor-Critic算法基礎(chǔ)上，MAC算法設(shè)置離線學(xué)習(xí)次數(shù)G，每次I個個體，其中一個個體表示完成一個MPS排序。根據(jù)傳統(tǒng)Actor-Critic算法的流程，結(jié)合MAC算法的結(jié)構(gòu)改進(jìn)，形成MAC算法流程如下：

步驟1：設(shè)置算法參數(shù)，初始化離線學(xué)習(xí)次數(shù)G和個體數(shù)I、Critic網(wǎng)絡(luò)學(xué)習(xí)率LR_C以及Actor網(wǎng)絡(luò)學(xué)習(xí)率LR_A等；根據(jù)經(jīng)驗設(shè)定產(chǎn)品投產(chǎn)間隔時間C。

步驟2：初始化第g代，?g∈{1,2,…,G}。

步驟3：初始化第i個階段的MPS和工位狀態(tài)Os1參數(shù)，?i∈{1,2,…,I}。

步驟4：根據(jù)裝配線各工位狀態(tài)Osd，Actor選擇投產(chǎn)產(chǎn)品類型Xtd，?d∈D，?s∈S，?t∈T。

Xtd=μ(Osd|θμ)

(7)

式中，μ表示排序策略；θ表示Actor網(wǎng)絡(luò)權(quán)重參數(shù)。

步驟5：投入產(chǎn)品類型Xtd，得到選擇該產(chǎn)品類型所對應(yīng)的裝配過載時間rd和下一個工位狀態(tài)Os(d+1)。

(8)

步驟6：Critic階段根據(jù)上一個工位狀態(tài)Osd、獎勵rd以及下一個工位狀態(tài)Os(d+1)的學(xué)習(xí)，評價所選產(chǎn)品類型Xtd，并反饋TDerror。

TDerror=rd+γ*V′-V

(9)

式中，V′代表對當(dāng)前工位狀態(tài)Os(d+1)的獎勵期望；V代表對上一個工位狀態(tài)Osd的獎勵期望；γ是折扣率，0<γ<1，表示獎勵隨著時間的增加而減少。

步驟7：為了最小化由TDerror構(gòu)成的損失函數(shù)，Actor和Critic分別以學(xué)習(xí)率LR_A和LR_C更新網(wǎng)絡(luò)權(quán)重參數(shù)。

步驟8：如果d≥|D|，歷史記憶功能記錄產(chǎn)品投產(chǎn)序列解，否則MDP返回步驟4，并且d=d+1。

步驟9：如果i≥I，歷史記憶功能根據(jù)第j個解，輸出TDerror，?j∈{1,2,…,I}。

(10)

式中，Rgj是指第g代中第j個產(chǎn)品投產(chǎn)序列的總工位過載時間；MinRg是指前g代所有產(chǎn)品投產(chǎn)序列中最小的總工位過載時間。否則返回步驟3，并且i=i+1。

步驟10：Actor網(wǎng)絡(luò)根據(jù)學(xué)習(xí)率LR_A更新權(quán)重參數(shù)，使由TDerror所構(gòu)成的損失函數(shù)最小化，其中該TDerror由式(10)生成。

步驟11：如果g=G，則歷史記憶功能輸出工位過載時間為MinRg的產(chǎn)品投產(chǎn)序列解，并且g=G+1。否則g=g+1。

步驟12：如果g≤G，該MDP返回步驟2。否則算法結(jié)束。

3 算例驗證

在處理器為Intel(R)Core(TM)i5-9300H CPU@2.4 GHz四核處理器，RAM為8 GB，64位Window10操作系統(tǒng)的計算機(jī)環(huán)境下，分別在小規(guī)模算例和大規(guī)模算例中設(shè)計多組MPS進(jìn)行對比實驗，將MAC算法與車間調(diào)度問題中已有廣泛應(yīng)用的傳統(tǒng)Actor-Critic算法、DQN算法以及遺傳算法進(jìn)行對比分析。

3.1 小規(guī)模算例

根據(jù)表3中的數(shù)據(jù)，隨機(jī)生成3個不同的小規(guī)模算例，進(jìn)行參數(shù)實驗。

表3 小規(guī)模算例設(shè)定

3.1.1 Actor-Critic網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)實驗

假設(shè)MAC算法的Actor學(xué)習(xí)率LR_A為5×10-5、Critic學(xué)習(xí)率LR_C為5×10-4，進(jìn)行參數(shù)實驗，MAC算法和DQN算法的網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)如表4所示。

表4 小規(guī)模算例下的網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)設(shè)置

3.1.2 Actor-Critic算法參數(shù)實驗

進(jìn)一步對MAC算法參數(shù)中的Actor學(xué)習(xí)率LR_A和Critic學(xué)習(xí)率LR_C進(jìn)行正交實驗?？紤]MAC算法的Actor學(xué)習(xí)率LR_A水平分別為5×10-4、5×10-5和5×10-6；Critic學(xué)習(xí)率LR_C水平分別為5×10-3、5×10-4和5×10-5。根據(jù)實驗結(jié)果，Actor學(xué)習(xí)率LR_A設(shè)置為5×10-5，Critic學(xué)習(xí)率LR_C設(shè)置為5×10-4。參考相關(guān)文獻(xiàn)，DQN算法的學(xué)習(xí)率LR設(shè)為0.01[18]。

3.1.3 對比實驗與結(jié)果討論

根據(jù)3.1.1節(jié)與3.1.2節(jié)參數(shù)實驗，采用基于文獻(xiàn)[19]的小規(guī)模算例，對比MAC算法、傳統(tǒng)Actor-Critic算法、DQN算法和遺傳算法的排序結(jié)果。

由于傳統(tǒng)Actor-Critic算法結(jié)構(gòu)與MAC相同，因此設(shè)置相同參數(shù)。遺傳算法染色體編碼采用十進(jìn)制編碼，交叉算子采用POX交叉方法，變異采用隨機(jī)兩點交換位置方式，算法參數(shù)為交叉率Pc=0.8，變異率Pm=0.1[20-21]。

為驗證MAC算法的有效性，設(shè)置相同個體數(shù)和離線學(xué)習(xí)次數(shù)，隨機(jī)生成12組MPS進(jìn)行實驗，4種算法的實驗結(jié)果如表5所示，其中Umin表示最小工位過載時間。

表5 小規(guī)模目標(biāo)算例對比結(jié)果

由表5可知，由于狀態(tài)空間較為復(fù)雜，傳統(tǒng)Actor-Critic算法難以在短時間內(nèi)搜索到較優(yōu)產(chǎn)品投產(chǎn)序列；DQN算法利用雙網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行學(xué)習(xí)，避免過高估計，相對于傳統(tǒng)Actor-Critic算法，能短時間內(nèi)獲得更好的產(chǎn)品投產(chǎn)序列，但是難以從部分歷史數(shù)據(jù)中學(xué)習(xí)到更好的排序策略；遺傳算法由于在小規(guī)模算例時有較好的遍歷性，能快速遍歷出一個可行解，但是其局部搜索效果一般；相對于上述3種算法，MAC算法通過利用歷史記憶功能輸出的較好實例時序差分序列進(jìn)行排序策略學(xué)習(xí)，使算法更快搜索到較優(yōu)的產(chǎn)品投產(chǎn)序列。以上算法整體結(jié)果如圖2所示。綜上所述，相對于傳統(tǒng)Actor-Critic算法、DQN算法和遺傳算法，MAC算法表現(xiàn)出較好的學(xué)習(xí)和搜索效率，驗證了MAC算法的有效性。

圖2 小規(guī)模目標(biāo)算例實驗結(jié)果

3.2 大規(guī)模算例

根據(jù)表6中的數(shù)據(jù)，隨機(jī)生成兩個不同的大規(guī)模算例，進(jìn)行參數(shù)實驗。

表6 大規(guī)模算例設(shè)定

3.2.1 Actor-Critic網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)實驗

參照小規(guī)模算例，對MAC算法和DQN算法的網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)進(jìn)行實驗，結(jié)果如表7所示。

表7 大規(guī)模算例的網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)設(shè)置

3.2.2 Actor-Critic算法參數(shù)實驗

參照小規(guī)模算例進(jìn)行正交實驗，根據(jù)實驗結(jié)果，Actor學(xué)習(xí)率LR_A設(shè)置為5×10-6，Critic學(xué)習(xí)率LR_C設(shè)置為5×10-3。參考相關(guān)文獻(xiàn)，DQN算法的學(xué)習(xí)率LR設(shè)為0.01[18]。

3.2.3 對比實驗與結(jié)果討論

根據(jù)3.2.1節(jié)與3.2.2節(jié)的參數(shù)實驗結(jié)果，采用基于文獻(xiàn)[19]的大規(guī)模算例，對比MAC算法、傳統(tǒng)Actor-Critic算法、DQN算法和遺傳算法的投產(chǎn)排序結(jié)果。

傳統(tǒng)Actor-Critic算法的網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)和算法參數(shù)與MAC算法設(shè)置一致。遺傳算法的編碼方式、交叉與變異方式以及超參數(shù)設(shè)置均與小規(guī)模算例實驗時相同。

為驗證MAC算法的有效性，設(shè)置相同個體數(shù)和離線學(xué)習(xí)次數(shù)，隨機(jī)生成12組MPS進(jìn)行實驗，4種算法的實驗結(jié)果如表8所示，其中Umin表示最小工位過載時間。

表8 大規(guī)模目標(biāo)算例對比結(jié)果

由表8可知，傳統(tǒng)Actor-Critic算法由于可選產(chǎn)品類型和數(shù)量增加，導(dǎo)致動作空間過大，難以在較短時間內(nèi)搜索到較優(yōu)的排序策略；而DQN算法能獲得較好的產(chǎn)品投產(chǎn)序列，但是其求解結(jié)果可能受到歷史數(shù)據(jù)的限制；遺傳算法局部搜索效果一般，難以遍歷到較好的產(chǎn)品投產(chǎn)序列；MAC算法基于較好實例的off-policy，指導(dǎo)排序策略優(yōu)化，獲得了相對其他算法更好的產(chǎn)品投產(chǎn)序列，整體結(jié)果如圖3所示。綜上所述，相對于傳統(tǒng)Actor-Critic算法、DQN算法和遺傳算法，MAC算法在大規(guī)模算例中表現(xiàn)出了較好的學(xué)習(xí)和搜索效率，驗證了MAC算法的有效性。

圖3 大規(guī)模目標(biāo)算例實驗結(jié)果

根據(jù)小規(guī)模案例和大規(guī)模案例的實驗結(jié)果可知，傳統(tǒng)Actor-Critic算法當(dāng)動作空間和狀態(tài)空間過大時，難以在較短時間內(nèi)搜索到較好的排序策略；DQN算法由于使用雙網(wǎng)絡(luò)結(jié)構(gòu)防止過高估計，相對于傳統(tǒng)Actor-Critic算法，能獲得更好的尋優(yōu)效果；遺傳算法在小規(guī)模算例和大規(guī)模算例時，其局部搜索能力一般，難以遍歷到較好的產(chǎn)品投產(chǎn)序列；相對于上述4種算法，MAC算法通過綜合基于Critic網(wǎng)絡(luò)的on-policy和基于較好實例的off-policy，更新Actor網(wǎng)絡(luò)權(quán)重參數(shù)，提升算法學(xué)習(xí)和搜索效率，使得更快搜索到較優(yōu)的解空間，在小規(guī)模算例和大規(guī)模算例中搜索到更好的產(chǎn)品投產(chǎn)序列，驗證了MAC算法的有效性。

4 結(jié)論

根據(jù)航天產(chǎn)品裝配特點，針對以最小化工位過載時間為優(yōu)化目標(biāo)的混流裝配線投產(chǎn)排序問題，設(shè)計了一種具有記憶功能的改進(jìn)Actor-Critic算法，最終得到結(jié)論如下：

(1)設(shè)計了基于Critic網(wǎng)絡(luò)的on-policy和基于較好實例的off-policy兩種學(xué)習(xí)機(jī)制，以此提升Actor網(wǎng)絡(luò)中的排序策略訓(xùn)練效果，有效提升了傳統(tǒng)Actor-Critic算法的學(xué)習(xí)與搜索效率。

(2)在與傳統(tǒng)Actor-Critic算法、DQN算法以及遺傳算法的對比實驗中，驗證了本文算法的有效性。