郭 劍，史耀耀，胡 昊，陳 振，張軍鋒，趙 盼

（1.西北工業(yè)大學(xué)機(jī)電學(xué)院，西安 710072；2.西北工業(yè)大學(xué)航空發(fā)動(dòng)機(jī)高性能制造工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室，西安 710072；3.西安建筑科技大學(xué)機(jī)電工程學(xué)院，西安 710055）

隨著計(jì)算機(jī)技術(shù)、傳感器技術(shù)、無線通信技術(shù)和機(jī)器人技術(shù)快速發(fā)展，制造業(yè)正向高度自動(dòng)化和智能化方向發(fā)展[1]。自新冠肺炎全球蔓延以來，5G技術(shù)、大數(shù)據(jù)中心、工業(yè)物聯(lián)網(wǎng)、人工智能和機(jī)器人技術(shù)在“抗疫”中發(fā)揮了極大作用，力促我國加速工業(yè)“新基建”的投入。在這一背景下，企業(yè)將大量使用移動(dòng)機(jī)器人和自動(dòng)導(dǎo)引運(yùn)輸車(Automated guided vehicle,AGV)進(jìn)行車間調(diào)度和倉庫物料配送，實(shí)現(xiàn)智能化生產(chǎn)和供應(yīng)鏈管理[2]。

當(dāng)前，制造企業(yè)面臨著激烈的市場競爭和不斷上升的制造成本等方面的挑戰(zhàn)，同時(shí)產(chǎn)品需求頻繁波動(dòng)也給企業(yè)帶來較大壓力[3]。而物料調(diào)度不僅能夠優(yōu)化完工時(shí)間，同時(shí)在遵從客戶需求下能夠找到設(shè)備、路徑和運(yùn)送時(shí)間等的最佳組合。近幾年國內(nèi)外對于物料機(jī)器人調(diào)度方面的研究主要集中于傳統(tǒng)靜態(tài)調(diào)度問題，即在所有信息穩(wěn)定且已知的情況下通過啟發(fā)算法求解。朱琳等[4]提出了一種改進(jìn)的遺傳算法進(jìn)行自動(dòng)導(dǎo)航小車的任務(wù)分配和任務(wù)排序優(yōu)化。Mousavi等[5]結(jié)合遺傳算法和粒子群算法優(yōu)化柔性車間中的多目標(biāo)AGV調(diào)度問題。Gen等[6]以最小完工時(shí)間為優(yōu)化目標(biāo)，應(yīng)用基于混合優(yōu)先級的遺傳算法求解AGV調(diào)度問題。Jerald等[7]提出自適應(yīng)的遺傳算法和蟻群算法，以實(shí)現(xiàn)AGV調(diào)度中的綜合懲罰成本和機(jī)器空閑時(shí)間的最小化。Batur等[8]在兩種鄰域結(jié)構(gòu)下應(yīng)用模擬退火啟發(fā)算法求解混流車間(Hybrid flow shop,HFS)中的物料機(jī)器人調(diào)度問題，并通過對比驗(yàn)證了該方法的有效性。Zabihzadeh等[9]應(yīng)用雙信息素的蟻群算法和遺傳算法分別優(yōu)化混流車間中多物料機(jī)器人調(diào)度問題，結(jié)果表明遺傳算法性能更優(yōu)。然而，在實(shí)際生產(chǎn)中，難以提前獲知所有加工任務(wù)信息，并且在動(dòng)態(tài)的車間環(huán)境中存在諸多不確定信息（如緊急任務(wù)，設(shè)備故障，任務(wù)返工等），因此難以將靜態(tài)調(diào)度用于實(shí)際生產(chǎn)中。

