賀俊杰，張 潔+，張 朋，鄭 鵬，王 明

(1.東華大學(xué) 機(jī)械工程學(xué)院，上海 201620；2.上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院，上海 200240)

0 引言

紡織產(chǎn)業(yè)是我國(guó)國(guó)民經(jīng)濟(jì)的支柱產(chǎn)業(yè)之一[1]，面對(duì)競(jìng)爭(zhēng)日益激烈的市場(chǎng)環(huán)境和多品種小批量的個(gè)性化定制生產(chǎn)需求，通過(guò)生產(chǎn)調(diào)度優(yōu)化提高產(chǎn)品準(zhǔn)時(shí)交付率是提升企業(yè)競(jìng)爭(zhēng)力的有效措施。紡織面料的生產(chǎn)由織造和染整兩個(gè)階段組成，其中染整階段又包括前處理、染色和后處理等工藝。染色工序由于耗時(shí)長(zhǎng)，通常被視為紡織品生產(chǎn)管控的關(guān)鍵環(huán)節(jié)，也是制約產(chǎn)品訂單準(zhǔn)時(shí)交付的瓶頸所在。通過(guò)對(duì)染色車間生產(chǎn)過(guò)程進(jìn)行調(diào)度優(yōu)化以降低產(chǎn)品的拖期交付，對(duì)提升企業(yè)的競(jìng)爭(zhēng)力具有重要意義。

根據(jù)染色工藝特點(diǎn)，染色車間的調(diào)度問(wèn)題可拆分為訂單組批和排缸兩個(gè)子問(wèn)題，且需要考慮機(jī)器容量限制與不相容工件族等約束，該問(wèn)題已被證明為NP-Hard問(wèn)題[2]。此外，實(shí)際的染色生產(chǎn)以訂單為驅(qū)動(dòng)，染色任務(wù)隨著訂單動(dòng)態(tài)到達(dá)。通過(guò)調(diào)研發(fā)現(xiàn)，染色車間存在染色回修、緊急訂單、改色漂染等突發(fā)緊急任務(wù)，緊急任務(wù)的擾動(dòng)會(huì)影響生產(chǎn)進(jìn)程和降低生產(chǎn)效率。因此，本文將染色車間調(diào)度問(wèn)題抽象為具有不相容加工族和不同的染缸容量約束，考慮任務(wù)動(dòng)態(tài)到達(dá)的并行批處理機(jī)調(diào)度問(wèn)題，并通過(guò)最小化總拖期時(shí)間來(lái)減少產(chǎn)品的拖期交付。

近年來(lái)，已有眾多學(xué)者針對(duì)染色車間調(diào)度問(wèn)題展開(kāi)研究，且現(xiàn)有的研究以靜態(tài)調(diào)度問(wèn)題為主，主要方法包括數(shù)學(xué)規(guī)劃方法和智能優(yōu)化算法[2-7]。隨著紡織企業(yè)向小批量個(gè)性化定制和面向訂單驅(qū)動(dòng)的生產(chǎn)模式轉(zhuǎn)型，車間調(diào)度的動(dòng)態(tài)事件頻率增加，這對(duì)調(diào)度算法在動(dòng)態(tài)生產(chǎn)環(huán)境下的自適應(yīng)響應(yīng)能力提出了更高的要求。動(dòng)態(tài)環(huán)境下的調(diào)度策略主要包括魯棒調(diào)度、預(yù)—反應(yīng)式調(diào)度和完全反應(yīng)式調(diào)度3類[8-9]。由于染色車間動(dòng)態(tài)事件發(fā)生頻率較高，頻繁的預(yù)—反應(yīng)式重調(diào)度不利于生產(chǎn)過(guò)程的穩(wěn)定性，魯棒調(diào)度以犧牲調(diào)度性能為代價(jià)提高魯棒性，且不能對(duì)動(dòng)態(tài)事件進(jìn)行響應(yīng)，而以各類啟發(fā)式規(guī)則為代表的完全反應(yīng)式調(diào)度方法更適用于染色車間動(dòng)態(tài)事件頻發(fā)的生產(chǎn)環(huán)境[10]。但現(xiàn)有的啟發(fā)式調(diào)度規(guī)則均基于特定的動(dòng)態(tài)場(chǎng)景設(shè)計(jì)，缺乏自適應(yīng)調(diào)整能力。隨著機(jī)器學(xué)習(xí)技術(shù)的快速發(fā)展，其中的強(qiáng)化學(xué)習(xí)方法可通過(guò)學(xué)習(xí)生成復(fù)雜的調(diào)度策略，具有較強(qiáng)的自適應(yīng)和學(xué)習(xí)能力，被廣泛應(yīng)用于各類實(shí)際調(diào)度問(wèn)題中。張東陽(yáng)等[11]應(yīng)用Q-Learning強(qiáng)化學(xué)習(xí)算法求解置換流水車間調(diào)度問(wèn)題；肖鵬飛等[12]提出了基于深度強(qiáng)化學(xué)習(xí)的非置換流水車間調(diào)度算法并改進(jìn)了網(wǎng)絡(luò)輸出層；WANG等[13]將Actor-Critic算法用于晶圓制造系統(tǒng)調(diào)度，對(duì)多目標(biāo)采用加權(quán)的獎(jiǎng)勵(lì)函數(shù)；ZHANG等[14]將Q-Learning強(qiáng)化學(xué)習(xí)算法應(yīng)用于小規(guī)模的批調(diào)度問(wèn)題。近年來(lái)提出的近端策略優(yōu)化(Proximal Policy Optimization, PPO)算法[15]是一種基于策略的深度強(qiáng)化學(xué)習(xí)算法，該算法交互的經(jīng)驗(yàn)數(shù)據(jù)可重復(fù)利用，使得其采樣效率更高，該算法獨(dú)有的損失函數(shù)裁剪使得該算法學(xué)習(xí)穩(wěn)定性更強(qiáng)，在交通[16-17]、機(jī)器人[18-20]、車間調(diào)度[21-22]等智能控制領(lǐng)域得到了實(shí)際應(yīng)用，且明顯優(yōu)于策略梯度(Policy Gradient, PG)[23]、信任區(qū)域策略優(yōu)化(Trust Region Policy Optimization, TRPO)[24]、優(yōu)勢(shì)動(dòng)作評(píng)論(Advantage Actor Critic, A2C)[25]等深度強(qiáng)化學(xué)習(xí)算法。但在現(xiàn)有基于PPO的車間調(diào)度方法中均為獨(dú)立的智能體，如何針對(duì)組批和排缸兩階段的染色車間調(diào)度使用多個(gè)PPO智能體協(xié)作調(diào)度，并提升任務(wù)動(dòng)態(tài)到達(dá)的響應(yīng)能力，是將PPO算法應(yīng)用于染色車間調(diào)度問(wèn)題的難點(diǎn)所在。

