陸志強，任逸飛，許則鑫

(同濟大學 機械與能源工程學院，上海 201804)

0 引言

為了滿足市場訂單需求，降低飛機生產裝配成本，目前國際大型飛機制造公司摒棄傳統(tǒng)的固定站位式飛機裝配模式，吸取豐田汽車流水生產線理念和精益生產理論，對飛機總裝生產線進行流程再造，設計了全新的飛機移動生產線裝配模式。從而大大縮短了飛機總裝時間，降低了飛機制造成本，提高了裝配質量，可按需連續(xù)生產。裝配線上的飛機以穩(wěn)定的速度平穩(wěn)地通過所有工位，從而完成整個裝配過程。每個工位都存在空間容量限制，并包含不同種類和數量的作業(yè)，而每個作業(yè)均有固定的執(zhí)行時間和所需資源種類和數量，同時不同作業(yè)間包含特定的時序約束。基于上述生產背景，任一單架飛機的總裝作業(yè)裝配過程在本質上是一類具有復雜約束的大規(guī)模單項目調度問題，同時涵蓋了具有正則目標的資源受限項目調度問題(Resource Constrained Project Scheduling Problem, RCPSP)及與之關聯的資源投入問題(Resource Investment Problem, RIP)[1]。本文以RIP為研究對象，即在保證給定生產工期條件下，滿足作業(yè)時序約束等，引入單位資源成本系數，通過合理分配各類資源和決策各個作業(yè)的調度時間，達到項目資源投入總成本最小的目的。

M?HRING[2]首先提出了RIP，證明該問題為NP-hard(nondeterministic polynomial)問題，并通過包含16個作業(yè)的算例驗證了其所設計的圖解精確算法求解RIP的有效性；RODRIGUES等[3]針對RIP設計了一種改進的分支定界算法，減少了解空間，提高了算法的效率。由于精確算法無法求解大規(guī)模問題，許多學者通過研究RIP特性，結合求解RCPSP算法思路，設計了不同的啟發(fā)式和元啟發(fā)式算法進行求解。ZHU等[4]將RIP拆分成排序問題和資源決策問題兩個子問題求解，并提出一個多開始迭代搜索啟發(fā)式算法。SHADROKH等[5]采用對資源容量和作業(yè)列表編碼的雙鏈表編碼方式的遺傳算法求解延遲懲罰成本的RIP。NAJAFI等[6]設計了一種遺傳算法求解RIP，并詳細介紹了通過實驗設計和響應曲面法調整遺傳算法參數；AFSHAR-NADJAFI[7]考慮了資源需要招募和釋放的多模式RIP，提出了以作業(yè)浮動時間為編碼的模擬退火方法；JAVANMARD等[8]針對資源多技能的RIP設計了一種基于遺傳和粒子群的算法，該算法能夠校準參數和染色體結構，保證解的可行性。上述文獻所提到求解RIP的算法均采用對資源量搜索的方式，求解在不同資源量下對應的RCPSP。然而現有算法所設計的資源上下界差距較大，使得搜索空間大，搜索效率低，極易產生不可行的資源組合。同時RCPSP本身也是NP-hard問題，現有搜索算法求解時間較長，中大規(guī)模算例的解與最優(yōu)解有一定偏差，從而會錯過最優(yōu)資源組合。RANJBAR等[9]對作業(yè)序列編碼并通過路徑重連和遺傳算法直接求解RIP，但是該算法會產生大量不可行解，需要對優(yōu)先級不可行的活動列表進行調整；任逸飛等[10]提出了基于全局作業(yè)影響的改進調度機制的遺傳算法，通過基于全局資源水平影響的作業(yè)調度評估策略優(yōu)化非關鍵作業(yè)的調度位置，然而該評估策略在求解大規(guī)模算例時效率較低，求解時間較長。

