基于復合規則和強化學習的混流裝配線調度方法

郭具濤 呂佑龍 戴 錚 張 潔 郭 宇

1.上海航天精密機械研究所,上海,2016002.南京航空航天大學機電學院,南京,2100163.東華大學人工智能研究院,上海,201620

0 引言

隨著航空航天、汽車等領域的客戶化定制需求不斷增加[1-2],越來越多的制造企業利用總裝階段的多品種混線生產保障產品的準時交付,并且逐步采用單元式生產模式,利用裝配單元的資源配置柔性與物流供應柔性,實現給定生產節拍下的均衡生產。這種方式面臨裝配單元之間的負載均衡,以及不同產品之間的投產規劃等調度難題,需要考慮工人裝配能力差異和產品裝配時間差異等約束,解決混流裝配線的平衡與排序問題,合理安排各裝配單元的工人和產品投產序列,提升裝配線的生產效率。

針對混流裝配線平衡與排序問題,目前的研究方法以啟發式規則和智能算法為主[3-4]。RAUF等[5]融合優先級規則與多準則NEH算法,通過對優先級規則進行組合優化,實現了面向多目標集成優化的算法求解。AKYOL等[6]通過設計工人優先級規則和任務優先級規則,提出一種基于多規則的隨機搜索算法。DEFERSHA等[7]設計了一種嵌入多階段線性規劃的遺傳算法,求解了平衡與排序問題。ZHANG等[8]提出一種多目標遺傳算法來集成優化平衡問題與排序問題。智能算法利用全局搜索能力可獲得較優解,但需要大量計算時間,難以滿足大規模生產的需求。啟發式規則能以較短時間獲得合理的調度方案,但對調度問題的適應性較差。復合規則對不同啟發式規則進行線性加權,能通過參數變化適應不同問題,但參數設置依賴人工經驗和試驗結果,難以穩定獲得較優的調度方案。

隨著人工智能技術的發展,強化學習等機器學習方法將調度問題映射為狀態-動作轉移函數和獎勵函數來最大化獎勵函數的動作規劃過程,獲取較優調度方案。賀俊杰等[9]提出一種基于長短期記憶網絡與強化學習算法的調度方法來求解最小化加權完工時間的等效并行機在線調度問題。WANG等[10]根據3種啟發式規則(底層工序優先、最長加工時間優先和最短加工時間優先),提出一種雙層Q-learning算法來求解最小化交付懲罰的裝配車間調度問題。TORTORELLI等[11]提出一種基于并行深度強化學習的混流裝配線平衡方法,以最小化生產周期。調度問題變化時,強化學習算法需要根據新的狀態空間與動作空間重新訓練,產生新的大量計算工作。

本文提出基于復合規則和強化學習的混流裝配線平衡與排序方法,結合復合規則對不同問題的適應能力與強化學習對具體問題的學習能力,實現混流裝配線的生產調度。首先構建混流裝配線平衡與排序問題的數學模型,然后分別設計面向混流裝配過程的平衡規則庫與排序規則庫,最后設計近端策略優化(proximal policy optimization, PPO)算法調控復合規則中的參數權重,獲取調度方案。

1 混流裝配線平衡與排序問題

1.1 問題描述

航天產品的混流裝配線具有產品多品種、小批量,批產研制型號混線生產等特點,并且為滿足班組操作需求,裝配過程具有單元式組織的特點。因此,需要在裝配線設計階段實現各個裝配單元之間的負載均衡,保障裝配物流的連續性。隨著批產訂單和研制任務的增加,產能需求出現波動,設計階段形成的裝配單元之間的負載均衡被打破,需要利用裝配單元的人員動態配置與不同產品的投產順序規劃,實現混流裝配過程的再次平衡,即考慮裝配單元容量和工人裝配能力等約束條件,合理安排裝配單元的工人,并考慮航天產品的最小生產集合(minimum part set,MPS)循環,規劃產品的投產順序,形成混流裝配線的平衡與排序解決方案,避免裝配單元出現過載和空閑等情況,實現最小化過載時間和最小化空閑時間的優化目標。根據以上生產特點,本文對航天產品混流裝配線平衡與排序問題提出以下假設:

(1)工件以固定節拍進行投產;

(2)根據設計階段的裝配任務量,各裝配單元具有相同的傳送距離;

(3)工人為多能工,能完成多種產品的各項裝配任務;

(4)裝配單元是封閉的,工人不能在裝配單元之間移動;

(5)裝配單元內的工人共同完成裝配任務;

(6)各裝配單元可分配人數固定,工人裝配能力存在差異,工人的裝配能力影響產品在該單元的裝配時間;

(7)過載工作由裝配單元內的工人完成;

(8)過載工作對當前裝配單元及下一個裝配單元產生影響。