綜上所述，當(dāng)前研究以靜態(tài)調(diào)度為主，無(wú)法滿足生產(chǎn)轉(zhuǎn)型帶來(lái)的快速響應(yīng)需求，傳統(tǒng)的強(qiáng)化學(xué)習(xí)調(diào)度方法[26]在優(yōu)化調(diào)度目標(biāo)時(shí)只關(guān)注了車間的實(shí)時(shí)信息而缺乏對(duì)歷史動(dòng)態(tài)信息的考慮。因此，本文在現(xiàn)有染色車間調(diào)度研究和PPO強(qiáng)化學(xué)習(xí)算法的基礎(chǔ)上，針對(duì)任務(wù)動(dòng)態(tài)到達(dá)的染色車間調(diào)度問(wèn)題，以最小化總拖期時(shí)間為目標(biāo)，設(shè)計(jì)具有組批智能體和排缸智能體的多智能體循環(huán)近端策略優(yōu)化(Multi-Agent Recurrent Proximal Policy Optimization, MA-RPPO)強(qiáng)化學(xué)習(xí)算法。針對(duì)車間復(fù)雜約束和調(diào)度目標(biāo)，抽取車間關(guān)鍵參數(shù)并設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù)，將染色車間調(diào)度問(wèn)題轉(zhuǎn)化為序列決策問(wèn)題；為多智能體引入長(zhǎng)短期記憶網(wǎng)絡(luò)(Long Short Term Memory network, LSTM)的記憶與預(yù)測(cè)功能，實(shí)現(xiàn)車間動(dòng)態(tài)信息的提??；針對(duì)組批和排缸的全局優(yōu)化問(wèn)題，設(shè)計(jì)組批智能體與排缸智能體協(xié)作調(diào)度機(jī)制，通過(guò)智能體與車間交互訓(xùn)練建立高效的調(diào)度策略。

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

染色工序要求將素色坯布放置染缸中持續(xù)浸染，直至紡織品的顏色符合預(yù)定要求[27]。染色車間通常有多種不同容量的染缸且各染缸獨(dú)立工作，染缸一旦開(kāi)始染色，在工序完成之前無(wú)法被其他任務(wù)搶占。為提高染缸的利用率，相同幅寬的坯布可經(jīng)首尾縫制連接后，組批進(jìn)入同一個(gè)染缸進(jìn)行染色，但多個(gè)染色任務(wù)的總質(zhì)量不得超過(guò)染缸的最大容量。由于印染不同的顏色所需的染料和助劑不同，只有相同顏色的染色任務(wù)才能同時(shí)進(jìn)入同一個(gè)染缸生產(chǎn)。因不同型號(hào)的坯布紗線原料比例不同，不同批次紗線的化學(xué)處理不同可能會(huì)導(dǎo)致染色差異，組批時(shí)還需是同一批紗線原料織造的同型號(hào)坯布。因此幅寬、顏色、型號(hào)和紗線批號(hào)均相同的坯布可歸為同一加工族，僅同族的任務(wù)才能進(jìn)行組批，組批完成后進(jìn)行排缸，即選擇批次指派到染缸進(jìn)行染色，染色任務(wù)的生產(chǎn)調(diào)度過(guò)程如圖1所示。

綜上，染色車間調(diào)度問(wèn)題可描述為：有n個(gè)染色任務(wù)動(dòng)態(tài)到達(dá)，需在m臺(tái)并行批處理機(jī)上進(jìn)行加工，已知生產(chǎn)工藝和加工參數(shù)等，在滿足相關(guān)約束的基礎(chǔ)上，對(duì)訂單任務(wù)進(jìn)行組批和排序，以使得產(chǎn)品訂單總拖期時(shí)間最小。

本文研究的問(wèn)題基于以下假設(shè)：

(1)所有任務(wù)動(dòng)態(tài)到達(dá)；(2)不存在撤單等特殊情況；(3)批處理機(jī)有不同的最大容量限制；(4)具有不同色系、色號(hào)、幅寬或布批號(hào)的任務(wù)不兼容；(5)同族任務(wù)加工時(shí)間相同，且可組批加工；(6)連續(xù)的批次加工之間存在由顏色決定的不同準(zhǔn)備時(shí)間；(7)任務(wù)在任一時(shí)刻只能由一臺(tái)機(jī)器加工；(8)任務(wù)在機(jī)器上非搶占式加工。

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

進(jìn)一步建立染色車間調(diào)度的數(shù)學(xué)模型：

1.2.1 符號(hào)與變量定義

表1 符號(hào)與變量