飛機移動生產線調度問題，由于現場環(huán)境復雜多變，而傳統(tǒng)的搜索算法由于其容易陷入局部最優(yōu)以及算法本身搜索時間較長成本較高而不能滿足現場需求[11]。結合優(yōu)先級規(guī)則的啟發(fā)式調度算法具有較低的時間復雜度，能夠快速做出調度計劃。然而在大量文獻[11-15]研究優(yōu)先級規(guī)則過程中得出一個被廣泛認同的結論：單個同一種規(guī)則并不能在所有算例中都比其他規(guī)則具有最優(yōu)性[13-15]，混合組合多種規(guī)則比單一規(guī)則的求解效果好[11-12]?，F有算法在選擇調度規(guī)則時的缺點是根據調度系統(tǒng)穩(wěn)態(tài)行為進行選擇[16]，當系統(tǒng)狀態(tài)發(fā)生變化時，算法并不能根據系統(tǒng)狀態(tài)的變化作出對應調整，進而改變調度規(guī)則的選擇。因此，需要人工或專家系統(tǒng)進行調整[11]，但是其不足之處在于需要豐富的調度經驗和知識，以及對調度環(huán)境具有較強適應性和高效的反應速度。針對上述算法的不足，本文提出通過機器學習方法對調度規(guī)則進行智能選擇。機器學習通過計算機或智能系統(tǒng)模擬人類的學習行為自動獲取知識和技能，重新組織已有的知識結構，并不斷實現系統(tǒng)的自我完善。MOUELHI-CHIBANI等[16]通過神經網絡根據當前系統(tǒng)狀態(tài)為每臺機器動態(tài)轉化調度規(guī)則，實驗結果優(yōu)于靜態(tài)使用調度規(guī)則；EL-BOURI等[17]在5臺機器和3個調度規(guī)則的小規(guī)模算例實驗下，通過神經網絡為每臺機器選擇調度規(guī)則，實驗結果證明該算法所得結果優(yōu)于所有機器都使用同一種調度規(guī)則的結果；吳秀麗等[18]針對智能制造環(huán)境下的混合流水車間實時調度問題, 提出了基于BP神經網絡的數據驅動的實時調度方法，并驗證了所提方法在不同的調度性能指標下優(yōu)于固定單一調度規(guī)則；曹琛祺等[19]對調度序列進行處理,將作業(yè)車間調度問題轉化為一個分類問題，并使用人工神經網絡構建分類器。對于調度實例,利用訓練得到的分類器得出優(yōu)先級,再利用優(yōu)先級得到調度序列；SHOU[20]設計了一個前饋神經網絡為資源受限項目調度問題選擇合適的優(yōu)先級規(guī)則，其中選擇3個特征作為神經網絡的輸入端，輸出端為9種優(yōu)先級規(guī)則；?ZKAN等[21]通過建立人工神經網絡從3個優(yōu)先級規(guī)則中選擇最合適的規(guī)則分配到不同的算例中，使得項目完工時間最短。RIP作為傳統(tǒng)RCPSP的拓展問題，是一種更為復雜的NP問題[22]。本文提出了基于深度學習的雙層迭代循環(huán)搜索算法。算法上層為一種啟發(fā)式資源搜索框架，通過資源搜索和調整機制逐步縮小資源搜索空間。同時，在滿足上層資源搜索空間的基礎上，設計了下層基于實時調度狀態(tài)的調度優(yōu)先級規(guī)則智能決策算法，并將調度結果反饋到算法上層，指導上層優(yōu)化資源調整。

綜上所述，本文在現有求解RIP算法的基礎上提出了基于深度學習的調度規(guī)則智能分配算法。通過大量實驗，選擇12個特征作為系統(tǒng)輸入特征，采用現階段比較成熟的深度學習模型，通過從歷史離線調度數據中學習隱含的匹配關系，實現在項目調度過程中的每一個階段都能根據當前的調度狀態(tài)動態(tài)智能地分配最優(yōu)的調度規(guī)則，進而完成整個項目作業(yè)的調度計劃。

1 問題描述及數學模型

