基于工業物聯網的混流車間機器人自適應調度

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

（1.西北工業大學機電學院，西安 710072；2.西北工業大學航空發動機高性能制造工業和信息化部重點實驗室，西安 710072；3.西安建筑科技大學機電工程學院，西安 710055）

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

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

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

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

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

混流車間中物料調度問題

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

為模型建立需要，引入參數變量用于描述數學模型，見表1。

混流車間實時調度是依據實時狀態選擇規則，然后按照規則在車間約束關系下選擇運送物料的方法，因此混流車間中物料運送的約束關系如下[19]：

即

s.t．

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

表1 符號說明Table 1 Problem notation

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

馬爾科夫決策模型建立

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

1 狀態

將車間設備特征信息與任務信息組成一個狀態變量來引導調度決策，即在時間t時狀態向量St=（Tt,Ft,Rt），Tt代表待運送工件特征信息，Ft代表車間狀態信息，Rt代表機器人特征信息。

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

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

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

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

（3）Rt為2×i矩陣，表示各機器人的工作狀態。i與機器人ID對應，Rt（1,:）表示機器人的狀態，Rt（1,2）=1為2號機器人“運送”，Rt（1,2）=0為“空閑”。Rt（2,:）為機器人當前位置ID。

2 動作

動作即為機器人的運送行為，其通過工序ID，調度規則和機器人ID組成向量at=（Sat,Rut,Rbt）。工序ID選擇調度工件所在工序，調度規則選擇運送工件，同時，機器人ID確定哪一臺機器人被選中用于調度。文中選用5種調度規則用于緩沖工位調度，SSO用于工序內待運送工件調度。調度規則的詳細描述如表2所示，Sat={進線緩沖工位=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}，通過上述動作設計，時間t時將在指定規則下分配機器人運送指定工序下的唯一任務。

3 獎勵函數

獎勵函數被用來對當前行為和調度策略進行評估，由于SP–MCTS是通過最終收益回溯逐個更新節點信息，而本文將最小化最大完工時間和延遲率作為綜合評價指標，因此獎勵函數設計為：

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

方法論述

1 多層子樹設計

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

表2 調度規則Table 2 Scheduling rules

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

2 基于SP-MCTS強化學習

結合SP–MCTS算法尋優特性，設計適應于文中混流車間調度問題的選擇、擴展、模擬和回溯方案[23]，如圖5所示。

2.1 選擇

選擇步驟始于當前根節點s0，終止于樹中葉節點sL，其選擇策略根據UCT[24]（Upper confidence bounds applied to trees）算法構建，其改進如下：

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

式（18）中N（s）代表狀態s被訪問的次數，N（s,a）表示狀態s時執行運送動作a的次數，Q（s,a）表示節點s處選擇運送動作a的平均收益，∑q（s,a）2表示到目前為止在狀態s處執行動作a獲得收益Q（s,a）的平方和。式（19）中π（s）代表狀態s下的最優策略。

2.2 擴展與模擬

如果搜索至葉節點sL且該節點遍歷次數大于P（P為節點擴展臨界值）時，應用選擇策略后執行動作a得到狀態sCL。此時將狀態sCL擴展為樹中葉節點且節點信息初始為{N(sL,a)=0,Q(sL,a) = 0,N(sCL)=0}。

圖4 子樹優化過程Fig.4 Subtree optimization process

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

2.3 回溯

當模擬至終止狀態時，信息更新從模擬的初始葉節點sL回溯至根節點s0。更新各遍歷節點信息：

式（20）更新節點s被訪問的總次數。式（21）記錄s狀態下動作a被執行的次數，式（22）更新節點s執行動作a的平均收益。式（23）計算收益求平方和。

3 系統架構

如上所述，文中提出了基于SP–MCTS求解工業物聯網的混流車間多機器人調度問題，其體系架構如圖6所示。