續(xù)表1

表2 決策變量

1.2.2 建立數(shù)學(xué)模型

將染色車間調(diào)度問(wèn)題建立如下數(shù)學(xué)模型：

(1)

(2)

?k∈[1,…,b],j∈[1,…,n]；

(3)

?k∈[1,…,b],i∈[1,…,m]；

(4)

eif·xjki≤Ykif,?j∈[1,…,n],k∈[1,…,b],i∈[1,…,m],f∈[1,…,o]；

(5)

tli≥tki+(Pf+Sfg)xjki,?k∈Ff,l∈Fg,k

(6)

tki≥max{rj|?Jj∈Bk}+Sfg,b

(7)

cki≥tki+Pf·xjbi,?Ff,j∈[1,…,n],i∈[1,…,m]；

(8)

cki,tki≥0,?k∈[1,…,b],i∈[1,…,m]；

(9)

Tj≥max(cki·xjki-dj,0),?k∈[1,…,b],i∈[1,…,m],j∈[1,…,n]；

(10)

xjki，Ykif∈{0,1},?j∈[1,…,n],k∈[1,…,b],i∈[1,…,m],f∈[1,…,o]。

(11)

其中：式(1)表示最小化總拖期時(shí)間；約束(2)確保一個(gè)任務(wù)只能匹配到一個(gè)批和一個(gè)染缸；約束(3)表示批的最大重量不得超過(guò)加工該批的染缸的最大容量；約束(4)和約束(5)表示加工族約束；約束(6)表示相鄰兩個(gè)批次的染缸切換時(shí)間約束；約束(7)表示開(kāi)始加工時(shí)間約束；約束(8)表示完工時(shí)間約束；約束(9)表示起始時(shí)間和完工時(shí)間必須大于0；約束(10)表示任務(wù)的拖期時(shí)間約束，若未拖期則為0；約束(11)表示兩個(gè)決策變量為0-1變量。

2 基于MA-RPPO強(qiáng)化學(xué)習(xí)的染色車間動(dòng)態(tài)調(diào)度方法

染色車間調(diào)度問(wèn)題可分解為組批和排缸兩個(gè)子問(wèn)題。組批是將同加工族的任務(wù)組合到一起形成批次；排缸是將組合好的批分配至染缸進(jìn)行染色生產(chǎn)。在實(shí)際生產(chǎn)過(guò)程中，客戶訂單不斷的下達(dá)，車間狀態(tài)隨時(shí)序演進(jìn)，染色車間調(diào)度問(wèn)題轉(zhuǎn)化為包含組批和排缸的序列決策問(wèn)題。本文研究基于多智能體強(qiáng)化學(xué)習(xí)的調(diào)度算法，設(shè)計(jì)動(dòng)態(tài)調(diào)度機(jī)制，并驅(qū)動(dòng)如圖2所示的組批智能體和排缸智能體分別對(duì)兩個(gè)子問(wèn)題進(jìn)行求解，以實(shí)現(xiàn)總拖期時(shí)間最小。

2.1 動(dòng)態(tài)調(diào)度機(jī)制

基于完全反應(yīng)式的動(dòng)態(tài)調(diào)度方法的主要思想是根據(jù)車間的實(shí)時(shí)狀態(tài)實(shí)時(shí)安排待加工任務(wù)的生產(chǎn)。隨著新任務(wù)的到達(dá)和車間加工進(jìn)度的變化，需要及時(shí)地安排新任務(wù)到空閑的染缸上進(jìn)行加工，不斷重復(fù)上述過(guò)程直至所有任務(wù)加工完成。如圖3所示為本文提出的調(diào)度染色車間動(dòng)態(tài)調(diào)度流程。在加工過(guò)程中依次執(zhí)行如圖3左側(cè)所示的組批子循環(huán)和排缸子循環(huán)，在調(diào)度策略中考慮等待實(shí)現(xiàn)目標(biāo)優(yōu)化，并通過(guò)圖3右側(cè)所示的事件與時(shí)間窗結(jié)合的混合觸發(fā)方法不斷滾動(dòng)。

染色車間以訂單驅(qū)動(dòng)生產(chǎn)，在未知未來(lái)訂單的動(dòng)態(tài)環(huán)境下需要考慮等待。如圖4中無(wú)等待的調(diào)度甘特圖所示，在t1時(shí)刻可對(duì)J1進(jìn)行加工，但后續(xù)到達(dá)的任務(wù)J2到達(dá)時(shí)，由于J1已進(jìn)行加工且無(wú)法中斷，導(dǎo)致J3和J4的拖期時(shí)間均有增加。因此，在動(dòng)態(tài)生產(chǎn)環(huán)境下對(duì)任務(wù)訂單進(jìn)行合理的等待能有效的減少任務(wù)的完工時(shí)間。

為提升動(dòng)態(tài)環(huán)境下的響應(yīng)能力，本文首先考慮了現(xiàn)有研究常用的事件驅(qū)動(dòng)的調(diào)度。但因在調(diào)度策略中考慮了等待，等待成功與否同樣具有不確定性，可能會(huì)發(fā)生因等待任務(wù)而導(dǎo)致染缸長(zhǎng)時(shí)間空閑的情況，因此在其基礎(chǔ)上引入時(shí)間窗口觸發(fā)機(jī)制，可及時(shí)對(duì)不合理的等待方案進(jìn)行修正。調(diào)度觸發(fā)時(shí)間刷新表示如下：

t←min(thappen,t+tw)。

(12)

式中：thappen為下一事件發(fā)生時(shí)刻，tw為時(shí)間窗口長(zhǎng)度參數(shù)。

2.2 MA-RPPO強(qiáng)化學(xué)習(xí)調(diào)度算法

