劉 鋒， 徐 杰,2， 柯文博

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

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

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

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

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

1 強(qiáng)化學(xué)習(xí)基本原理

1.1 強(qiáng)化學(xué)習(xí)與Q-learning方法

強(qiáng)化學(xué)習(xí)是一種機(jī)器學(xué)習(xí)算法，其通?；隈R爾科夫決策過程進(jìn)行建模。馬爾科夫決策過程是順序決策的數(shù)學(xué)模型,通常采用四元組[S,A,R,P]來表示。在決策時(shí)間點(diǎn)t,st∈S代表當(dāng)前狀態(tài);at∈A,代表在t時(shí)刻所采取的動(dòng)作;P(st+1,rt+1|st,at)∈P,表示狀態(tài)st時(shí)采取動(dòng)作at轉(zhuǎn)移到狀態(tài)st+1以及獲得相應(yīng)即時(shí)獎(jiǎng)勵(lì)rt+1概率。

強(qiáng)化學(xué)習(xí)的目標(biāo)是使智能體在與環(huán)境交互過程中找到一個(gè)最優(yōu)策略。在此，策略π(a|s)是指狀態(tài)到動(dòng)作的映射，如果從狀態(tài)s一直遵循最優(yōu)策略π*，能獲得最大累積獎(jiǎng)勵(lì)的期望。通常，狀態(tài)s在策略π的指導(dǎo)下，所能獲得的累積獎(jiǎng)勵(lì)的期望用狀態(tài)價(jià)值函數(shù)Vπ(s)=E[rt+1+γrt+2+γ2rt+3+…|st=s]表示或狀態(tài)動(dòng)作價(jià)值函數(shù)Qπ(s,a)=E[rt+1+γrt+2+γ2rt+3+…|st=s,at=a]來表示。其中，γ∈[0,1]，是為了區(qū)分短期獎(jiǎng)勵(lì)與長期獎(jiǎng)勵(lì)之間的相對重要性。Vπ(s)和Qπ(s,a)之間的關(guān)系可用式(1)和(2)描述：

(1)

(2)

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

(3)

(4)

標(biāo)準(zhǔn)的Q-learning方法即基于貝爾曼最優(yōu)方程演化而來[11]。

1.2 DQN與DDQN算法

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

2 服裝縫制調(diào)度問題的描述

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

同時(shí)，基于服裝加工特點(diǎn)以及生產(chǎn)現(xiàn)狀，做出以下假設(shè)：1)1個(gè)工位同一時(shí)間只能縫制1件服裝；2)由于現(xiàn)有服裝縫制生產(chǎn)大多基于吊掛系統(tǒng)，工序之間物流傳遞時(shí)間固定，將物流傳遞時(shí)間以及加工準(zhǔn)備時(shí)間直接計(jì)入加工時(shí)間；3)工序之間有充足的緩沖區(qū)。

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

表1 模型參數(shù)說明

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

(5)

(6)

(7)

(8)

(9)

(10)

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

3 基于深度強(qiáng)化學(xué)習(xí)的調(diào)度方法

將深度強(qiáng)化學(xué)習(xí)方法應(yīng)用于服裝縫制生產(chǎn)調(diào)度，首先需要通過定義狀態(tài)、動(dòng)作、獎(jiǎng)勵(lì)、探索和利用方法等將調(diào)度問題轉(zhuǎn)化為一個(gè)順序決策問題。然后，利用本文采用的DDQN算法基于過往生產(chǎn)數(shù)據(jù)訓(xùn)練調(diào)度策略。最后將該調(diào)度策略用于解決加工任務(wù)動(dòng)態(tài)到達(dá)的服裝縫制過程調(diào)度問題。本文提出的方法框架如圖1所示。

圖1 基于深度強(qiáng)化學(xué)習(xí)的服裝縫制過程實(shí)時(shí)動(dòng)態(tài)調(diào)度方法總體框架

3.1 狀態(tài)特征

狀態(tài)特征是對狀態(tài)變量的數(shù)值表征，用于描述調(diào)度環(huán)境的狀況及其變化。本文將任意時(shí)刻的狀態(tài)以2張二維結(jié)構(gòu)表格和1張一維結(jié)構(gòu)表格進(jìn)行表達(dá),并抽取特征(見圖1)。

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

(11)

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

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

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

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

3.2 動(dòng)作空間

啟發(fā)式規(guī)則能夠有效且快速地解決特定的調(diào)度問題，但任何規(guī)則在所有的生產(chǎn)狀態(tài)下不可能均取得良好效果，因此，根據(jù)不同的生產(chǎn)狀態(tài)應(yīng)選擇不同的調(diào)度規(guī)則。本文構(gòu)建了由16項(xiàng)規(guī)則組成的動(dòng)作空間(見表2)，所學(xué)習(xí)出的最佳策略會依據(jù)不同的狀態(tài)選擇相應(yīng)的規(guī)則，依據(jù)該規(guī)則從待加工服裝中進(jìn)行挑選并加工，最終實(shí)現(xiàn)最小化生產(chǎn)周期的目標(biāo)。