近年來，由于無線射頻識別和條形碼等工業(yè)物聯(lián)網(wǎng)技術(shù)已逐步擴(kuò)展到制造環(huán)境中，車間實(shí)時(shí)數(shù)據(jù)經(jīng)多源數(shù)據(jù)融合處理后形成制造業(yè)的大數(shù)據(jù)環(huán)境[10]。而這些來自各種傳感器的實(shí)時(shí)數(shù)據(jù)流并不能直接適用于傳統(tǒng)的物料處理系統(tǒng)，因此，越來越多的學(xué)者開始關(guān)注物料機(jī)器人實(shí)時(shí)調(diào)度問題，以解決運(yùn)行環(huán)境中動(dòng)態(tài)調(diào)度問題。Lee等[11]指出在實(shí)時(shí)數(shù)據(jù)環(huán)境下，制造系統(tǒng)中的物料處理系統(tǒng)將更加高效。Zhang等[12]基于AGV實(shí)時(shí)狀態(tài)提出物料運(yùn)送的優(yōu)先策略用于物料調(diào)度。Li等[13]提出了同時(shí)面臨多個(gè)客戶需求時(shí)的智能倉庫系統(tǒng)AGV調(diào)度機(jī)制。研究表明，在車間調(diào)度中使用多種調(diào)度規(guī)則(Multiple scheduling rules,MSRs)比使用單一調(diào)度規(guī)則能更大程度地提高生產(chǎn)效率[14]，劉想德[15]應(yīng)用層次分析法(Analytic hierarchy process,AHP)在組合規(guī)則中選擇調(diào)度規(guī)則，避免了傳統(tǒng)調(diào)度人員在制定調(diào)度方案時(shí)憑借經(jīng)驗(yàn)或自己偏好選擇調(diào)度規(guī)則。上述文獻(xiàn)中，多在實(shí)時(shí)環(huán)境下應(yīng)用先進(jìn)先出(First come first served，F(xiàn)CFS),最短距離(Shortest distance first，SDF)和最早截止時(shí)間 (Earliest due date first，EDD)等規(guī)則調(diào)度物料機(jī)器人，或基于傳統(tǒng)知識庫選擇規(guī)則，因此實(shí)時(shí)適應(yīng)性較差。

為解決上述問題，越來越多的學(xué)者開始應(yīng)用強(qiáng)化學(xué)習(xí)算法求解車間物料調(diào)度問題。Wang[16]提出基于加權(quán)的強(qiáng)化學(xué)習(xí)車間自適應(yīng)調(diào)度方法，通過聚類和動(dòng)態(tài)搜索確定適合策略。另外Zhang等[17]通過融合遙感信息和AGV信息實(shí)時(shí)共享，并優(yōu)化AGV速度避免碰撞，同時(shí)提出緊急任務(wù)超車策略實(shí)現(xiàn)AGV調(diào)度。Shahrabi等[18]引入帶有Q因子的強(qiáng)化學(xué)習(xí)算法以提高動(dòng)態(tài)車間調(diào)度性能，仿真結(jié)果表明該方法相比傳統(tǒng)單規(guī)則調(diào)度和鄰域搜索，優(yōu)化性能較高。

盡管上述文獻(xiàn)中物料機(jī)器人調(diào)度研究取得了一些研究成果，但考慮到在工業(yè)物聯(lián)網(wǎng)下車間調(diào)度屬于復(fù)雜的實(shí)時(shí)優(yōu)化問題，且鮮有涉及大批量和多種類任務(wù)的動(dòng)態(tài)混流車間調(diào)度問題的相關(guān)研究。因此本文提出應(yīng)用SP–MCTS的機(jī)器人自適應(yīng)調(diào)度方法，是在基于工業(yè)物聯(lián)網(wǎng)的混流車間中以最小化完工時(shí)間和延遲率為優(yōu)化目標(biāo)，將調(diào)度系統(tǒng)實(shí)時(shí)信息作為輸入狀態(tài)，通過搜索學(xué)習(xí)快速選出實(shí)時(shí)狀態(tài)下適應(yīng)的調(diào)度規(guī)則和機(jī)器人，然后發(fā)送調(diào)度指令進(jìn)行工件運(yùn)送。最后通過模擬試驗(yàn)對所提方法進(jìn)行分析評估，驗(yàn)證其可靠性和有效性。

混流車間中物料調(diào)度問題

混流車間中物料機(jī)器人的調(diào)度問題可以描述為：多組工件je={1，2，…，ne}需經(jīng)Oj1→Oj2→，…，→Ojs道工序加工。每道工序S={1，2，…，s}內(nèi)有Mk≥1個(gè)同類并行設(shè)備，且工件j只能占用工序內(nèi)一臺(tái)平行設(shè)備加工。R個(gè)機(jī)器人對線內(nèi)物料進(jìn)行卸載、運(yùn)送、裝載。由于各工序間不設(shè)緩沖工位，物料完成加工后將在設(shè)備上等待運(yùn)送，因此當(dāng)阻塞發(fā)生時(shí)機(jī)器人選擇運(yùn)送工件的實(shí)時(shí)調(diào)度策略尤為重要。如圖1所示，物料運(yùn)送過程滿足以下約束：（1）開始調(diào)度時(shí)，各組內(nèi)的工件釋放時(shí)間相同；（2）工件j在每道工序只能加工一次，且每臺(tái)設(shè)備同一時(shí)刻只能加工一個(gè)工件；（3）工件在占用每臺(tái)設(shè)備的時(shí)間由兩部分組成，即加工時(shí)間和等待運(yùn)送時(shí)間；（4）物料的運(yùn)輸時(shí)間由設(shè)備的距離決定。