基于強(qiáng)化學(xué)習(xí)的調(diào)度方法不同于傳統(tǒng)調(diào)度優(yōu)化方法的“建模、分析、優(yōu)化”的思路，而是通過(guò)對(duì)調(diào)度交互數(shù)據(jù)進(jìn)行學(xué)習(xí)，根據(jù)生產(chǎn)系統(tǒng)的反饋逐步調(diào)整調(diào)度策略實(shí)現(xiàn)調(diào)度策略的優(yōu)化[28]。首先，針對(duì)問(wèn)題特點(diǎn)進(jìn)行了強(qiáng)化學(xué)習(xí)智能體的設(shè)計(jì)；然后，強(qiáng)化學(xué)習(xí)智能體與染色車間的調(diào)度交互過(guò)程采用馬爾可夫決策過(guò)程(Markov Decision Processes, MDP)進(jìn)行描述，包括調(diào)度狀態(tài)空間、調(diào)度動(dòng)作空間和調(diào)度獎(jiǎng)勵(lì)函數(shù)的設(shè)計(jì)；最后，在調(diào)度觸發(fā)時(shí)智能體輸入染色車間狀態(tài)s，然后輸出調(diào)度決策a，車間環(huán)境反饋獎(jiǎng)勵(lì)值r，隨時(shí)序不斷地執(zhí)行如圖5所示循環(huán)交互獲得大量調(diào)度經(jīng)驗(yàn)數(shù)據(jù)，智能體以數(shù)據(jù)驅(qū)動(dòng)的方法更新模型，實(shí)現(xiàn)調(diào)度策略優(yōu)化。

2.2.1 調(diào)度智能體

MA-RPPO強(qiáng)化學(xué)習(xí)多智能體結(jié)構(gòu)如圖6所示，模型包括組批與排缸兩個(gè)PPO智能體，每個(gè)智能體有一個(gè)調(diào)度策略模塊Actor，各自通過(guò)一個(gè)深度神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)從車間狀態(tài)到組批或排缸調(diào)度動(dòng)作的映射。組批Actor和排缸Actor通過(guò)動(dòng)態(tài)調(diào)度機(jī)制進(jìn)行序列式調(diào)度，與染色車間環(huán)境進(jìn)行交互并學(xué)習(xí)的調(diào)度經(jīng)驗(yàn)優(yōu)化調(diào)度策略。兩個(gè)智能體共享一個(gè)全局Critic和一個(gè)全局LSTM網(wǎng)絡(luò)。設(shè)計(jì)的全局的調(diào)度行為評(píng)價(jià)模塊Critic用來(lái)逼近真實(shí)的系統(tǒng)反饋，通過(guò)一個(gè)深度神經(jīng)網(wǎng)絡(luò)建立從車間全局狀態(tài)與調(diào)度決策到調(diào)度評(píng)價(jià)的映射。在PPO算法基礎(chǔ)上，本強(qiáng)化學(xué)習(xí)多智能體針對(duì)問(wèn)題動(dòng)態(tài)性引入LSTM實(shí)現(xiàn)動(dòng)態(tài)信息融合，針對(duì)組批調(diào)度和排缸調(diào)度兩個(gè)子設(shè)計(jì)智能體交互機(jī)制實(shí)現(xiàn)智能體的協(xié)作調(diào)度。

(1)動(dòng)態(tài)信息融合

LSTM模塊輸入車間的歷史狀態(tài)與調(diào)度記錄進(jìn)行編碼和記憶，實(shí)現(xiàn)歷史動(dòng)態(tài)信息的融合，并輸出一維矩陣對(duì)為智能體的調(diào)度提供關(guān)鍵的車間動(dòng)態(tài)信息。如圖7所示，全局狀態(tài)向量和調(diào)度決策進(jìn)行拼接后，輸入至LSTM網(wǎng)絡(luò)的內(nèi)部通過(guò)隱狀態(tài)h和c進(jìn)行信息傳遞，LSTM單元的輸入輸出可表示如下：

mdc-1=LSTM(hdc-2,cdc-2,[sdc-1,adc-1];ψ)。

(13)

式中：LSTM輸入包括車間狀態(tài)sdc-1，上一時(shí)刻的調(diào)度決策adc-1，ψ為L(zhǎng)STM網(wǎng)絡(luò)參數(shù)，hdc-2和cdc-2均為L(zhǎng)STM的內(nèi)部隱狀態(tài)，LSTM輸出交互向量mdc-1是一維向量，該向量是歷史車間狀態(tài)記錄的和預(yù)測(cè)信息的編碼。交互向量輸出后，作為調(diào)度智能體的輸入，使得智能體調(diào)度時(shí)獲得當(dāng)前的車間調(diào)度關(guān)鍵動(dòng)態(tài)信息。通過(guò)為智能體引入上述LSTM的記憶與預(yù)測(cè)功能，實(shí)現(xiàn)車間動(dòng)態(tài)信息的融合，進(jìn)一步提高智能體的動(dòng)態(tài)自適應(yīng)能力。

(2)智能體交互機(jī)制

通過(guò)LSTM為中心的調(diào)度決策輸入和交互向量輸出實(shí)現(xiàn)智能體之間的交互。智能體調(diào)度前，從LSTM獲取交互向量作為智能體的部分輸入，而交互向量編碼了歷史調(diào)度信息，實(shí)現(xiàn)了歷史調(diào)度的智能體到當(dāng)前調(diào)度智能體的調(diào)度信息發(fā)送；智能體調(diào)度后的調(diào)度動(dòng)作返回給LSTM，將當(dāng)前智能體的調(diào)度決策信息由LSTM記錄，未來(lái)智能體調(diào)度時(shí)均可從LSTM獲得本次的調(diào)度信息。以圖6中的連續(xù)兩次組批調(diào)度和排缸調(diào)度為例，在dc=0次調(diào)度時(shí)刻，組批智能體進(jìn)行調(diào)度，本次調(diào)度的車間狀態(tài)和組批調(diào)度動(dòng)作發(fā)送到LSTM記錄；dc=1次調(diào)度時(shí)，排缸智能體從LSTM獲取輸出向量m1，因m1中編碼了dc=0次調(diào)度的組批信息，通過(guò)上述交互實(shí)現(xiàn)組批智能體和排缸智能體之間的交互，如圖6中的紅色路徑所示。