數學模型中決策變量如下：

目標函數為：

(1)

模型約束為：

(2)

(3)

?j∈J,?t∈T;

(4)

(5)

xjt={0,1},?j∈J,?t∈T。

(6)

其中：式(1)表示目標函數即最小化資源投入成本；式(2)表示確保每一個作業(yè)在給定作業(yè)執(zhí)行工期內完成；式(3)表示時序約束，即每一項作業(yè)在其所有緊前作業(yè)完成后才能開始；式(4)表示作業(yè)一旦開始就不可中斷；式(5)表示項目中所有作業(yè)的結束時間都不超過給定項目工期上限；式(6)表示決策變量的可行域。

2 算法設計

現有文獻提到的算法在選取調度優(yōu)先級規(guī)則時，所選優(yōu)先級規(guī)則貫穿整個調度過程中保持不變。但是，隨著部分作業(yè)的調度完成，由于作業(yè)時序約束影響和資源使用情況的變化，現有算法并不能保證原有優(yōu)先級規(guī)則在后續(xù)作業(yè)調度過程中是最優(yōu)調度規(guī)則。針對現有算法缺乏預測性和前瞻性，本文設計了一種實時調度優(yōu)先級規(guī)則智能決策機制。該策略思路是：對相關調度問題算例的詳細歷史調度數據進行離線學習，通過數據挖掘方法獲取其中潛在的調度規(guī)則知識，建立當前調度狀態(tài)與對應該狀態(tài)下的最優(yōu)調度優(yōu)先級規(guī)則的映射知識網絡，即構建了基于實時調度狀態(tài)的調度優(yōu)先級規(guī)則智能決策系統(tǒng)，能夠根據獲取的實時調度狀態(tài)數據快速切換優(yōu)先級規(guī)則，對每一個調度階段進行最優(yōu)的調度決策，從而實現整個調度過程的智能連續(xù)性調度。本文使用人工神經網絡(Artificial Neural Network, ANN)作為智能決策系統(tǒng)的核心方法，通過BP(back propagation)神經網絡進行調度規(guī)則知識的挖掘。

綜上所述，針對資源投入問題，本文提出了基于ANN的雙層迭代循環(huán)搜索算法(Artificial Neural Network-Iterative Loop, ANN-IL)。ANN-IL的雙層迭代框架為上層是通過啟發(fā)式方法得到可行的資源組合，下層為求解在上層算法輸出結果為資源約束的RCPSP問題的算法，其迭代尋優(yōu)機制為下層算法在上層算法輸出結果基礎上進行調度優(yōu)化，并將調度結果反饋到上層作為其進一步優(yōu)化依據，即算法下層為通過基于實時調度狀態(tài)的調度優(yōu)先級規(guī)則智能決策機制進行作業(yè)調度，并將調度結果反饋到算法上層，指導上層算法對資源組合進行調整。ANN-IL算法流程如圖1所示。

2.1 啟發(fā)式資源搜索框架

(7)

(8)

定義tESTj，tEFTj，tLSTj，tLFTj分別表示通過關鍵路徑法得到的作業(yè)j的最早開始時間、最早結束時間、最晚開始時間和最晚結束時間；tASTj和tAFTj分別表示作業(yè)j在調度時的開始時間和結束時間。

資源調整機制：計算各個作業(yè)的延遲時間Δtj=|tESTj-tASTj|，選擇max{Δtj,?j∈J}對應作業(yè)j的資源需求量rjk更新rk，即rk=rk+rjk；驗證更新后的rk是否可行，若rk不可行，重新計算Δtj，max{Δtj,?j∈J}，更新資源rk=rk+rjk，依此類推直到rk可行；若rk可行，則完成資源調整機制。

ANN-IL算法上層啟發(fā)式資源搜索框架具體步驟流程如下：

步驟2驗證rk是否可行，若不可行，轉步驟3；若可行則令k=1，轉步驟4。

