陸志強，任逸飛，許則鑫

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

0 引言

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

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

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

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

1 問題描述及數(shù)學模型

數(shù)學模型中決策變量如下：

目標函數(shù)為：

(1)

模型約束為：

(2)

(3)

?j∈J,?t∈T;

(4)

(5)

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

(6)

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

2 算法設計

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

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

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

(7)

(8)

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

資源調(diào)整機制：計算各個作業(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可行，則完成資源調(diào)整機制。

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

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

步驟3進行資源調(diào)整機制，更新rk=rk+rjk，轉(zhuǎn)步驟2。

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

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

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

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

2.2.1 離線訓練模塊

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

(1)訓練樣本構(gòu)建

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

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

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

續(xù)表1

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

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

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

(9)

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

(3)人工神經(jīng)網(wǎng)絡模型構(gòu)建

本文中BP神經(jīng)網(wǎng)絡前三層以RLUE函數(shù)為激活函數(shù)，輸出層以Sigmoid函數(shù)為激活函數(shù)，以網(wǎng)絡的均方誤差為目標函數(shù)。采用Adam算法[25]進行優(yōu)化，以目標的負梯度方向?qū)?shù)進行調(diào)整，不斷地修正所有隱層和輸出層神經(jīng)元的權(quán)值和閾值，直到實現(xiàn)最好的優(yōu)化目標，保存此時神經(jīng)網(wǎng)絡中的所有權(quán)重參數(shù)。

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

2.2.2 實時調(diào)度決策模塊

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

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

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

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

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

步驟5調(diào)度完成，輸出最終調(diào)度結(jié)果和Tc。

3 數(shù)值實驗與分析

為驗證本文設計算法的有效性，選擇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。人工神經(jīng)網(wǎng)絡的相關參數(shù)為：輸入層神經(jīng)元數(shù)目12，輸出層神經(jīng)元數(shù)目8，隱層1神經(jīng)元數(shù)目100，隱層2神經(jīng)元數(shù)目50，訓練樣本數(shù)80 000個算例。

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

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

續(xù)表3

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

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

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

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

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

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

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

4 結(jié)束語

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