陸志強(qiáng)，任逸飛，許則鑫

(同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804)

0 引言

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

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

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

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

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

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

目標(biāo)函數(shù)為：

(1)

模型約束為：

(2)

(3)

?j∈J,?t∈T;

(4)

(5)

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

(6)

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

2 算法設(shè)計(jì)

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

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

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

(7)

(8)

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

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

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

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

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

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

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

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

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

2.2.1 離線訓(xùn)練模塊

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

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

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

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

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

續(xù)表1

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

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

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

(9)

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

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

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

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

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

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

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

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

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

步驟4根據(jù)串行調(diào)度機(jī)制對(duì)作業(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ù)值實(shí)驗(yàn)與分析

為驗(yàn)證本文設(shè)計(jì)算法的有效性，選擇PSPLIB標(biāo)準(zhǔn)算例庫(kù)中作業(yè)規(guī)模為30作業(yè)，60作業(yè)，90作業(yè)規(guī)模算例進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)平臺(tái)采用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)絡(luò)的相關(guān)參數(shù)為：輸入層神經(jīng)元數(shù)目12，輸出層神經(jīng)元數(shù)目8，隱層1神經(jīng)元數(shù)目100，隱層2神經(jīng)元數(shù)目50，訓(xùn)練樣本數(shù)80 000個(gè)算例。

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

針對(duì)不同規(guī)模算例的RCPSP問題，通過單一調(diào)度規(guī)則啟發(fā)式算法和基于實(shí)時(shí)調(diào)度狀態(tài)的調(diào)度優(yōu)先級(jí)規(guī)則智能決策算法之間的性能對(duì)比，驗(yàn)證該算法的有效性。實(shí)驗(yàn)結(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ī)模實(shí)驗(yàn)結(jié)果

續(xù)表3

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

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

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

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

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

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

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

4 結(jié)束語

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