步驟3進行資源調整機制，更新rk=rk+rjk，轉步驟2。

步驟4降低資源k一個單位量，即rk=rk-rjk，調用下層基于實時調度狀態(tài)的調度優(yōu)先級規(guī)則智能決策算法，得到Tc，轉步驟5。

步驟6得到最終資源組合rk，求出目標函數值。

2.2 基于實時調度狀態(tài)的調度優(yōu)先級規(guī)則智能決策算法

基于ANN的雙層迭代循環(huán)搜索算法中下層為基于實時調度狀態(tài)的調度優(yōu)先級規(guī)則智能決策算法，其機制架構如圖2所示。該算法主要有離線訓練模塊和實時調度決策模塊，離線訓練模塊包含訓練樣本構建、樣本數據歸一化處理和人工神經網絡模型構建，實時調度決策模塊包括調度優(yōu)先級規(guī)則智能決策機制和作業(yè)調度過程。實時調度決策模塊通過離線訓練模塊得到的學習模型在調度的每一階段根據當前調度數據，智能決策調度優(yōu)先級規(guī)則，并指導作業(yè)調度進行。

2.2.1 離線訓練模塊

在離線訓練模塊中，首要就是構建用于挖掘調度狀態(tài)和調度規(guī)則間映射關系模型的訓練數據，本文通過文獻[24]所提算法，針對項目調度標準算例庫(Project Scheduling Problem Library, PSPLIB)中算例求解，將求解的結果分為多階段，每一階段代表一個作業(yè)的調度。比如，當整個項目進行到階段i時，可以獲取項目在階段i的狀態(tài)參數Χi，其中Χi=(x1,x2,…,xn)，將該狀態(tài)參數作為人工神經網絡的輸入層特征參數。同時，由于整個項目最終的最優(yōu)結果已確定，從而可以得到該階段下調對應的最優(yōu)調度優(yōu)先級規(guī)則Yi，其中Yi=(y1,…y2,…,ym)，并將此作為人工神經網絡的輸出端數據，因此(Χi,Yi)構成了離線訓練數據樣本。通過基于BP神經網絡的學習機制對樣本數據(Χi,Yi)進行知識挖掘，得到調度過程中每一階段的調度狀態(tài)與調度優(yōu)先級規(guī)則的映射關系，并將其作為可供實時調度模塊使用的調度決策機制，指導整個項目的調度過程。

(1)訓練樣本構建

訓練樣本數據(Χi,Yi)中調度狀態(tài)數據Χi通過文獻[24]所提算法求解所得。首先選擇PSPLIB算例庫中部分不同規(guī)模算例作為訓練數據，通過參考算法得到算例的最終調度方案。然后根據所得調度方案確定作業(yè)調度順序，每調度一個作業(yè)表示調度過程的一個階段，根據調度方案確定該階段下所定義的調度狀態(tài)數據，即人工神經網絡模型的輸入端。調度狀態(tài)特征選取時，需要綜合考慮當前調度狀態(tài)以及對后續(xù)調度狀態(tài)的影響，使得選取的特征具有前瞻性和整體性。本文設置以下12個調度狀態(tài)特征，如表1所示。

結合文獻[20,21],選擇以下8種優(yōu)先級規(guī)則作為輸出端Yi數據，如表2所示。

表1 實時調度狀態(tài)特征表

續(xù)表1

表2 優(yōu)先級規(guī)則集合表

(2)樣本數據歸一化處理

針對人工神經網絡的各維度輸入量Χi存在較大差異數量級問題，本文通過式(9)對樣本輸入數據進行歸一化處理。

(9)

在訓練神經網絡時，對于輸出數據Yi，在調度的每一階段，令能夠選取到該作業(yè)的優(yōu)先級規(guī)則對應數值為1，未能選取到該作業(yè)的規(guī)則對應數值為0。在實時調度階段，根據輸入數據Χi，會生成在區(qū)間[0,1]內的輸出數據Yi，選擇最大數值對應的優(yōu)先級規(guī)則為最終確定的調度規(guī)則。