為模型建立需要，引入?yún)?shù)變量用于描述數(shù)學(xué)模型，見表1。

混流車間實(shí)時(shí)調(diào)度是依據(jù)實(shí)時(shí)狀態(tài)選擇規(guī)則，然后按照規(guī)則在車間約束關(guān)系下選擇運(yùn)送物料的方法，因此混流車間中物料運(yùn)送的約束關(guān)系如下[19]：

即

s.t．

圖1 混合流水車間物料流動(dòng)示意圖Fig.1 Diagram of material flow in hybrid flow shop

表1 符號說明Table 1 Problem notation

上述模型中：式（1）最小化最大完工時(shí)間；式（2）最小化延遲率；式（3）最小化綜合優(yōu)化目標(biāo)；式（4）每個(gè)工件各階段完工時(shí)間；式（5）各工件的完工時(shí)間；式（6）用來約束工件按照工序加工；式（7）工件在各工序段中只能在一個(gè)加工設(shè)備上完成加工；式（8）和式（9）用來約束在每個(gè)工序中同一設(shè)備工件的加工順序；式（10）和式（11）確保每個(gè)機(jī)器人在任何時(shí)候只能運(yùn)送一個(gè)工件；式（12）確保每個(gè)工件運(yùn)送過程按照工序的先后順序進(jìn)行；式（13）和式（14）機(jī)器人的調(diào)度順序符合工件在同一設(shè)備的處理順序。

馬爾科夫決策模型建立

文中將多機(jī)器人調(diào)度過程轉(zhuǎn)化為馬爾科夫決策過程[20-21]，通過四元組描述為（S,A,P,R）。其中S為調(diào)度車間狀態(tài)空間，車間現(xiàn)場狀態(tài)s∈S；A表示動(dòng)作空間，由調(diào)度規(guī)則、工序ID、機(jī)器人ID組成；P（s,A,s'）= 1，一旦動(dòng)作選擇，狀態(tài)從s轉(zhuǎn)換至s'的概率為1；R表示在狀態(tài)s下執(zhí)行動(dòng)作a狀態(tài)轉(zhuǎn)換至s'所得報(bào)酬。如圖2所示，根據(jù)混流車間的調(diào)度問題數(shù)學(xué)約束關(guān)系建立物料車間環(huán)境，馬爾科夫決策過程即為智能系統(tǒng)根據(jù)當(dāng)前車間環(huán)境選擇一個(gè)機(jī)器人運(yùn)送動(dòng)作a作用于車間，完成運(yùn)送后車間狀態(tài)發(fā)生改變，同時(shí)產(chǎn)生一個(gè)獎(jiǎng)勵(lì)信號反饋給智能系統(tǒng)。智能體再根據(jù)獎(jiǎng)勵(lì)函數(shù)和車間狀態(tài)s選擇下一個(gè)動(dòng)作a'。針對多機(jī)器人混流車間調(diào)度的實(shí)際情況，將車間運(yùn)行中的狀態(tài)、動(dòng)作和報(bào)酬函數(shù)定義如下。

1 狀態(tài)

將車間設(shè)備特征信息與任務(wù)信息組成一個(gè)狀態(tài)變量來引導(dǎo)調(diào)度決策，即在時(shí)間t時(shí)狀態(tài)向量St=（Tt,Ft,Rt），Tt代表待運(yùn)送工件特征信息，F(xiàn)t代表車間狀態(tài)信息，Rt代表機(jī)器人特征信息。

（1）Tt為3×s矩陣，Tt（:,1）至Tt（:,s）依次為進(jìn)線工位至最后一道加工工序的統(tǒng)計(jì)信息。Tt（1,:）為每道工序中待運(yùn)送工件數(shù)目，Tt（2,:）代表每道工序待運(yùn)送工件平均剩余時(shí)間，Tt（3,:）代表每道工序待運(yùn)送工件中最小剩余時(shí)間。

圖2 車間調(diào)度的馬爾科夫決策過程Fig.2 Diagram of Markov decision process for flow shop scheduling

式中tk,l代表在第k階段待運(yùn)送工件l的剩余時(shí)間，該參數(shù)反映工件的緊迫程度。

