基于深度強化學習的服裝縫制過程實時動態調度

劉 鋒， 徐 杰,2， 柯文博

1. 武漢紡織大學 紡織科學與工程學院， 湖北 武漢 430200； 2. 武漢紡織大學 省部共建紡織新材料與先進加工技術國家重點實驗室， 湖北 武漢 430200； 3. 廣東前進牛仔布有限公司， 廣東 佛山 528000)

服裝制造業是我國國民經濟的重要組成部分，伴隨國內生產成本的上升，我國服裝產業已進入提質增效的關鍵時期。同時，服裝生產需求也在發生著深刻的變化。由于客戶的個性化需求增加以及品牌商為避免存貨和滯銷成本，現今的服裝生產需求已明顯由過往的少品種、大規模轉為多品種、小批量、短交期，這對服裝生產企業的柔性生產以及快速響應能力提出了挑戰。應對上述挑戰最為直接的方法是對生產設備進行革新，采用新型柔性化設備。但一方面，由于投資費用與生產利潤的相互制約，導致實際生產過程中設備更新緩慢；另一方面，新型設備所帶來的效率提升也存在瓶頸，且不少企業由于管理水平有限，存在無法充分有效利用設備資源的問題。生產調度方法是通過將現有的制造資源進行有效合理地分配，從而實現生產能力提升[1]，且該方法極具經濟性[2]，更符合我國以中小企業為主的服裝制造類企業的實際需求。

在現有條件下，有效的生產調度方法可作為提升服裝制造業競爭力的核心技術之一。在過往數十年，有眾多生產調度方法被提出，但大多數基于靜態生產環境的假設，即車間制造信息事先完全已知且不會發生變化。然而，由于現有服裝生產過程中存在大量插單返單、訂單到達時間隨機、加工人員流動、設備故障等動態因素，對已有調度方案產生干擾，使生產安排與生產實際嚴重脫離，造成生產混亂。為提升服裝生產企業對動態事件的響應能力，確保生產的高效性、穩定性與連續性，動態調度方法成為現今的研究重點。

過往的生產調度算法研究主要分為精確算法和近似算法。精確算法，例如分枝定界法，能確保求出最優調度方案，但難以應對NP-hard問題，較少運用于生產實際。而近似算法能求出近優或最優解，且適用于中大規模問題，成為該領域的研究熱點。元啟發式算法和啟發式算法是研究和應用較多的二大類近似方法。其中，元啟發式算法能適用于多種類型問題求解，并能提供較好質量的解。在服裝生產調度領域，遺傳算法[3]作為一種通過模擬達爾文自然進化過程的元啟發式算法得到廣泛運用。鄭衛波等[4]通過遺傳算法求解服裝生產調度模型，實現了減少訂單總體拖期時間的目標；謝子昂等[5]利用遺傳算法結合滾動窗機制解決了服裝吊掛流水線的動態調度問題。然而，該類算法計算量會隨著問題規模呈指數增長，面對中大規模動態調度問題無法實時響應。相對而言，啟發式算法(如NEH算法[6])源自專家知識或經驗，能有效且快速地解決特定的調度問題[7]，但該類方法是基于特定條件而歸納出來的算法，相同的算法在不同條件下會有迥然不同的表現。動態調度本質上是順序決策問題，通常形式化為馬爾科夫決策過程，其從問題的順序中間狀態確定一系列最優決策以實現優化目標。由于中間狀態不斷變化，單一啟發式算法顯然無法一直提供最優解。

隨著人工智能技術的快速發展，強化學習方法近年來得到廣泛關注，并應用于包括智能調度在內的各類決策問題[8-10]。強化學習本身基于馬爾可夫決策過程，由智能體與環境的不斷交互過程中逐步完善策略，目標是實現最大的長期獎勵。在服裝生產動態調度問題中，啟發式調度規則可被視為強化學習中的可選動作，通過與環境不斷交互所構建的策略(本質上是一個啟發式調度規則的自適應選擇器)，可實時有效地響應生產狀態的變化，最終達到調度目標。為此，本文面向服裝的縫制生產過程，以最小化最大完工周期為目標，提出利用深度強化學習算法對縫制生產過程進行實時動態調度，以期提升縫制生產的高效性和連續性。