(3)人工神經網絡模型構建

本文中BP神經網絡前三層以RLUE函數為激活函數，輸出層以Sigmoid函數為激活函數，以網絡的均方誤差為目標函數。采用Adam算法[25]進行優(yōu)化，以目標的負梯度方向對參數進行調整，不斷地修正所有隱層和輸出層神經元的權值和閾值，直到實現最好的優(yōu)化目標，保存此時神經網絡中的所有權重參數。

在訓練模型中，對輸入層而言，每個輸入層的神經元對應一個項目調度狀態(tài)值，輸入層的神經元數目取決于項目調度狀態(tài)的個數。輸出層由對應的規(guī)則組成，由于對于不同的規(guī)則可能對應相同的調度結果，數據訓練的輸出為一組由0和1組成的向量，其中0表示該規(guī)則不是此狀態(tài)下最優(yōu)規(guī)則，1表示該規(guī)則在此狀態(tài)下為最優(yōu)規(guī)則。在預測模型中，輸入層為實際調度中的狀態(tài)特征通過標準化之后的向量。輸出層為一組大小在[0,1]之間，長度為優(yōu)先規(guī)則數量的小數向量。輸出向量與調度規(guī)則一一對應，最大數對應的規(guī)則，則為該調度狀態(tài)下的調度規(guī)則。搭建完成基于BP神經網絡的調度知識模型后，將獲取的數據輸入到該模型中進行訓練，得到項目調度狀態(tài)到調度規(guī)則之間的映射模型，保存模型參數。

2.2.2 實時調度決策模塊

將人工神經網絡與串行調度相結合，構成實時調度決策模塊。在線調度階段，基于BP神經網絡的學習模型能夠依據當前調度階段的系統(tǒng)狀態(tài)，實時決策最佳調度優(yōu)先級規(guī)則，具體步驟如下：

步驟1初始化，j=0，tS0=0，N={0}，U={1,2,…J}，待調度作業(yè)集合D=?。

步驟2計算當前階段下12個調度狀態(tài)特征，根據人工神經網絡模型，從8種調度優(yōu)先級規(guī)則中選擇最佳調度規(guī)則λ，轉步驟3。

步驟3根據調度優(yōu)先級規(guī)則λ，確定待調度作業(yè)j，更新D={j}，轉步驟4。

步驟4根據串行調度機制對作業(yè)j調度，確定tSj，更新集合N=N∪{j}，U=CU(N∩U)；如果U≠?，則轉步驟2；如U=?，則轉步驟5。

步驟5調度完成，輸出最終調度結果和Tc。

3 數值實驗與分析

為驗證本文設計算法的有效性，選擇PSPLIB標準算例庫中作業(yè)規(guī)模為30作業(yè)，60作業(yè)，90作業(yè)規(guī)模算例進行實驗，實驗平臺采用Windows10 64位操作系統(tǒng)，Intel Core i7-8700、3.20 GHz CPU、16.00 G RAM，開發(fā)環(huán)境為Pycharm和Python 3.7。人工神經網絡的相關參數為：輸入層神經元數目12，輸出層神經元數目8，隱層1神經元數目100，隱層2神經元數目50，訓練樣本數80 000個算例。

2.1 兩組圍術期指標比較 觀察組手術時間、術后肛門排氣時間及住院時間均短于對照組(P<0.05)；觀察組術中出血量少于對照組(P<0.05)。見表1。

針對不同規(guī)模算例的RCPSP問題，通過單一調度規(guī)則啟發(fā)式算法和基于實時調度狀態(tài)的調度優(yōu)先級規(guī)則智能決策算法之間的性能對比，驗證該算法的有效性。實驗結果如表3～表5所示，其中ANN表示本文算法求得算例的解，AVG表示8種單一調度規(guī)則啟發(fā)式算法求得算例解的平均值，即