（2）Ft為車間現(xiàn)場狀態(tài)描述矩陣，F(xiàn)t為3×s矩陣，F(xiàn)t（1,:）表示每道工序的空閑設(shè)備數(shù)，例如Ft（1,1）=1 即為工序1中有1臺(tái)空閑設(shè)備。Ft（2,:）為每道工序中正在加工狀態(tài)的設(shè)備數(shù)，F(xiàn)t（3,:）代表每道工序中被待運(yùn)送工件占用的設(shè)備數(shù)。

（3）Rt為2×i矩陣，表示各機(jī)器人的工作狀態(tài)。i與機(jī)器人ID對應(yīng)，Rt（1,:）表示機(jī)器人的狀態(tài)，Rt（1,2）=1為2號機(jī)器人“運(yùn)送”，Rt（1,2）=0為“空閑”。Rt（2,:）為機(jī)器人當(dāng)前位置ID。

2 動(dòng)作

動(dòng)作即為機(jī)器人的運(yùn)送行為，其通過工序ID，調(diào)度規(guī)則和機(jī)器人ID組成向量at=（Sat,Rut,Rbt）。工序ID選擇調(diào)度工件所在工序，調(diào)度規(guī)則選擇運(yùn)送工件，同時(shí)，機(jī)器人ID確定哪一臺(tái)機(jī)器人被選中用于調(diào)度。文中選用5種調(diào)度規(guī)則用于緩沖工位調(diào)度，SSO用于工序內(nèi)待運(yùn)送工件調(diào)度。調(diào)度規(guī)則的詳細(xì)描述如表2所示，Sat={進(jìn)線緩沖工位=0,工序=1,…,s},Rut={SPT=1,LPT=2,SLACK =3,SPT/TWK=4,LPT/TWK=5,SSO=6},Rbt={1=robot 1,2=robot 2,…,r=robotr}，通過上述動(dòng)作設(shè)計(jì)，時(shí)間t時(shí)將在指定規(guī)則下分配機(jī)器人運(yùn)送指定工序下的唯一任務(wù)。

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

獎(jiǎng)勵(lì)函數(shù)被用來對當(dāng)前行為和調(diào)度策略進(jìn)行評估，由于SP–MCTS是通過最終收益回溯逐個(gè)更新節(jié)點(diǎn)信息，而本文將最小化最大完工時(shí)間和延遲率作為綜合評價(jià)指標(biāo)，因此獎(jiǎng)勵(lì)函數(shù)設(shè)計(jì)為：

式(17)中C1為子樹內(nèi)第1次搜索至當(dāng)前所有工件完成加工時(shí)所得時(shí)間，Cn為子樹內(nèi)實(shí)時(shí)狀態(tài)節(jié)點(diǎn)的第n次搜索所得時(shí)間，其中項(xiàng)C1–Cn若大于0則取實(shí)際差值，若小于0則取0值。ND表示當(dāng)前子樹延遲率(延遲工件包括當(dāng)前搜索中出線延遲的工件和線內(nèi)剩余時(shí)間小于0的工件，總數(shù)即為子樹中的所有工件)，b1，b2為權(quán)重因子。

方法論述

1 多層子樹設(shè)計(jì)

SP–MCTS是一類利用模擬運(yùn)行過程來評價(jià)非終端狀態(tài)的搜索樹算法。模擬過程中選擇執(zhí)行動(dòng)作，直到達(dá)到一個(gè)終端狀態(tài)，并基于多次模擬中平均獎(jiǎng)勵(lì)，以此評估每個(gè)動(dòng)作的潛力[22]。針對工業(yè)物聯(lián)網(wǎng)下混流車間多機(jī)器人調(diào)度問題提出基于SP–MCTS算法的多層子樹自適應(yīng)優(yōu)化方法，如圖3所示。圖3中根據(jù)各組任務(wù)和當(dāng)前車間環(huán)境依次建立多個(gè)子樹（TR1,TR2,…TRn）進(jìn)行策略優(yōu)化，如子樹TR1進(jìn)行實(shí)時(shí)優(yōu)化時(shí)，是以車間當(dāng)前狀態(tài)作為根節(jié)點(diǎn)，組內(nèi)所有工件完成加工作為目標(biāo)狀態(tài)，應(yīng)用SP–MCTS算法進(jìn)行優(yōu)化，并取使節(jié)點(diǎn)收益最大的分支規(guī)則作為運(yùn)送動(dòng)作。根據(jù)實(shí)時(shí)狀態(tài)依次進(jìn)行優(yōu)化，最終取最優(yōu)路徑節(jié)點(diǎn)S43（組間臨界實(shí)時(shí)狀態(tài)，即進(jìn)線工位清空，工件全部進(jìn)線加工時(shí)）作為下一個(gè)子樹TR2的根節(jié)點(diǎn)原始環(huán)境，此時(shí)下一組進(jìn)入緩沖區(qū)的工件與當(dāng)前車間環(huán)境建立子樹TR2根節(jié)點(diǎn)，從而依次優(yōu)化直至各組工件完成加工。