兩個(gè)不同的智能體功能不同，所需要觀測(cè)的信息也不同，因此智能體調(diào)度時(shí)所輸入的矩陣是全局狀態(tài)的不同子集。具體的，組批智能體觀察的狀態(tài)包括待組批任務(wù)狀態(tài)f1和批狀態(tài)f2，而排缸智能體觀察的狀態(tài)則包括批狀態(tài)f2和染缸的狀態(tài)f3。設(shè)計(jì)組批智能體局部觀測(cè)的狀態(tài)矩陣如下：

sB=[f1,f2];

(14)

設(shè)計(jì)排缸智能體局部觀測(cè)的狀態(tài)矩陣如下：

sS=[f2,f3]。

(15)

2.2.2 調(diào)度狀態(tài)空間

智能體進(jìn)行調(diào)度決策依賴于車間的狀態(tài)信息，通過(guò)狀態(tài)信息感知車間環(huán)境動(dòng)態(tài)變化。根據(jù)車間調(diào)度約束與優(yōu)化目標(biāo)相關(guān)的狀態(tài)特征設(shè)計(jì)狀態(tài)矩陣Fdye。染色車間調(diào)度主要包括任務(wù)、批和染缸3個(gè)對(duì)象，因此用Fdye=[f1,f2,f3]對(duì)車間狀態(tài)進(jìn)行描述，其中f1=[f1,1,…,f1,n]為待組批任務(wù)的狀態(tài)，而f1,j=[f1,j,1,…,f1,j,8]表示任務(wù)Jj的特征向量；f2=[f2,1,…,f2,b]為批狀態(tài)，其中f2,k=[f2,k,1,…,f2,k,9]表示批次Bk的特征向量，而f3=[f3,1,…,f3,m]為染缸狀態(tài)，其中f3,i=[f3,i,1,…,f3,i,6]表示染缸Mi的特征向量。待組批任務(wù)、批和染缸3種特征向量中的參數(shù)含義及表達(dá)式分別如表3所示。

表3 染色車間狀態(tài)參數(shù)表

2.2.3 調(diào)度動(dòng)作空間

染色車間調(diào)度決策空間是在車間不同的狀態(tài)下可執(zhí)行的調(diào)度決策集合，主要包括組批調(diào)度決策空間和排缸調(diào)度決策空間。

(1)組批調(diào)度決策空間 設(shè)定數(shù)量為q的組批緩沖區(qū)，組批調(diào)度決策將當(dāng)前待組批任務(wù)加入某個(gè)組批緩沖區(qū)或暫緩組批，組批調(diào)度決策空間定義為：

調(diào)度決策1：選擇第k個(gè)組批緩沖區(qū)