AVG=(SPT+LFT+MST+MTS+

OGRPW+GRD+TRS+WRUP)/8；

GAP1=100%×(min{SPT,LFT,MST,

MTS,OGRPW,GRD,TRS,

WRUP}-ANN)/ANN;

GAP2=100%×(AVG-ANN)/ANN。

表3 30作業(yè)規(guī)模實驗結果

續(xù)表3

表4 60作業(yè)規(guī)模實驗結果

表5 90作業(yè)規(guī)模實驗結果

為進一步驗證本文求解RIP所設計的雙層迭代循環(huán)搜索算法(ANN-IL)的有效性，通過與改進文獻[24]所提出的算法(P-GA)進行對比實驗，不同算例規(guī)模的詳細實驗數據如表6～表8所示。表中：GAP為兩種算法求解算例的目標函數值的偏差百分比，GAP=100%×[(ANN-IL)-(P-GA)]/(P-GA);tA，tG分別表示兩種算法的求解時間(單位：s)。

表6 30作業(yè)規(guī)模兩算法對比實驗結果

表7 60作業(yè)規(guī)模兩算法對比實驗結果

表8 90作業(yè)規(guī)模兩算法對比實驗結果

從表6～表8可以得出以下結論：針對30個作業(yè)的小規(guī)模算例，本文所提算法ANN-IL與對比的遺傳算法差距較小，其中一個算例的值甚至優(yōu)于遺傳算法的值。兩種算法的平均誤差在2%左右，證明了該ANN-IL算法在求解RIP時解的有效性。由于ANN-IL相當于一種啟發(fā)式方法，在求解速度方面，兩種算法不是一個數量級，ANN-IL的平均時間不到1 s，而遺傳算法的平均時間為68 s。針對60，90個作業(yè)的中大規(guī)模算例，ANN-IL的結果次于遺傳算法，誤差大概在3.8%～5%左右。但在求解速度方面，60規(guī)模算例，ANN-IL運算時間平均約3 s，遺傳算法平均求解時間約為186 s，是ANN-IL運算時間的60倍；90規(guī)模算例實驗中，遺傳算法平均求解時間約為ANN-IL運算時間的60倍。如圖5所示為不同作業(yè)規(guī)模下兩算法實驗結果比較，虛線表示兩算法所求目標函數值相等，由圖5可得ANN-IL算法求得的解與對比算法所求解的差值在一個極小范圍內波動。由于P-GA算法運算時間波動幅度較大，為方便比較，通過對CPU時間做底數為10的對數處理，由圖6可得本文算法ANN-IL運算時間遠小于對比算法時間。綜上可得本文設計算法在求解精度誤差可接受范圍內可以極大縮短求解時間，求解效率遠高于傳統(tǒng)的元啟發(fā)式算法。

4 結束語

本文提出一種基于人工神經網絡的雙層迭代循環(huán)搜索算法(ANN-IL)實時調度求解資源投入問題。該算法通過數據挖掘方法獲取實時調度狀態(tài)和對應的最優(yōu)調度優(yōu)先級規(guī)則的映射知識網絡，即構建了基于實時調度狀態(tài)的調度優(yōu)先級規(guī)則智能決策系統(tǒng)，能夠根據獲取的實時調度狀態(tài)數據快速切換優(yōu)先級規(guī)則，對每一個調度階段進行最優(yōu)的調度決策，從而實現整個調度過程的智能連續(xù)性調度。實驗數據表明，本文設計的算法性能上優(yōu)于任何單一優(yōu)先級調度規(guī)則，運算時間上遠遠小于常用的元啟發(fā)式算法。因此，本文所設計的基于實時調度狀態(tài)的調度優(yōu)先級規(guī)則智能決策系統(tǒng)為合理指導調度過程提供了技術支持，提高了生產調度決策的實時性和智能性。在今后研究中，考慮對不確定環(huán)境下的資源投入問題做進一步研究，如資源可使用情況不確定，緊急訂單插入等情況。