表2 調(diào)度規(guī)則Table 2 Scheduling rules

如圖4子樹模擬優(yōu)化過程，工序內(nèi)和進(jìn)線出線緩沖區(qū)的數(shù)字“1,2,3”分別代表工件等待、加工、和出線3種狀態(tài)，各工序的平行設(shè)備數(shù)為“2 2 1 2”。在子樹TR1內(nèi)，若實(shí)時(shí)車間為狀態(tài)s1，優(yōu)化完成后執(zhí)行策略π（s）至s2，然后保留節(jié)點(diǎn)s2下的子樹信息，丟棄其他節(jié)點(diǎn)信息。此時(shí)等待下一個(gè)實(shí)時(shí)調(diào)度狀態(tài)信息與s2進(jìn)行對比，若相同則以根節(jié)點(diǎn)s2繼續(xù)優(yōu)化（子樹節(jié)點(diǎn)信息可累積使用）。依次搜索和節(jié)點(diǎn)更新，最終直至該組調(diào)度完成。

2 基于SP-MCTS強(qiáng)化學(xué)習(xí)

結(jié)合SP–MCTS算法尋優(yōu)特性，設(shè)計(jì)適應(yīng)于文中混流車間調(diào)度問題的選擇、擴(kuò)展、模擬和回溯方案[23]，如圖5所示。

2.1 選擇

選擇步驟始于當(dāng)前根節(jié)點(diǎn)s0，終止于樹中葉節(jié)點(diǎn)sL，其選擇策略根據(jù)UCT[24]（Upper confidence bounds applied to trees）算法構(gòu)建，其改進(jìn)如下：

圖3 基于SP-MCTS算法的多層子樹示意圖Fig.3 Diagram of multi-layer subtree based on SP-MCTS algorithm

式（18）中N（s）代表狀態(tài)s被訪問的次數(shù)，N（s,a）表示狀態(tài)s時(shí)執(zhí)行運(yùn)送動(dòng)作a的次數(shù)，Q（s,a）表示節(jié)點(diǎn)s處選擇運(yùn)送動(dòng)作a的平均收益，∑q（s,a）2表示到目前為止在狀態(tài)s處執(zhí)行動(dòng)作a獲得收益Q（s,a）的平方和。式（19）中π（s）代表狀態(tài)s下的最優(yōu)策略。

2.2 擴(kuò)展與模擬

如果搜索至葉節(jié)點(diǎn)sL且該節(jié)點(diǎn)遍歷次數(shù)大于P（P為節(jié)點(diǎn)擴(kuò)展臨界值）時(shí)，應(yīng)用選擇策略后執(zhí)行動(dòng)作a得到狀態(tài)sCL。此時(shí)將狀態(tài)sCL擴(kuò)展為樹中葉節(jié)點(diǎn)且節(jié)點(diǎn)信息初始為{N(sL,a)=0,Q(sL,a) = 0,N(sCL)=0}。

圖4 子樹優(yōu)化過程Fig.4 Subtree optimization process

如果搜索至葉節(jié)點(diǎn)sL且該節(jié)點(diǎn)遍歷次數(shù)小于P時(shí)，sL將作為初始的模擬節(jié)點(diǎn)。在模擬過程中，每一次執(zhí)行模擬策略前需對線內(nèi)工件評估緊迫度，若剩余時(shí)間tkr<2Tr（tkr任務(wù)k的剩余時(shí)間，Tr為車間中設(shè)備最大距離間機(jī)器人運(yùn)送時(shí)間)，則執(zhí)行LLF作為模擬策略，否則執(zhí)行既定的3種模擬策略SPT，LPT和隨機(jī)策略(Random)。

2.3 回溯

當(dāng)模擬至終止?fàn)顟B(tài)時(shí)，信息更新從模擬的初始葉節(jié)點(diǎn)sL回溯至根節(jié)點(diǎn)s0。更新各遍歷節(jié)點(diǎn)信息：