a=k(0≤k

(16)

調(diào)度決策2：等待

a=q。

(17)

組批調(diào)度決策時(shí)選擇一個(gè)組批緩沖區(qū)則將當(dāng)前待組批任務(wù)加入該組批緩沖區(qū)，選擇等待則該任務(wù)暫緩組批。若組批智能體將任務(wù)加入的批不兼容或超出批最大容量則組批失敗，結(jié)果等同于動(dòng)作2。

(2)排缸調(diào)度決策空間 排缸調(diào)度決策在組批緩沖區(qū)中選擇一個(gè)組批緩沖區(qū)，并匹配到染缸進(jìn)行加工，與組批調(diào)度決策空間定義相同。選擇一個(gè)組批緩沖區(qū)則將該批進(jìn)行染缸匹配并進(jìn)行染色生產(chǎn)，并將該組批緩沖區(qū)清空；選擇等待則表示不選擇任何批進(jìn)行加工。若染缸匹配失敗，則等執(zhí)行等待。為減少拖期，染缸匹配規(guī)則設(shè)為在滿足容量要求的染缸集合中選擇切換時(shí)間最小的染缸。

2.2.4 調(diào)度獎(jiǎng)勵(lì)函數(shù)

設(shè)計(jì)調(diào)度獎(jiǎng)勵(lì)函數(shù)，將目標(biāo)函數(shù)按調(diào)度的步驟進(jìn)行分解，實(shí)現(xiàn)分步獎(jiǎng)勵(lì)。

(1)組批調(diào)度獎(jiǎng)勵(lì)函數(shù)

(18)

(19)

(20)

(2)排缸調(diào)度獎(jiǎng)勵(lì)函數(shù)

(21)

(22)

spj(t)=

(23)

引理1最小化總拖期時(shí)間等效于最大化累積獎(jiǎng)勵(lì)。

證明對(duì)右式中的累積獎(jiǎng)勵(lì)進(jìn)行如下變換：

步驟1將單次調(diào)度步驟的獎(jiǎng)勵(lì)轉(zhuǎn)換為該調(diào)度窗口內(nèi)拖期時(shí)間的積分：

步驟2將整個(gè)調(diào)度回合的獎(jiǎng)勵(lì)合并為拖期時(shí)間積分：

步驟3將組批拖期與排缸拖期時(shí)間積分合并：

由此得證：

其中sfj(t)為任務(wù)j已到達(dá)且未完工的標(biāo)志位：

(24)

強(qiáng)化學(xué)習(xí)方法的學(xué)習(xí)過(guò)程即通過(guò)參數(shù)更新實(shí)現(xiàn)最大化獎(jiǎng)勵(lì)，最大化上述獎(jiǎng)勵(lì)與最小化拖期時(shí)間等價(jià)，為后續(xù)的強(qiáng)化學(xué)習(xí)模型更新提供有效的指導(dǎo)。

2.2.5 模型更新

本文的模型參數(shù)更新方法在傳統(tǒng)的PPO算法[15]上進(jìn)行改進(jìn)。首先，將LSTM網(wǎng)絡(luò)與Actor和Critic進(jìn)行全局更新實(shí)現(xiàn)LSTM網(wǎng)絡(luò)與智能體同步優(yōu)化。LSTM網(wǎng)絡(luò)輸出是Actor網(wǎng)絡(luò)和Critic網(wǎng)絡(luò)的輸入，將Actor網(wǎng)絡(luò)和Critic網(wǎng)絡(luò)更新時(shí)的梯度回傳至前綴LSTM網(wǎng)絡(luò)實(shí)現(xiàn)全局參數(shù)優(yōu)化。然后，由于組批和排缸智能體優(yōu)化同一目標(biāo)，將組批和排缸的獎(jiǎng)勵(lì)值進(jìn)行全局折扣，實(shí)現(xiàn)組批和排缸之間的相互關(guān)聯(lián)與影響：

(25)

式中Q(sdc,adc)為在狀態(tài)sdc下選擇調(diào)度決策adc所獲得的全局累計(jì)折扣獎(jiǎng)勵(lì)值。通過(guò)滾動(dòng)事件和滾動(dòng)時(shí)間窗驅(qū)動(dòng)，不斷進(jìn)行調(diào)度，獲取大量染色車間調(diào)度交互數(shù)據(jù)〈s,a,r〉并進(jìn)行存儲(chǔ)，直至所有任務(wù)完成，采用梯度下降法對(duì)參數(shù)進(jìn)行更新，通過(guò)不斷迭代實(shí)現(xiàn)車間狀態(tài)到調(diào)度決策的策略函數(shù)優(yōu)化。算法偽代碼如算法1所示。

算法1基于MA-RPPO強(qiáng)化學(xué)習(xí)的染色車間調(diào)度算法。

1:初始化智能體參數(shù)θ1,θ2,φ,ψ

3:for each episode do:

4: 初始化決策時(shí)間dt=0，化決策次數(shù)dc=0

5: 初始化任務(wù)序列、交互向量mdc、經(jīng)驗(yàn)緩存池、全局狀態(tài)sdc

6: while not done do:

7: for job in waiting job:

13: dc←dc+1

14: While True：

20: dc←dc+1

21: If排缸結(jié)果為等待：

22: break

23: end while

24: 等待至下一次調(diào)度觸發(fā)，刷新時(shí)間t

25: end while

26: 計(jì)算全局折扣Q(sdc,adc),?k

27: for agent=組批智能體A0，排缸智能體A1do：

28: for epoch=1,2,…,N do:

29: 計(jì)算策略網(wǎng)絡(luò)梯度?L(θi,γ)和值網(wǎng)絡(luò)梯度?J(ω,ψ)

30: 更新策略網(wǎng)絡(luò)(θi,ψ)←(θi,ψ)+αθ?J(θi,ψ)

31: 更新值網(wǎng)絡(luò)(ω,ψ)←(ω,ψ)-αω?L(ω,ψ)

32: end for

33: θold,wold,ψo(hù)ld←θ,w,ψ

34: end for

35:end for

3 實(shí)例驗(yàn)證

通過(guò)對(duì)福建某紡織品企業(yè)染色車間的實(shí)際生產(chǎn)歷史數(shù)據(jù)進(jìn)行實(shí)驗(yàn)以驗(yàn)證所提方法的有效性。每條染色任務(wù)數(shù)據(jù)包括顏色、重量、色系、任務(wù)類型、布批號(hào)、加工時(shí)間、到達(dá)時(shí)間等參數(shù)。依次加工不同族批次所需準(zhǔn)備時(shí)間sj1,j2取值如表4所示。實(shí)驗(yàn)使用Python 3.6進(jìn)行編程，使用Pytorch機(jī)器學(xué)習(xí)框架搭建強(qiáng)化學(xué)習(xí)網(wǎng)絡(luò)模型，計(jì)算環(huán)境為core i5, 16G RAM, Windows 10操作系統(tǒng)。實(shí)驗(yàn)包括訓(xùn)練和測(cè)試兩部分，模型訓(xùn)練過(guò)程中染色任務(wù)按照任務(wù)數(shù)據(jù)中既定的時(shí)間到達(dá)，通過(guò)迭代訓(xùn)練獲得最優(yōu)模型并保存，最后將測(cè)試任務(wù)算例導(dǎo)入到保存的模型進(jìn)行測(cè)試，并對(duì)比其性能。

表4 顏色切換準(zhǔn)備時(shí)間表 h

3.1 數(shù)據(jù)預(yù)處理

原始數(shù)據(jù)部分特征為字符串或特殊含義的數(shù)字，例如布批號(hào)和顏色等，字符串無(wú)法參與運(yùn)算，編號(hào)類數(shù)字直接參與運(yùn)算會(huì)造成網(wǎng)絡(luò)更新過(guò)程產(chǎn)生梯度消失或梯度爆炸等現(xiàn)象。因此，在進(jìn)行實(shí)驗(yàn)之前應(yīng)對(duì)數(shù)據(jù)中的以下特征首先進(jìn)行編碼處理，包括色號(hào)、色系和布批號(hào)。常用的編碼方式有二進(jìn)制編碼、獨(dú)熱編碼和整數(shù)編碼。其中對(duì)同一色系內(nèi)的色號(hào)按照顏色的深淺進(jìn)行整數(shù)編碼并歸一化，對(duì)不同的色系和布批號(hào)進(jìn)行獨(dú)熱編碼，緊急任務(wù)類型參數(shù)本身為整數(shù)編碼，對(duì)其進(jìn)行0-1歸一化。因部分觀測(cè)的狀態(tài)特征如等待時(shí)間等參數(shù)隨時(shí)間變化而增長(zhǎng)，導(dǎo)致梯度消失或梯度爆炸，采用比例因子法對(duì)與時(shí)間相關(guān)的狀態(tài)參數(shù)進(jìn)行縮放，減少各個(gè)特征維度的數(shù)量級(jí)差異，設(shè)縮放比例因子為bt。數(shù)據(jù)預(yù)處理示例如圖8所示。

(26)

3.2 參數(shù)設(shè)置與優(yōu)化

采用概率匹配[29]對(duì)候選調(diào)度決策按策略輸出權(quán)重進(jìn)行隨機(jī)采樣，避免智能體陷入局部最優(yōu)并提高解集的多樣性，實(shí)現(xiàn)調(diào)度的探索與利用之間的平衡。在狀態(tài)矩陣后分別添加后綴0或1，實(shí)現(xiàn)全局Critic對(duì)組批和排缸的區(qū)分。搭建兩個(gè)網(wǎng)絡(luò)結(jié)構(gòu)相同的智能體，對(duì)學(xué)習(xí)率、累積折扣因子、交互向量長(zhǎng)度、組批緩沖區(qū)數(shù)量等進(jìn)行參數(shù)優(yōu)化，部分關(guān)鍵參數(shù)正交實(shí)驗(yàn)結(jié)果如圖9所示；小批量樣本數(shù)和經(jīng)驗(yàn)緩存區(qū)容量上限則根據(jù)算法調(diào)度交互過(guò)程的交互數(shù)據(jù)情況進(jìn)行確定，因PPO算法的交互數(shù)據(jù)在參數(shù)更新后可以重用，將經(jīng)驗(yàn)緩存區(qū)容量設(shè)置成一個(gè)回合獲取交互數(shù)據(jù)條數(shù)的3倍～5倍，提高智能體的調(diào)度交互效率，學(xué)習(xí)速度更快；時(shí)間窗大小、組批緩沖區(qū)最大數(shù)量和時(shí)間縮放因子bt則根據(jù)調(diào)度過(guò)程的情況進(jìn)行設(shè)定；優(yōu)化器、折扣因子和隱層神經(jīng)元數(shù)量參數(shù)則根據(jù)經(jīng)驗(yàn)進(jìn)行確定；最終確定相關(guān)參數(shù)如表5所示，并且在該參數(shù)設(shè)定時(shí)算法的調(diào)度優(yōu)化效果較好。

表5 實(shí)驗(yàn)參數(shù)

3.3 模型訓(xùn)練

根據(jù)表5所示參數(shù)對(duì)算法進(jìn)行設(shè)定并在訓(xùn)練集上進(jìn)行訓(xùn)練，在迭代過(guò)程中記錄各項(xiàng)參數(shù)變化，并與改進(jìn)前的PPO算法對(duì)比。對(duì)比算法為兩個(gè)單獨(dú)PPO智能體，沒(méi)有LSTM單元、智能體交互與全局折扣，其余參數(shù)設(shè)置均相同。如圖10所示為改進(jìn)前后的算法在100個(gè)相同規(guī)模的算例上迭代訓(xùn)練的結(jié)果對(duì)比。每個(gè)算例有50個(gè)任務(wù)，由10臺(tái)染缸生產(chǎn)，在每一代對(duì)所有算例進(jìn)行調(diào)度后更新參數(shù)，訓(xùn)練過(guò)程參數(shù)變化如圖10所示。

由圖10a可知，MA-RPPO算法訓(xùn)練過(guò)程的全局累積折扣獎(jiǎng)勵(lì)值逐漸上升，同時(shí)圖10b所示組批智能體和圖10c所示排缸智能體的平均累積折扣獎(jiǎng)勵(lì)均表現(xiàn)出良好的上升趨勢(shì)，表明兩個(gè)智能體通過(guò)以LSTM單元為中心的信息交互形成了良好的協(xié)作關(guān)系，排缸和組批實(shí)現(xiàn)了全局優(yōu)化，且其優(yōu)化過(guò)程明顯優(yōu)于PPO模型。全局累積折扣獎(jiǎng)勵(lì)值上升的同時(shí)，圖10d中的總拖期時(shí)間也隨之逐漸降低，驗(yàn)證了本文設(shè)計(jì)的獎(jiǎng)勵(lì)函數(shù)與全局優(yōu)化目標(biāo)的一致性，進(jìn)一步證明了模型改進(jìn)的有效性。圖10e中值網(wǎng)絡(luò)損失逐漸收斂，表明全局Critic對(duì)兩個(gè)智能體所作調(diào)度的評(píng)估誤差逐漸減小，建立了染色車間調(diào)度全局評(píng)估體系。圖10f中全局Critic對(duì)智能體的動(dòng)作值評(píng)價(jià)逐漸升高，說(shuō)明在評(píng)價(jià)誤差減小的同時(shí)，智能體的調(diào)度性能越來(lái)越好。

綜上可見(jiàn)，MA-RPPO算法在訓(xùn)練過(guò)程實(shí)現(xiàn)了對(duì)調(diào)度智能體的優(yōu)化，智能體間的協(xié)作調(diào)度體系得以形成，對(duì)組批和排缸兩種調(diào)度決策實(shí)現(xiàn)了全局評(píng)估，通過(guò)訓(xùn)練模型提升了動(dòng)態(tài)環(huán)境下染色車間調(diào)度能力。訓(xùn)練過(guò)程整體表明MA-RPPO模型訓(xùn)練過(guò)程穩(wěn)定，收斂速度較PPO模型快，全局求解能力更強(qiáng)，更滿足動(dòng)態(tài)調(diào)度的需求，驗(yàn)證了改進(jìn)的有效性。

3.4 實(shí)例測(cè)試

通過(guò)測(cè)試算例驗(yàn)證訓(xùn)練所得模型解決調(diào)度問(wèn)題的有效性。染缸數(shù)m=5或10，任務(wù)數(shù)n=50或100，對(duì)每一種m與n設(shè)置10個(gè)算例。MA-RPPO模型事先在包括100個(gè)相同規(guī)模算例的訓(xùn)練集上進(jìn)行訓(xùn)練并對(duì)模型進(jìn)行保存。表6展示的是訓(xùn)練后的算法與A1規(guī)則[30]和按到期時(shí)間排序組批(SortedbyDuedateandconstructBatches,SDB)規(guī)則[31]對(duì)測(cè)試算例的調(diào)度結(jié)果對(duì)比情況。結(jié)果表明，A1規(guī)則是解決染色車間調(diào)度問(wèn)題的較優(yōu)規(guī)則，因SDB規(guī)則考慮的僅是任務(wù)的到期時(shí)間而未考慮加工族的整體情況，而A1首先通過(guò)族的篩選然后在族內(nèi)按照到期時(shí)間進(jìn)行排序，其綜合考慮了不同族任務(wù)的加工時(shí)間與到期時(shí)間的比值，調(diào)度結(jié)果更優(yōu)。但實(shí)質(zhì)上以上方法均為貪心策略，組批和排缸調(diào)度決策均為事件觸發(fā)，本文提出的方法在所有算例上均優(yōu)于以上兩種調(diào)度規(guī)則，無(wú)論其規(guī)模大小都能通過(guò)學(xué)習(xí)獲得比現(xiàn)有調(diào)度規(guī)則更優(yōu)的策略。

表6 算法性能對(duì)比

續(xù)表6

由圖11所示的較A1算法提升百分比可知，在規(guī)模為m=5,n=100的算例上提升最為明顯，這是因?yàn)樵撍憷靖讛?shù)較少且任務(wù)較多，染缸的負(fù)荷高，算例最大完工時(shí)間最長(zhǎng)，通過(guò)合理的等待對(duì)目標(biāo)的提升明顯，本方法可實(shí)現(xiàn)考慮動(dòng)態(tài)信息的等待，組批和排缸兩階段全局優(yōu)化，動(dòng)態(tài)調(diào)度能力更強(qiáng)。