1.2 數學模型

混流裝配線平衡與排序問題的數學模型如下所示,其中的數學符號如表1所示。

表1 混流裝配線平衡與排序問題的數學符號

(1)

s.t.

(2)

(3)

(4)

(5)

p′ik=pikQk?k

(6)

snk=en(k-1)-c

(7)

enk=snk+p′ik

(8)

uik=max[0,min(snk+p′ik-lk,lk-c)]

(9)

oik=min(0,T-enk)

(10)

式(1)給出了在航天產品混流裝配線平衡與排序問題的目標函數——最小化的過載時間和空閑時間。裝配單元的工人班組在設計的節距長度內不能完成裝配任務時,需要臨時延長裝配時間以完成過載工作量,這可能會造成其他裝配單元的工作延誤,并增加潛在的裝配質量風險。裝配單元的工人班組提前完成裝配任務時,由于裝配單元的封閉性限制,工人只能等待,這造成了裝配能力的浪費,因此需要同時避免裝配單元的過載和空閑。式(2)表示由于航天產品的復雜性與尺寸限制,投產序列中的任意位置有且僅有一個待裝配產品,即在每個生產節拍中,每個裝配單元里僅有一個航天產品被執行裝配操作。式(3)表示MPS中的所有產品都被安排到裝配線上進行裝配,即各個裝配單元需要順次完成一個MPS的產品裝配任務。式(4)表示裝配線中的所有工人都被安排到裝配單元中,以實現工人裝配能力的充分利用。式(5)表示根據工人分配結果,計算各個裝配單元上的裝配時間系數。式(6)表示根據裝配時間系數,計算各類型產品在裝配單元上的實際裝配時間。式(7)、式(8)分別表示投產序列中第n個產品在裝配單元k上的裝配起始時間和裝配結束時間。式(9)、式(10)分別表示投產序列中第n個產品在裝配單元k上產生的過載時間和空閑時間。

2 混流裝配線平衡與排序方法

針對以上約束條件與優化目標,航天產品混流裝配線平衡與排序方法首先構建面向復合規則的平衡規則庫與排序規則庫,然后設計PPO算法對復合規則中的權值參數進行動態調整,根據復合規則生成平衡方案與排序方案,并計算目標函數(式(1)),對平衡與排序結果進行評價,如圖1所示。

圖1 基于復合規則和強化學習的混流裝配線調度方法

2.1 平衡與排序規則庫

2.1.1平衡規則庫

在平衡過程中,綜合考慮整體裝配效率目標和工人裝配能力分布[12],對裝配單元上的工人配置設計以下規則。

規則b2：選擇在裝配單元上能力水平最高的工人w*,即滿足w*=argmaxqwk。

規則b3：選擇與瓶頸裝配單元能力水平之差最大的工人w*,即滿足w*=argmax(|qwk-qwkb|)。

規則b4：將工人w*分配至裝配單元。

2.1.2排序規則庫

排序過程中,綜合考慮裝配單元的操作時間和生產循環的產品需求分布[13],對裝配線的投產排序設計以下規則。

規則s4：將產品類型i*投產到裝配線。

2.2 近端策略優化算法

如圖2所示,在平衡規則庫與排序規則庫基礎上,PPO算法中的平衡智能體與排序智能體分別觀察混流裝配線的環境狀態Sb和Ss,輸出復合規則中的規則權重參數,并根據復合規則生成包括平衡調度與排序調度的馬爾可夫決策過程,計算平衡與排序階段的獎勵回報函數rb和rs。以歷史經驗為樣本數據,PPO算法設計如下的損失函數:

圖2 基于PPO算法的平衡與排序調度過程

(11)

c(Rt(θ),1-ωclip,1+ωclip)=

分別訓練平衡智能體與排序智能體。改進網絡結構、設計優先經驗回放機制,以提高PPO算法的數據利用率。

2.2.1平衡智能體與排序智能體

強化學習算法中的智能體以最大化累計獎勵為目標,通過感知環境的狀態S、對環境做出的動作A,根據環境的獎勵反饋R進行學習[14-15]。為實現以上過程,平衡智能體與排序智能體采用Actor-Critic網絡結構,其中,平衡智能體構建Actorb網絡和Criticb網絡,排序智能體構建Actors網絡和Critics網絡,利用Actor網絡與Critic網絡的交互,實現合理的裝配單元工人配置與多種產品投產規劃。

考慮平衡智能體與排序智能體的動作在裝配時間、生產節拍等方面的關聯性,在智能體之間設計GRU單元與注意力機制,即在GRU單元中綜合考慮Actor網絡的輸入參數與隱藏狀態,通過不斷更新隱藏狀態,學習平衡過程與排序過程的前后動作關聯信息。同時,運用注意力機制加強對平衡過程與排序過程中關鍵狀態特征的學習,提高網絡學習的能力。