式（20）更新節(jié)點(diǎn)s被訪問的總次數(shù)。式（21）記錄s狀態(tài)下動(dòng)作a被執(zhí)行的次數(shù)，式（22）更新節(jié)點(diǎn)s執(zhí)行動(dòng)作a的平均收益。式（23）計(jì)算收益求平方和。

3 系統(tǒng)架構(gòu)

如上所述，文中提出了基于SP–MCTS求解工業(yè)物聯(lián)網(wǎng)的混流車間多機(jī)器人調(diào)度問題，其體系架構(gòu)如圖6所示。

該架構(gòu)包含4個(gè)子模塊，基于工業(yè)物聯(lián)網(wǎng)的混流車間，系統(tǒng)狀態(tài)模塊，SP–MCTS模塊和規(guī)則與執(zhí)行動(dòng)作模塊。在機(jī)器人完成運(yùn)送或空閑時(shí)且有新工件組進(jìn)入緩沖區(qū)或狀態(tài)改變時(shí)，調(diào)度過程立即觸發(fā)。此時(shí)，工業(yè)物聯(lián)網(wǎng)采集混流車間內(nèi)各制造資源實(shí)時(shí)狀態(tài)，并且發(fā)送實(shí)時(shí)信息至系統(tǒng)狀態(tài)模塊以提取關(guān)鍵狀態(tài)信息，這些信息包括任務(wù)信息和設(shè)備信息。上述這些關(guān)鍵信息最終被傳輸至SP–MCTS模塊用于優(yōu)化調(diào)度策略。數(shù)據(jù)經(jīng)SP–MCTS模塊處理后，輸出數(shù)據(jù)至規(guī)則與執(zhí)行動(dòng)作模塊。最終，規(guī)則與執(zhí)行動(dòng)作模塊根據(jù)規(guī)則選擇調(diào)度工件并規(guī)劃機(jī)器人傳輸動(dòng)作，從而實(shí)現(xiàn)基于工業(yè)物聯(lián)網(wǎng)混流車間自適應(yīng)調(diào)度的閉環(huán)反饋機(jī)制。

4 基于SP-MCTS系統(tǒng)優(yōu)化過程

SP–MCTS系統(tǒng)自適應(yīng)優(yōu)化過程可分為擴(kuò)展方法和剪支方法。如圖4所示，以實(shí)時(shí)狀態(tài)s1為根節(jié)點(diǎn)，多次迭代后建立了TR1，滿足停止條件時(shí)，則依據(jù)策略π(s)執(zhí)行動(dòng)作a得到實(shí)時(shí)調(diào)度狀態(tài)s2，此時(shí)以s2為根節(jié)點(diǎn)繼續(xù)搜索，實(shí)時(shí)狀態(tài)依次建樹的過程稱為擴(kuò)展過程。選擇動(dòng)作a時(shí)，樹內(nèi)則保留節(jié)點(diǎn)s2以下分支，剪掉其他分支即剪支過程，這樣依次搜索直至目標(biāo)狀態(tài)sgoal。其求解混流車間多機(jī)器人調(diào)度問題的流程圖如圖7所示，SP–MCTS算法偽代碼如算法1所示（表3）。

圖5 SP-MCTS算法原理圖Fig.5 Schematic diagram of SP-MCTS algorithm

圖6 應(yīng)用SP-MCTS的多機(jī)器人調(diào)度方法架構(gòu)Fig.6 Architecture of multi-robot scheduling approach using SP-MCTS

方法驗(yàn)證與討論

為評估所提方法的有效性，在此提出基于工業(yè)物聯(lián)網(wǎng)混流車間多機(jī)器調(diào)度的案例用于模擬驗(yàn)證。

1 案例描述

應(yīng)用西門子Tecnomatix 數(shù)字化平臺(tái)作為案例模擬軟件，如圖8所示，混流車間主要由9臺(tái)加工設(shè)備以及4道工序組成，其中9臺(tái)加工設(shè)備、進(jìn)線緩沖工位、出線緩沖工位均勻分布于機(jī)器人軌道兩側(cè)，且有兩臺(tái)機(jī)器人用于物料運(yùn)送。

2 應(yīng)用SP-MCTS進(jìn)行多機(jī)器人調(diào)度

應(yīng)用TensorFlow軟件和西門子Tecnomatix 數(shù)字化平臺(tái)聯(lián)合模擬工業(yè)物聯(lián)網(wǎng)下混流車間多機(jī)器人實(shí)時(shí)調(diào)度系統(tǒng)，如圖9所示。