該架構包含4個子模塊，基于工業物聯網的混流車間，系統狀態模塊，SP–MCTS模塊和規則與執行動作模塊。在機器人完成運送或空閑時且有新工件組進入緩沖區或狀態改變時，調度過程立即觸發。此時，工業物聯網采集混流車間內各制造資源實時狀態，并且發送實時信息至系統狀態模塊以提取關鍵狀態信息，這些信息包括任務信息和設備信息。上述這些關鍵信息最終被傳輸至SP–MCTS模塊用于優化調度策略。數據經SP–MCTS模塊處理后，輸出數據至規則與執行動作模塊。最終，規則與執行動作模塊根據規則選擇調度工件并規劃機器人傳輸動作，從而實現基于工業物聯網混流車間自適應調度的閉環反饋機制。

4 基于SP-MCTS系統優化過程

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

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

圖6 應用SP-MCTS的多機器人調度方法架構Fig.6 Architecture of multi-robot scheduling approach using SP-MCTS

方法驗證與討論

為評估所提方法的有效性，在此提出基于工業物聯網混流車間多機器調度的案例用于模擬驗證。

1 案例描述

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

2 應用SP-MCTS進行多機器人調度

應用TensorFlow軟件和西門子Tecnomatix 數字化平臺聯合模擬工業物聯網下混流車間多機器人實時調度系統，如圖9所示。

該系統軟件可分為兩部分，分別是在TensorFlow平臺使用python開發的SP–MCTS程序和使用西門子Tecnomatix平臺模擬軟件開發的模擬程序。其整個模擬程序分為以下幾個子模塊：設備管理、任務管理、狀態管理、通信模塊和調度指令模塊。在模擬車間生產過程中，設備管理模塊負責車間內加工設備、機器人和各類傳感器的信息管理；任務管理模塊負責所有工件的管理；狀態處理模塊作為關鍵的信息處理模塊，其作用是處理從設備管理和任務管理模塊發送的實時設備和工件信息，并將提取的關鍵信息發送至通信模塊。通信模塊是在SP–MCTS程序和模擬程序間建立一個通信網絡，實時傳輸狀態信息和調度指令信息。SP–MCTS優化策略根據當前狀態優化調度策略，將調度策略發送至調度指令模塊。最后，調度指令模塊根據策略協調規則和機器人執行調度任務。

3 案例描述

混流車間內的設備、任務、機器人以及計算機模擬環境等參數設置如下：

圖7 混流車間多機器人自適應調度流程Fig.7 Multi-robot scheduling process with SP-MCTS

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

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

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

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

（5）計算機模擬環境為i7–6700 CPU@3.40GHz,16G RAM。

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

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

圖8 混流車間多機器人調度模擬環境Fig.8 Simulation of multi-robot scheduling on shop floor environment

圖9 混流車間多機器人調度系統Fig.9 Implementation of the SP-MCTS based multi-robot scheduling system

4 結果分析

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

圖10 子樹內節點深度與收益值關系Fig.10 Relationship between node depth and revenue value in subtree

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

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

基于SP–MCTS解的質量優于多規則組合AHP方法和強化學習RLVNS方法，可知，與多規則組合AHP方法相比，SP–MCTS算法的適應性更強；而RLVNS方法只考慮第一工序的鄰域搜索學習，不能夠分辨工序之間工件調度時的信息差異，存在明顯的局限性。因此，該模擬結果驗證了在工業物聯網下應用SP–MCTS對混流車間進行多機器人調度的有效性和優越性。

結論

為最小化工業物聯網混流車間中多機器人調度的完工時間和延遲率，本文提出基于SP–MCTS算法的自適應調度方法。由于工件分組進入緩沖工位，因而采用分層子樹搜索機制，應用SP–MCTS以實時狀態為節點進行搜索和信息積累，然后根據現場情況快速選擇合適的規則和物料機器人，從而達到了自適應調度目的。主要結論如下：

（1）分層子樹優化，使得各組工件從一個完整的根節點出發同時兼顧相鄰子樹，簡化了模型難度。

（2）狀態依次作為根節點搜索，能夠根據累積的節點信息，精確快速定位動作分支，提高了搜索效率。

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

本文調度方法架構簡明，易于實現，為進一步解決工業物聯網下車間實時調度問題提供了參考。下一步，將結合深度學習方法建立各規則的概率網絡和價值網絡，從而使調度系統成為一種有意識的智慧大腦。