1 強化學習基本原理

1.1 強化學習與Q-learning方法

強化學習是一種機器學習算法，其通?；隈R爾科夫決策過程進行建模。馬爾科夫決策過程是順序決策的數學模型,通常采用四元組[S,A,R,P]來表示。在決策時間點t,st∈S代表當前狀態;at∈A,代表在t時刻所采取的動作;P(st+1,rt+1|st,at)∈P,表示狀態st時采取動作at轉移到狀態st+1以及獲得相應即時獎勵rt+1概率。

強化學習的目標是使智能體在與環境交互過程中找到一個最優策略。在此，策略π(a|s)是指狀態到動作的映射，如果從狀態s一直遵循最優策略π*，能獲得最大累積獎勵的期望。通常，狀態s在策略π的指導下，所能獲得的累積獎勵的期望用狀態價值函數Vπ(s)=E[rt+1+γrt+2+γ2rt+3+…|st=s]表示或狀態動作價值函數Qπ(s,a)=E[rt+1+γrt+2+γ2rt+3+…|st=s,at=a]來表示。其中，γ∈[0,1]，是為了區分短期獎勵與長期獎勵之間的相對重要性。Vπ(s)和Qπ(s,a)之間的關系可用式(1)和(2)描述：

(1)

(2)

將式(1)代入式(2)，可得到貝爾曼期望方程

(3)

(4)

標準的Q-learning方法即基于貝爾曼最優方程演化而來[11]。

1.2 DQN與DDQN算法

由于標準的Q-learning利用表格法存儲和查詢狀態-動作的Q值，因此，僅能處理具有離散及有限狀態的問題。為解決該不足，Mnih等[12]提出Deep Q-network(DQN)算法，即利用深度神經網絡來擬合狀態特征與各動作的Q值之間的對應關系，從而能處理大型且連續的復雜問題。由于標準DQN算法在最大Q值確定過程中，評估和選擇均采用同一網絡進行，易造成對Q值的過估計。Van等[13]提出Double DQN(DDQN)算法，該算法體系與DQN算法基本相同，只是對最大Q值的評估過程采用正在更新的網絡，而選擇過程采用目標網絡，因此，該過程所選出的最大Q值一定小于或等于標準DQN算法所選擇的值，從而減少過估計，更接近真實Q值。本文即采用DDQN算法框架建立Q值網絡，并據此在決策節點選擇最合適的調度規則。

2 服裝縫制調度問題的描述

在服裝縫制生產中，當縫制線調整完畢后，主要加工同一類型服裝，即具有相似加工順序的服裝，而同類型不同款式服裝在加工過程中，主要體現為各工序加工時間不同。本文縫制生產調度問題可描述為：n件服裝需要在m道工序上進行順序加工，每個工序有x個并行加工工位，調度的目的是確定所有待加工服裝的加工順序及其在各工序并行工位上的分配方案，以達到生產調度目標。

同時，基于服裝加工特點以及生產現狀，做出以下假設：1)1個工位同一時間只能縫制1件服裝；2)由于現有服裝縫制生產大多基于吊掛系統，工序之間物流傳遞時間固定，將物流傳遞時間以及加工準備時間直接計入加工時間；3)工序之間有充足的緩沖區。

本文以最小化最大完工時間f為調度目標(見式(5)，最大完工時間是指所有服裝加工完成的時間)，根據生產實際及其相應約束條件建立混合整數規劃模型，所涉及的相關模型參數描述見表1。

表1 模型參數說明

Min:f=(maxCi,m|i=1,2,…,n)

(5)

(6)

(7)

(8)

(9)

(10)

式(6)表示每道工序只能由唯一1個并行工位完成；式(7)表示此工序的開始時間不能早于上一工序的結束時間；式(8)表示第一工序的開始時間不能早于加工任務的下達時間；式(9)確保任意時刻，在任一工序上加工的服裝總數不能超過該工序上的并行工位數；式(10)表示縫制過程不能中斷，在相同工位上，后一順位所加工的服裝不能插入前一順位的加工過程。

3 基于深度強化學習的調度方法