該系統(tǒng)軟件可分為兩部分，分別是在TensorFlow平臺(tái)使用python開發(fā)的SP–MCTS程序和使用西門子Tecnomatix平臺(tái)模擬軟件開發(fā)的模擬程序。其整個(gè)模擬程序分為以下幾個(gè)子模塊：設(shè)備管理、任務(wù)管理、狀態(tài)管理、通信模塊和調(diào)度指令模塊。在模擬車間生產(chǎn)過程中，設(shè)備管理模塊負(fù)責(zé)車間內(nèi)加工設(shè)備、機(jī)器人和各類傳感器的信息管理；任務(wù)管理模塊負(fù)責(zé)所有工件的管理；狀態(tài)處理模塊作為關(guān)鍵的信息處理模塊，其作用是處理從設(shè)備管理和任務(wù)管理模塊發(fā)送的實(shí)時(shí)設(shè)備和工件信息，并將提取的關(guān)鍵信息發(fā)送至通信模塊。通信模塊是在SP–MCTS程序和模擬程序間建立一個(gè)通信網(wǎng)絡(luò)，實(shí)時(shí)傳輸狀態(tài)信息和調(diào)度指令信息。SP–MCTS優(yōu)化策略根據(jù)當(dāng)前狀態(tài)優(yōu)化調(diào)度策略，將調(diào)度策略發(fā)送至調(diào)度指令模塊。最后，調(diào)度指令模塊根據(jù)策略協(xié)調(diào)規(guī)則和機(jī)器人執(zhí)行調(diào)度任務(wù)。

3 案例描述

混流車間內(nèi)的設(shè)備、任務(wù)、機(jī)器人以及計(jì)算機(jī)模擬環(huán)境等參數(shù)設(shè)置如下：

圖7 混流車間多機(jī)器人自適應(yīng)調(diào)度流程Fig.7 Multi-robot scheduling process with SP-MCTS

（1）總的加工任務(wù)數(shù)為500,進(jìn)線緩沖工位有20個(gè)工位，根據(jù)緊迫度確定工件的進(jìn)線次序，如果存在緊迫度相同的產(chǎn)品，則按交貨期由早到晚排序[23]。從而將500個(gè)任務(wù)分成25組，依次送入進(jìn)線緩沖工位。

（2）工件在每個(gè)工序的加工時(shí)間服從(10,50)的均勻分布。

（3）為使問題簡單化，文中在機(jī)器人運(yùn)輸過程中不考慮最優(yōu)路徑和機(jī)器人碰撞沖突問題，同時(shí)工件運(yùn)輸時(shí)間服從(0.5,1)均勻分布。

（4）參數(shù)(C,D)設(shè)置為(0.5,10000)[25]，P=3，b1=0.5，b2=2。

（5）計(jì)算機(jī)模擬環(huán)境為i7–6700 CPU@3.40GHz,16G RAM。

依據(jù)上述參數(shù)取一組車間加工參數(shù)，應(yīng)用SP–MCTS算法對模擬車間中物料進(jìn)行實(shí)時(shí)調(diào)度。如圖10所示，以第一組進(jìn)線任務(wù)的路徑節(jié)點(diǎn)與最大收益值為例，可以看出在前期搜索中隨著節(jié)點(diǎn)經(jīng)驗(yàn)信息依次累加，收益數(shù)值快速提高，后期搜索中隨著狀態(tài)空間不斷縮小，樹節(jié)點(diǎn)越深其收益數(shù)值變化越趨平緩，且數(shù)據(jù)波動(dòng)越趨收窄。因而說明應(yīng)用SP–MCTS在實(shí)時(shí)優(yōu)化中能夠快速準(zhǔn)確地選擇最優(yōu)策略進(jìn)行物料調(diào)度。

表3 算法1: 基于SP-MCTS算法的優(yōu)化主程序Table 3 Algorithm 1：Optimized main procedure based on SP-MCTS

圖8 混流車間多機(jī)器人調(diào)度模擬環(huán)境Fig.8 Simulation of multi-robot scheduling on shop floor environment

圖9 混流車間多機(jī)器人調(diào)度系統(tǒng)Fig.9 Implementation of the SP-MCTS based multi-robot scheduling system

4 結(jié)果分析