2.2.2平衡與排序的馬爾可夫決策過程

根據混流裝配線平衡與排序問題面臨的約束條件與優化目標,建立平衡與排序的馬爾可夫決策過程(Markovian decision process, MDP)模型,以MDP模型中的狀態S、動作A和獎勵R描述平衡與排序問題的調度要素。

(1)狀態空間。平衡過程中,裝配人員的能力水平和裝配單元的人員配置是關鍵狀態特征。因此,設計平衡智能體的觀測狀態空間

(12)

排序過程中,裝配單元的產品操作時間和裝配任務的開始操作時間是關鍵狀態特征。因此,設計排序智能體的觀測狀態空間

Ss=(p′ik,d′i,snk,lk,T)

(13)

(2)動作空間。根據所設計的平衡規則庫,得到混流裝配線平衡階段復合規則的評價值:

Hbi=ωb1hb1+ωb2hb2+ωb3hb3+ωb4hb4

(14)

式中,ωb1～ωb4為平衡智能體根據當前狀態輸出的規則權重;hb1～hb4為平衡規則b1到b4的評價值。

根據設計的排序規則庫,得到混流裝配線排序階段復合規則的評價值:

Hsi=ωs1hs1+ωs2hs2+ωs3hs3+ωs4hs4

(15)

式中,ωs1～ωs4為排序智能體根據當前狀態輸出的規則權重;hs1～hs4為排序規則b1到b4的評價值。

(3)獎勵函數。根據Actor-Critic算法框架,需要根據平衡與排序方案的評價函數f,對平衡智能體與排序智能體進行訓練。考慮到平衡與排序問題的復雜性與規模性,以上訓練過程會使訓練過程迭代變慢,降低算法收斂速度,因此需要重新設計獎勵函數。平衡過程中,將混流裝配線的過載時間和空閑時間平均分配到每個動作回合,得到平衡階段的獎勵回報函數:

(16)

式中,tb為平衡過程的總步數;C為生產節拍常數。

排序過程中,根據每個排序動作產生的裝配單元過載時間和空閑時間,定義排序階段的獎勵回報函數:

(17)

2.2.3優先經驗回放機制

傳統PPO算法在學習過程中進行歷史樣本的隨機采樣,在面臨優化問題時的學習能力有限[16],因此提出一種優先經驗回放機制,根據平衡與排序問題的目標函數值fi設置經驗樣本i被學習的概率即調度經驗樣本τ的采樣概率

(18)

式中,i為經驗庫中調度經驗樣本τ的編號;T為經驗庫中所包含的調度經驗樣本總數。

通過權重保留較優經驗進行采樣,提高PPO算法的學習效率。

2.2.4算法訓練流程

馬爾可夫決策過程中,平衡智能體、排序智能體分別觀察混流裝配線平衡與排序過程中的狀態空間Sb和Ss,Actorb網絡和Actors網絡輸出復合規則的權重向量,通過集成平衡規則庫與排序規則庫,生成平衡調度方案與排序調度方案,得到式(16)、式(17)所示的獎勵函數。將平衡智能體、排序智能體與混流裝配線環境互動過程中的調度經驗儲存在經驗庫中,當經驗庫達到最大容量時,基于優先經驗回放機制對歷史經驗進行采樣,更新Actor與Critic中的網絡參數分布,并通過經驗回放的不斷迭代,調控優化智能體的動作策略。以上過程中的算法步驟如下:

(1)初始化平衡智能體與排序智能體的Actor-Critic網絡參數θb、θs、ψb、ψs,設置智能體中的迭代最大回合數emax、經驗庫容量z、經驗庫最大容量zmax;

(2)初始化航天產品平衡與排序問題調度環境,設置平衡智能體的工人配置步數tb=0與排序智能體的產品投產步數ts=0;

(3)根據平衡規則庫,平衡智能體觀察環境狀態Sbt,根據策略πθb(abt|Sbt)輸出復合規則權重向量,分配工人w*至裝配單元,更新環境狀態Sbt;

(5)根據排序規則庫,排序智能體觀察環境狀態Sst,根據策略πθs(ast|Sst)輸出排序規則權重向量,選擇產品類型i*進行投產,更新環境狀態Sst,反饋獎勵函數值rst;

(8)更新平衡動作策略網絡πθb(abt|Sbt),排序動作策略網絡πθs(ast|Sst);更新平衡評價網絡vψb(abt,Sbt),排序評價網絡vψs(ast,Sst);更新網絡參數θb、θs、ψb、ψs;

(9)若迭代循環次數達到最大回合數emax,訓練結束,否則重復步驟(2)～步驟(8)。

3 算例驗證