將深度強化學習方法應用于服裝縫制生產調度，首先需要通過定義狀態、動作、獎勵、探索和利用方法等將調度問題轉化為一個順序決策問題。然后，利用本文采用的DDQN算法基于過往生產數據訓練調度策略。最后將該調度策略用于解決加工任務動態到達的服裝縫制過程調度問題。本文提出的方法框架如圖1所示。

圖1 基于深度強化學習的服裝縫制過程實時動態調度方法總體框架

3.1 狀態特征

狀態特征是對狀態變量的數值表征，用于描述調度環境的狀況及其變化。本文將任意時刻的狀態以2張二維結構表格和1張一維結構表格進行表達,并抽取特征(見圖1)。

1)加工中服裝各工序加工時間表(A表)：該表橫坐標表示加工工序，縱坐標表示正在加工的服裝，縱坐標從上至下的排列順序表示服裝的加工順序，表中數據為歸一化后的不同服裝在各工序上的加工時間。歸一化的目的是為了避免神經網絡不同輸入之間的尺度相差過大，造成影響力不同，歸一化依據式(11)進行。

(11)

式中：x為原數據；xmax、xmin分別為原數據中的最大與最小值；xscale為歸一化后的數據。

2)加工中服裝各工序預估完工時間表(B表)：此表表示根據已安排加工服裝排序及工位分配方案，所計算出的每個工序的完工時刻。該表中橫縱坐標與A表相同，表中數據為歸一化后不同服裝在各工序上的預估完工時刻，該完工時刻可通過生產中實際完工時刻進行實時修正。

3)各加工設備的預估利用率(C表)：該表中設備利用率是指，從當前決策時刻t開始，到當前所有正在加工中的服裝在工位M上預計全部完成的時刻tM之間的利用率，即利用率UM=TM/tM-t。其中TM是指t-tM時間段內設備的使用時間。

針對A表和B表，分別利用不同尺寸的一維卷積核，包括2×m、3×m、4×m，來提取相鄰工序和相鄰加工任務之間不同尺度上的關聯特性，并將生成的卷積特征做最大池化處理，最后與C表中數據相結合作為狀態特征(見圖1)。相對于直接利用表中數據進行描述，該方法自適應挖掘特征能力更強，在應用中具有更好的泛化效果。

3.2 動作空間

啟發式規則能夠有效且快速地解決特定的調度問題，但任何規則在所有的生產狀態下不可能均取得良好效果，因此，根據不同的生產狀態應選擇不同的調度規則。本文構建了由16項規則組成的動作空間(見表2)，所學習出的最佳策略會依據不同的狀態選擇相應的規則，依據該規則從待加工服裝中進行挑選并加工，最終實現最小化生產周期的目標。

表2 候選動作集

3.3 獎勵函數

獎勵函數的設計與調度目標密切相關，但在調度規?；虍a品不同的情況下，生產周期差距巨大，故無法直接利用生產周期作為獎勵函數的構成依據。而生產周期與機器利用率密切相關，在約束條件不變的情況下，生產周期越短的工位(設備)平均利用率越高[14-15]，因此，本文直接利用所有加工任務加工完成后的工位平均利用率，作為學習過程的總獎勵，如式(12)所示。

(12)

式中：ti,j表示第i件服裝在第j工序的加工時間；Mtotal表示縫制線上總工位數；Cmax為最大完工周期。

3.4 探索與利用

探索(exploration)的目的是找到更多有關環境的信息，挖掘可能獲取更大Q值的動作。而利用exploitation是在已知的最優策略的基礎上，直接選Q值最大動作，用以最大限度地提高獎勵。為平衡探索與利用之間的分配，本文采用ε-greedy算法，即1-ε的概率隨機從動作空間中選取動作，以ε的概率從中選取已知Q值最大的動作a：

(13)

式中，ε并非固定值。在學習初期對環境的認知較低，需要加大對環境的探索，而在學習中后期需要利用已知環境信息最大的提升獎勵，因此，本文中ε將按下式進行變化:

ε=εmaxmin(1，2eiter/Nepisode)

(14)

式中：εmax為能達到的最大ε值，本文中設為0.95；eiter為當前的學習次數；Nepisode為設定的總學習次數。