在此引入RLVNS[18]、AHP[15]、SPT、LPT和SLACK與本文所提方法進(jìn)行對比，在相同的環(huán)境下處理隨機(jī)生成的500個(gè)任務(wù)，通過完工時(shí)間和延遲率進(jìn)行綜合比較。

圖10 子樹內(nèi)節(jié)點(diǎn)深度與收益值關(guān)系Fig.10 Relationship between node depth and revenue value in subtree

圖11 各方法比較結(jié)果示意圖Fig.11 Diagram of comparison results of scheduling methods

隨機(jī)產(chǎn)生10組案例車間參數(shù)應(yīng)用各方法分別優(yōu)化，然后取平均值進(jìn)行比較，如圖9所示。多機(jī)器人調(diào)度方法比較示意圖見圖11，可以直觀看出5種方法在完工時(shí)間和延遲率兩個(gè)指標(biāo)下的比較結(jié)果。與SPT、LPT和SLACK規(guī)則相比，SP–MCTS算法調(diào)度所得完工時(shí)間分別降低了28.3%、27.8%和31.4%，同時(shí)延遲率分別降低了70.4%、81%和42.9%；而相比于AHP和RLVNS方法，完工時(shí)間分別降低了16.7%和9.9%，延遲率分別降低了38.5%和22%。由此看出，單一的SPT、LPT和SLACK規(guī)則調(diào)度，雖然能快速響應(yīng)，但其適應(yīng)性差且調(diào)度質(zhì)量難以保證，而應(yīng)用SP–MCTS算法搜索尋優(yōu)后建立信息網(wǎng)絡(luò)，其結(jié)合現(xiàn)場狀況在多種規(guī)則中選擇適應(yīng)當(dāng)前狀態(tài)的最優(yōu)調(diào)度策略，從而得到更好的求解質(zhì)量。

基于SP–MCTS解的質(zhì)量優(yōu)于多規(guī)則組合AHP方法和強(qiáng)化學(xué)習(xí)RLVNS方法，可知，與多規(guī)則組合AHP方法相比，SP–MCTS算法的適應(yīng)性更強(qiáng)；而RLVNS方法只考慮第一工序的鄰域搜索學(xué)習(xí)，不能夠分辨工序之間工件調(diào)度時(shí)的信息差異，存在明顯的局限性。因此，該模擬結(jié)果驗(yàn)證了在工業(yè)物聯(lián)網(wǎng)下應(yīng)用SP–MCTS對混流車間進(jìn)行多機(jī)器人調(diào)度的有效性和優(yōu)越性。

結(jié)論

為最小化工業(yè)物聯(lián)網(wǎng)混流車間中多機(jī)器人調(diào)度的完工時(shí)間和延遲率，本文提出基于SP–MCTS算法的自適應(yīng)調(diào)度方法。由于工件分組進(jìn)入緩沖工位，因而采用分層子樹搜索機(jī)制，應(yīng)用SP–MCTS以實(shí)時(shí)狀態(tài)為節(jié)點(diǎn)進(jìn)行搜索和信息積累，然后根據(jù)現(xiàn)場情況快速選擇合適的規(guī)則和物料機(jī)器人，從而達(dá)到了自適應(yīng)調(diào)度目的。主要結(jié)論如下：

（1）分層子樹優(yōu)化，使得各組工件從一個(gè)完整的根節(jié)點(diǎn)出發(fā)同時(shí)兼顧相鄰子樹，簡化了模型難度。

（2）狀態(tài)依次作為根節(jié)點(diǎn)搜索，能夠根據(jù)累積的節(jié)點(diǎn)信息，精確快速定位動(dòng)作分支，提高了搜索效率。

（3）在模擬實(shí)驗(yàn)中與AHP方法和調(diào)度規(guī)則比較，驗(yàn)證了SP–MCTS方法的適應(yīng)性；同時(shí)SP–MCT求解的完工時(shí)間和延遲率均優(yōu)于RLVNS方法，驗(yàn)證了SP–MCTS方法在求解混流車間調(diào)度問題時(shí)的搜索理念的優(yōu)越性。

本文調(diào)度方法架構(gòu)簡明，易于實(shí)現(xiàn)，為進(jìn)一步解決工業(yè)物聯(lián)網(wǎng)下車間實(shí)時(shí)調(diào)度問題提供了參考。下一步，將結(jié)合深度學(xué)習(xí)方法建立各規(guī)則的概率網(wǎng)絡(luò)和價(jià)值網(wǎng)絡(luò)，從而使調(diào)度系統(tǒng)成為一種有意識的智慧大腦。