考慮PPO算法參數對復合規則學習過程的影響,結合多品種小批量生產與裝配單元工人配置柔性等特點,首先利用隨機算例進行混流裝配線平衡與排序方法中的算法參數實驗,然后根據文獻[17-18]設計的標準化算例進行不同平衡與排序方法的對比實驗。以上實驗采用Intel i7-10875H CPU,內存16G,Windows11的計算機環境,對比方法包括PPO+單一規則、復合規則和遺傳算法等調度方法。對比算法的具體說明如下:

(1)PPO+單一規則。使用PPO算法訓練強化學習智能體,根據調度狀態選取某條規則作為調度動作來選擇備選工人或產品。

(2)復合規則。使用正交試驗方法設計復合規則的權重,根據復合規則選擇備選的工人或產品。

(3)遺傳算法。采用十進制編碼分別構建平衡過程與排序過程的染色體,平衡過程中的染色體進行循環交叉,排序過程中的染色體進行優先交叉。交叉變異過程采用兩點交換法,通過三元錦標賽法和精英保留策略進行染色體篩選,最后根據染色體編碼情況生成調度方案。

在算法參數實驗中,以面向9種產品類型、包含10個裝配單元的混流裝配線為研究對象,在單元長度100 s、投產節拍為120 s的情況下,根據單元工人容量U[2,3]、產品數量U[4,7]、工人裝配能力U[0.8,1.2]、產品裝配時間U[80 s, 130 s]的分布情況,隨機生成3個算例。通過正交試驗分析以上算例中的PPO算法參數水平,得到PPO算法參數:Actorb的學習率RA,b=5×10-5,Criticb的學習率RC,b=5×10-5;Actorb網絡結構參數為(256,128,128);Criticb網絡結構參數為(256,128,128);Actors的學習率RA,s=5×10-5;Criticb的學習率RA,s=5×10-5;Actors網絡結構參數為(256,128,128);Critics網絡結構參數為(256, 128, 128)。

PPO+單一規則方法與表7所列算法參數設置相同,復合規則方法的權重設置基于三因素五水平的正交試驗,平衡規則的權重wb1=0.25,wb2=0.625,wb3=0.125,排序規則的權重ws1=0.3,ws2=0.5,ws3=0.2;遺傳算法初始種群規模100、交叉率0.8、變異率0.05、迭代次數200。在上述算法參數設置基礎上,根據文獻[17-18]中的生產循環、裝配單元和工人設置,生成標準化算例,采用本文方法和對比方法進行求解,得到混流裝配線調度問題的目標函數值f與方法運算時間即CPU time,結果分別如表2、表3所示。

表2 不同方法的目標函數值結果

表3 不同方法的運算時間

如表2、表3所示,對于工人數量、裝配單元數量、產品種類和產品數量共同決定的混流裝配線平衡與排序問題的大規模解空間,PPO+復合規則方法利用平衡智能體與排序智能體,將多個啟發式規則組合成復合規則,具備較好全局優化能力,并根據調度問題的目標函數設計了獎勵回報函數,建立了基于PPO算法的學習過程,不斷對復合規則中的權值進行動態調控,具備較好的局部適應能力,因此獲得了平衡與排序問題的更優解,并縮短了計算時間。在大規模解空間中,PPO+單一規則方法容易在初始化階段就陷入部分區域,使學習過程傾向于持續選擇某個規則,導致算法過早陷入局部最優。該方法雖然在較短時間內獲得了可行方案,但難以進一步生成更優方案。復合規則采用正交試驗對啟發式規則權重進行有限調整,雖然縮短了參數尋優的計算時間,但對大規模問題的優化十分有限,很難生成符合調度方案優化需求的復合規則,僅能獲得次優解或可行解。遺傳算法需要擴大種群規模、增加迭代次數來滿足大規模解空間的全局搜索需求,但計算時間的大幅度延長,且增大后的種群規模難以形成有效的局部搜索能力,因此對大部分MPS難以獲得近優求解效果。

4 結論

針對多品種小批量、單元制造的航天產品混流裝配線平衡與排序問題,結合復合規則對不同調度問題的適應性與強化學習對調度問題的策略學習能力,提出一種基于復合規則和強化學習的混流裝配線平衡與排序方法。在分析問題特點與數學模型的基礎上,分別設計了平衡規則庫與排序規則庫,提出的強化學習PPO算法對規則組合下的復合規則權重參數進行調控優化,根據復合規則生成混流裝配線平衡與排序方案,最小化裝配單元的過載時間和空閑時間。所提方法與PPO+單一規則、復合規則和遺傳算法的求解效果對比驗證了所提方法的有效性。在此基礎上,后續研究將關注混流裝配線調度問題特點與PPO算法中復合規則權重分布的可解釋性映射關系,進一步挖掘混流裝配線平衡與排序方法中存在的調度機理。