3.5 算法框架

本文訓練方法是基于DDQN算法框架，在訓練過程中，新加工任務可隨時加入待排任務組中，每當首加工工序中有工位出現空閑時被定義為決策時刻t，在該時刻從待排任務組中選擇一件服裝進入加工過程。整體算法框架如表3所示。

表3 基于DDQN訓練算法框架

4 實例仿真

4.1 參數設置與模型訓練

本文以牛仔褲前片縫制為例，按工藝流程分解為順次的15個工序，為保證流水線各工序生產平衡，每工序上有1～3個等速加工工位，如表4及圖1所示。對表中前7款牛仔褲的前片加工任務進行調度，所生成的調度方案如圖2(a)所示。

圖2 調度方案

表4 牛仔褲前片縫制流程及不同款式加工時間

本文所提出的方法在 python 3.6中進行編程,計算環境為AMD Ryzen 7 4800 H@ 2.9 GHz CPU，16 GB RAM，windows10系統。其中，深度神經網絡部分使用Keras進行搭建，該網絡輸入層的設置如3.1節所述，另外包含全連接隱含層4層，每層的神經元個數分別為512、512、256、128, 激活函數為softplus，輸出層含16個神經元對應16個動作，損失函數為mean_squared_error，優化器為Adam，網絡參數采取隨機初始化策略。訓練樣本從歷史生產數據中進行選取，訓練時采用20個加工任務作為訓練樣本。前6 000次訓練過程中工位利用率如圖3所示?？梢钥闯?，工位利用率曲線隨著訓練次數增加而逐漸平穩，表明所訓練的Q值網絡已經有效地學會在不同情況下選取適當的調度規則。

圖3 訓練過程工位利用率變化

4.2 仿真結果及分析

利用已訓練出的模型對加工過程進行調度，調度目標為總加工周期最小。圖2(a)所示的表4中前7款牛仔褲的最大完工周期為1 038 s。整個決策過程是在決策點(首工序有空余工位時)，分7次逐步選取下一項需加工款式，每次決策時間約為85 ms，總決策時間為595 ms(7×85 ms)。

本文利用在服裝生產調度研究中常用的遺傳算法進行對比，遺傳算法對該問題調度的最大完工周期為1 014 s，略優于本文所提出方法(采用遺傳算法所求得最大完工周期比本文方法短約2.3%)，但遺傳算法的總決策時間為6.9 s(迭代800次)，明顯劣于本文方法(采用遺傳算法的決策時間是本文方法的10.6倍，本文方法決策時間大幅減少91.4%)，且遺傳算法由于求解過程中存在隨機性，并不能保證每次求解均能達到該優化水平。另外，遺傳算法的決策時間會隨著所需排產任務數量的增加而大幅增長，例如排產加工50個款式約需59.1 s決策(迭代800次)，而本文方法每次決策點的決策時間基本沒有較大變化。

同時，本文考慮了訂單動態到達的情況，假設前7款任務開始加工100 s后，表4中第8款服裝的加工訂單到達，排產目標依然為總加工周期最小，采用本文方法調度方案(見圖2(b))得到所有加工任務最大完工時間為1 080 s。加工任務的動態到達未對本文所提出方法的決策過程產生明顯影響，依然是在決策點進行決策，選擇下一項任務進入加工過程。而采取遺傳算法等元啟發式算法，需在加工任務達到時或滾動窗口激活時，對包含新到任務在內的未開始加工的任務進行重新安排，當任務量較大時無法實現實時響應。

5 結 論

本文針對現有服裝生產調度過程中面對動態事件自適應性能差，以及實時響應能力差的問題，提出基于深度強化學習的服裝縫制過程動態調度方法。由于強化學習本身基于馬爾科夫決策過程，相較于現有服裝生產調度過程中所采用的啟發式算法或元啟發式算法，該方法具有更高的動態性和實時性。實驗表明，針對牛仔褲前片縫制過程，所提出的方法相較于遺傳算法，在調度目標的達成度方面略遜2.3%，但決策時間大幅減少91.4%。該結果表明，針對訂單動態到達的調度問題，該方法能夠實現有效的實時響應，確保了縫制生產的高效性與連續性。