表2 候選動(dòng)作集

3.3 獎(jiǎng)勵(lì)函數(shù)

獎(jiǎng)勵(lì)函數(shù)的設(shè)計(jì)與調(diào)度目標(biāo)密切相關(guān)，但在調(diào)度規(guī)?；虍a(chǎn)品不同的情況下，生產(chǎn)周期差距巨大，故無法直接利用生產(chǎn)周期作為獎(jiǎng)勵(lì)函數(shù)的構(gòu)成依據(jù)。而生產(chǎn)周期與機(jī)器利用率密切相關(guān)，在約束條件不變的情況下，生產(chǎn)周期越短的工位(設(shè)備)平均利用率越高[14-15]，因此，本文直接利用所有加工任務(wù)加工完成后的工位平均利用率，作為學(xué)習(xí)過程的總獎(jiǎng)勵(lì)，如式(12)所示。

(12)

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

3.4 探索與利用

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

(13)

式中，ε并非固定值。在學(xué)習(xí)初期對環(huán)境的認(rèn)知較低，需要加大對環(huán)境的探索，而在學(xué)習(xí)中后期需要利用已知環(huán)境信息最大的提升獎(jiǎng)勵(lì)，因此，本文中ε將按下式進(jìn)行變化:

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

(14)

式中：εmax為能達(dá)到的最大ε值，本文中設(shè)為0.95；eiter為當(dāng)前的學(xué)習(xí)次數(shù)；Nepisode為設(shè)定的總學(xué)習(xí)次數(shù)。

3.5 算法框架

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

表3 基于DDQN訓(xùn)練算法框架

4 實(shí)例仿真

4.1 參數(shù)設(shè)置與模型訓(xùn)練

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

圖2 調(diào)度方案

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

本文所提出的方法在 python 3.6中進(jìn)行編程,計(jì)算環(huán)境為AMD Ryzen 7 4800 H@ 2.9 GHz CPU，16 GB RAM，windows10系統(tǒng)。其中，深度神經(jīng)網(wǎng)絡(luò)部分使用Keras進(jìn)行搭建，該網(wǎng)絡(luò)輸入層的設(shè)置如3.1節(jié)所述，另外包含全連接隱含層4層，每層的神經(jīng)元個(gè)數(shù)分別為512、512、256、128, 激活函數(shù)為softplus，輸出層含16個(gè)神經(jīng)元對應(yīng)16個(gè)動(dòng)作，損失函數(shù)為mean_squared_error，優(yōu)化器為Adam，網(wǎng)絡(luò)參數(shù)采取隨機(jī)初始化策略。訓(xùn)練樣本從歷史生產(chǎn)數(shù)據(jù)中進(jìn)行選取，訓(xùn)練時(shí)采用20個(gè)加工任務(wù)作為訓(xùn)練樣本。前6 000次訓(xùn)練過程中工位利用率如圖3所示。可以看出，工位利用率曲線隨著訓(xùn)練次數(shù)增加而逐漸平穩(wěn)，表明所訓(xùn)練的Q值網(wǎng)絡(luò)已經(jīng)有效地學(xué)會在不同情況下選取適當(dāng)?shù)恼{(diào)度規(guī)則。

圖3 訓(xùn)練過程工位利用率變化

4.2 仿真結(jié)果及分析

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

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

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

5 結(jié) 論

本文針對現(xiàn)有服裝生產(chǎn)調(diào)度過程中面對動(dòng)態(tài)事件自適應(yīng)性能差，以及實(shí)時(shí)響應(yīng)能力差的問題，提出基于深度強(qiáng)化學(xué)習(xí)的服裝縫制過程動(dòng)態(tài)調(diào)度方法。由于強(qiáng)化學(xué)習(xí)本身基于馬爾科夫決策過程，相較于現(xiàn)有服裝生產(chǎn)調(diào)度過程中所采用的啟發(fā)式算法或元啟發(fā)式算法，該方法具有更高的動(dòng)態(tài)性和實(shí)時(shí)性。實(shí)驗(yàn)表明，針對牛仔褲前片縫制過程，所提出的方法相較于遺傳算法，在調(diào)度目標(biāo)的達(dá)成度方面略遜2.3%，但決策時(shí)間大幅減少91.4%。該結(jié)果表明，針對訂單動(dòng)態(tài)到達(dá)的調(diào)度問題，該方法能夠?qū)崿F(xiàn)有效的實(shí)時(shí)響應(yīng)，確保了縫制生產(chǎn)的高效性與連續(xù)性。