如圖12所示為其中一個(gè)m=5,n=100的算例經(jīng)MA-RPPO算法求解后的甘特圖，其中紅色標(biāo)記的任務(wù)(編號(hào)22，23，34，47，50)是通過(guò)延遲加工且等待到了新任務(wù)的批次，說(shuō)明了智能體的調(diào)度策略可對(duì)動(dòng)態(tài)環(huán)境下的任務(wù)等待實(shí)現(xiàn)批調(diào)度優(yōu)化，通過(guò)等待新任務(wù)提高染缸的利用率的同時(shí)進(jìn)一步降低了總拖期時(shí)間。

4 結(jié)束語(yǔ)

本文以紡織品的染色生產(chǎn)車間為背景，最小化總拖期時(shí)間為目標(biāo)，針對(duì)任務(wù)動(dòng)態(tài)到達(dá)的染色車間調(diào)度問(wèn)題，提出了基于MA-RPPO強(qiáng)化學(xué)習(xí)的紡織品染色車間動(dòng)態(tài)調(diào)度算法?？紤]染色車間的復(fù)雜約束的基礎(chǔ)上將調(diào)度問(wèn)題轉(zhuǎn)化為序列式?jīng)Q策問(wèn)題，設(shè)計(jì)了考慮等待的調(diào)度流程，并提出了MA-RPPO調(diào)度多智能體結(jié)構(gòu)，通過(guò)引入LSTM實(shí)現(xiàn)時(shí)間維度的車間動(dòng)態(tài)信息融合，并作為組批智能體和排缸智能體的交互中心實(shí)現(xiàn)智能體的交互協(xié)作，進(jìn)一步實(shí)現(xiàn)了組批與排缸的兩階段全局優(yōu)化。根據(jù)染色車間的組批和排缸約束設(shè)計(jì)了狀態(tài)矩陣對(duì)車間狀態(tài)進(jìn)行描述，并對(duì)設(shè)計(jì)的獎(jiǎng)勵(lì)函數(shù)與目標(biāo)函數(shù)的等效性進(jìn)行證明。經(jīng)企業(yè)真實(shí)算例測(cè)試表明，本文提出的方法調(diào)度獲得的結(jié)果優(yōu)于現(xiàn)有兩種啟發(fā)式算法。

隨著數(shù)字化技術(shù)的不斷發(fā)展，制造業(yè)的生產(chǎn)車間數(shù)字化程度不斷加深，為建立車間的數(shù)字孿生模型提供了可能。如何在建立數(shù)字孿生模型的基礎(chǔ)上結(jié)合圖網(wǎng)絡(luò)自動(dòng)提取出車間關(guān)鍵特征作為強(qiáng)化學(xué)習(xí)狀態(tài)特征，實(shí)現(xiàn)車間的智能決策，是進(jìn)一步的研究方向。