盧 斌，陸志強，張永峰

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

0 引言

對于飛機等大型復(fù)雜裝備制造企業(yè)而言，建立科學(xué)合理的裝配調(diào)度計劃是管理者實現(xiàn)高效管理生產(chǎn)項目的重要前提[1]。飛機裝配調(diào)度計劃的制定與執(zhí)行受到諸多因素的影響，包括裝配作業(yè)間的優(yōu)先級約束、各類資源的供給數(shù)量限制、作業(yè)裝配模式的選擇以及計劃執(zhí)行過程中的不確定性因素等。目前，鄭倩等[2]和LU等[3]認為飛機裝配調(diào)度問題需以滿足可更新資源限制和作業(yè)優(yōu)先順序兩類主要約束為前提，因此可將其抽象為資源受限項目調(diào)度問題(Resource Constrained Project Scheduling Problem, RCPSP)及其擴展問題，并設(shè)計相應(yīng)的元啟發(fā)式算法進行求解。盡管已有學(xué)者在飛機裝配背景下就RCPSP問題及其相關(guān)衍生問題進行了較為充分的研究[4-7]，但相關(guān)研究工作大多致力于模板計劃的制定，且均假定其物料能準時供應(yīng)。然而，在實際裝配過程中，飛機裝配所需的零部件種類復(fù)雜且數(shù)量巨大[8]，各零部件供應(yīng)商可能存在產(chǎn)能不足、質(zhì)量缺陷、設(shè)備故障、材料短缺等問題，物料供應(yīng)的準時性難以保證。此外，裝配作業(yè)時常因物料缺失、損壞、不符合裝配要求等突發(fā)擾動導(dǎo)致現(xiàn)場缺料而推遲執(zhí)行。物料供應(yīng)延期不僅影響裝配作業(yè)自身，還會干擾后續(xù)作業(yè)的正常執(zhí)行，使生產(chǎn)管理人員不得不對裝配現(xiàn)場的原有資源配置進行調(diào)整，從而增加額外的調(diào)度成本。因此，在裝配計劃執(zhí)行過程中，提供一種能有效應(yīng)對物料供應(yīng)不確定性、實現(xiàn)調(diào)度成本優(yōu)化的反應(yīng)調(diào)度方法具有重要意義。由此，本文對物料供應(yīng)不確定環(huán)境下的飛機裝配調(diào)度問題展開研究。

現(xiàn)有研究中，處理不確定性問題的方法主要包括前攝—反應(yīng)調(diào)度和反應(yīng)調(diào)度兩類，其中前攝—反應(yīng)調(diào)度通過合理安排時間緩沖來提升前攝計劃的魯棒性，在執(zhí)行前攝計劃階段采用事件驅(qū)動的反應(yīng)策略進行計劃調(diào)整。MA等[9]考慮資源可用性不確定的項目調(diào)度問題，先以解魯棒性為優(yōu)化指標生成前攝計劃，執(zhí)行階段采用反應(yīng)式調(diào)度策略，以最小化與前攝計劃的偏差為目標函數(shù)生成新調(diào)度計劃。韓笑樂等[10]針對船舶到港時間不確定環(huán)境下的集裝箱碼頭泊位堆場資源調(diào)度問題，設(shè)計了基于前攝—反應(yīng)的魯棒性調(diào)度方法。上述文獻在制定前攝計劃階段，往往在事先假定不確定性因素服從某一概率分布的條件下進行魯棒性優(yōu)化，但無論前攝計劃的魯棒性有多高，當(dāng)計劃實際執(zhí)行過程中的某些干擾并沒有發(fā)生時，先前加入的緩沖便會造成浪費。

反應(yīng)調(diào)度方法可根據(jù)干擾觸發(fā)方式的不同，分為事件驅(qū)動策略、周期驅(qū)動策略和事件與周期混合驅(qū)動策略3類。

(1)事件驅(qū)動策略，即在干擾事件發(fā)生時立刻進行重調(diào)度，其主要適用于干擾因素有突發(fā)性且可預(yù)知性較差的情況。LI等[11]考慮單元式制造系統(tǒng)中突發(fā)的機器故障干擾，采用整數(shù)規(guī)劃方法將反應(yīng)調(diào)度問題描述為離散優(yōu)化問題，并通過結(jié)合混合二進制粒子群算法和模擬退火算法進行求解。CHAKRABORTTY等[12]在RCPSP問題的背景下，考慮資源中斷的干擾場景，建立了混合整數(shù)規(guī)劃模型，提出多種啟發(fā)式算法進行求解。RAHMANI等[13]針對流水線車間生產(chǎn)過程中插入新作業(yè)的干擾問題，建立了以最小化作業(yè)拖期時間和穩(wěn)定性代理指標加權(quán)和為目標的數(shù)學(xué)模型，并設(shè)計了變鄰域搜索算法進行求解。

(2)周期驅(qū)動策略，即預(yù)先定義重調(diào)度的滾動時域，然后通過獲取每個滾動時域末制造系統(tǒng)的實際狀態(tài)來確定下一滾動時域的初始條件，并進行重調(diào)度。SOURIRAJAN等[14]針對半導(dǎo)體制造車間實時狀態(tài)不斷變化的問題，采用周期性滾動時域調(diào)度策略求解加工調(diào)度子問題。

(3)事件與周期混合驅(qū)動策略則結(jié)合前兩種策略，即首先在每個滾動時域初進行重調(diào)度，在時域內(nèi)進行基于事件驅(qū)動的再調(diào)度。周炳海等[15]針對物料搬運系統(tǒng)運行中的路徑?jīng)_突干擾問題，結(jié)合滾動時域方法和時域內(nèi)基于事件驅(qū)動的再調(diào)度策略設(shè)計了搬運避碰調(diào)度方法。

綜合上述文獻發(fā)現(xiàn)，現(xiàn)有的反應(yīng)調(diào)度方法往往在不確定性事件發(fā)生時或到達滾動時域節(jié)點時進行重調(diào)度處理。然而對于飛機裝配過程而言，除了要考慮計劃執(zhí)行過程中突發(fā)的物料缺失、損壞、不符合裝配要求等干擾問題以外，還應(yīng)處理各供應(yīng)商的物料交貨期不確定的情況。事實上，由于飛機裝配周期較長，各物料的供應(yīng)過程易受外部不確定因素影響，物料交貨期隨著裝配進程的推進不斷變化。而現(xiàn)有的反應(yīng)調(diào)度方法在重調(diào)度過程僅利用了決策點的確定性信息，無法有效應(yīng)對不確定性因素不斷改變的情況，忽視了主動改善的優(yōu)勢。

實際上，在全球航空制造業(yè)普遍采用“主制造商—供應(yīng)商”模式的背景下，飛機制造商通過同各供應(yīng)商建立起戰(zhàn)略合作伙伴關(guān)系、打造基于信息共享與集成的供應(yīng)鏈管控體系[16]等方法，可實現(xiàn)對物料供應(yīng)過程的實時追蹤。此外，供應(yīng)商運用大量智能化的數(shù)據(jù)采集和存儲設(shè)備，在獲取實時監(jiān)測數(shù)據(jù)的同時，積累了大量關(guān)于物料交貨的歷史數(shù)據(jù)。這些技術(shù)條件以及機器學(xué)習(xí)預(yù)測技術(shù)的長足發(fā)展為飛機制造商實時掌握物料供應(yīng)狀態(tài)、實現(xiàn)物料交貨期預(yù)測提供了基礎(chǔ)。由此，本文提出一種基于數(shù)據(jù)預(yù)測的決策方法。相比現(xiàn)有的反應(yīng)調(diào)度方法，基于數(shù)據(jù)預(yù)測的決策方法能夠充分利用不斷變化的物料供應(yīng)狀態(tài)信息，預(yù)測未來可能出現(xiàn)的物料交貨場景，并事先主動調(diào)整原有的調(diào)度計劃，從而提升裝配過程應(yīng)對未來不確定性的能力。

現(xiàn)有文獻已對交貨期預(yù)測問題進行了較為深入的研究。孫德廠等[17]將不確定性要素分為外部環(huán)境不確定性和生產(chǎn)系統(tǒng)不確定性兩類，分析了它們對交貨期的影響機制并建立了交貨期模型，提出了基于支持向量回歸(Support Vector Regression, SVR)的交貨期預(yù)測方法。朱雪初等[18]以晶圓生產(chǎn)為背景，將加工周期影響因素歸納為待加工工件和生產(chǎn)系統(tǒng)相關(guān)的屬性與狀態(tài)，并提出基于ReliefF和SVR的產(chǎn)品完工周期預(yù)測方法;CHEN等[19]將模糊C-均值等聚類算法同BP神經(jīng)網(wǎng)絡(luò)結(jié)合，提高了晶圓加工周期預(yù)測精度。WANG等[20]通過基于信息熵的關(guān)鍵因素識別方法和基于模糊C-均值聚類的BP神經(jīng)網(wǎng)絡(luò)完成晶圓交貨期的預(yù)測。上述文獻大多利用支持向量回歸或神經(jīng)網(wǎng)絡(luò)等單個學(xué)習(xí)器對交貨期進行預(yù)測，對于規(guī)模較大的復(fù)雜系統(tǒng)而言，其泛化性能較差，且由于此類學(xué)習(xí)器固有的淺層結(jié)構(gòu)，模型參數(shù)數(shù)量會隨著變量增加而增多，導(dǎo)致其在包含較多變量的大規(guī)模系統(tǒng)中的推理能力下降[21]。事實上，上述交貨期預(yù)測方法仍難以滿足飛機裝配過程對物料交貨期的預(yù)測需求。一方面，飛機裝配所需物料大多涉及復(fù)雜的供應(yīng)系統(tǒng)，物料交貨期相關(guān)影響因素較多，對預(yù)測方法的適應(yīng)性提出了更高要求；另一方面，由于預(yù)測所得信息將用于指導(dǎo)裝配調(diào)度的優(yōu)化決策，預(yù)測方法還應(yīng)具有較優(yōu)的推理能力和預(yù)測準確率。針對上述需求，本文通過研究物料交貨期與物料供應(yīng)過程相關(guān)因素的映射關(guān)系，提出了基于XGBoost算法的物料交貨期預(yù)測模型。并以此為基礎(chǔ)，借鑒文獻[22]中的基于兩階段近似優(yōu)化的動態(tài)決策框架，進一步分析物料供應(yīng)不確定性對調(diào)度計劃執(zhí)行過程的影響形式，建立包含上述映射關(guān)系表達式在內(nèi)的動態(tài)調(diào)度模型。針對模型決策邏輯，設(shè)計了雙層循環(huán)迭代搜索算法進行求解。對于執(zhí)行計劃過程中突發(fā)的物料擾動問題，通過設(shè)計基于松弛時間的反應(yīng)機制對計劃進行修復(fù)。

1 問題描述與決策框架

1.1 問題描述

基于物料交貨期預(yù)測的飛機裝配動態(tài)調(diào)度問題，是通過確定和量化影響物料交貨期的主要因素，結(jié)合物料在生產(chǎn)運輸過程中積累的相關(guān)歷史數(shù)據(jù)建立物料交貨期預(yù)測模型，并以此為基礎(chǔ)，進一步分析物料供應(yīng)不確定性對調(diào)度計劃執(zhí)行過程的影響形式，采用基于事件與周期混合驅(qū)動的滾動決策框架，優(yōu)化決策作業(yè)的開始時間和執(zhí)行模式以減少其與模板計劃的偏差，從而達到最小化反應(yīng)調(diào)度總成本的目的。以飛機裝配項目為背景，該問題涉及如下假設(shè)：

(1)裝配項目包含J個裝配作業(yè)和K種共享的可更新資源。裝配作業(yè)間存在優(yōu)先級關(guān)系，且每個作業(yè)包含若干種裝配模式，特定的裝配模式對應(yīng)特定的作業(yè)執(zhí)行工期和可更新資源需求量。將時間軸進行離散化處理，每種資源在任意時刻的需求量不應(yīng)超過資源供給上限。

(2)裝配項目的物料集合為Ι={1,2,…,|I|}。為了實現(xiàn)飛機裝配線的高效運作，作業(yè)所需物料均采取齊套的方式，從中央倉庫向相應(yīng)裝配位置進行準時化配送。

(3)在臨近裝配項目啟動階段，已知各物料的上線生產(chǎn)時間，本文將物料交貨期b定義為物料從上線生產(chǎn)到送達飛機裝配中央倉庫的時間。物料交貨期主要包括生產(chǎn)時間和運輸時間兩個部分。生產(chǎn)時間是指物料上線生產(chǎn)至完工的時間，運輸時間是指從物料完工后至供應(yīng)商送達裝配中央倉庫的時間。其中，影響生產(chǎn)時間的定性因素主要包括物料屬性O(shè)(如物料的產(chǎn)品類型等)、車間的生產(chǎn)狀態(tài)Q(如上線生產(chǎn)時各設(shè)備前的加工隊列等)以及生產(chǎn)環(huán)節(jié)出現(xiàn)的異常情況U(如設(shè)備故障、材料缺失、工人短缺、返工等異常事件)；影響運輸時間的定性因素主要包括運輸方案S(包括運輸方式、運輸路線等)、運輸環(huán)節(jié)出現(xiàn)的異常情況E(如因其他待運輸產(chǎn)品未完工而造成的等待、天氣狀況惡劣、交通管制等)。由此，物料交貨期b可通過上述5個主要因素的映射關(guān)系表達式來描述，即

b=F(O,Q,U,S,E)。

(1)

本文通過上述5個因素的相關(guān)歷史數(shù)據(jù)建立物料交貨期預(yù)測模型。將待預(yù)測數(shù)據(jù)定義為物料i∈I在某時刻采集到的5個因素相關(guān)數(shù)據(jù)，即(Oi,Qi,Ui,Si,Ei)。對于特定的飛機裝配項目而言，物料屬性和運輸方案可通過簽訂采購合同的方式提前確定，且在臨近裝配項目啟動階段，物料上線生產(chǎn)時的車間生產(chǎn)狀態(tài)可提前掌握，因此可認為Oi、Qi和Si是固定的。物料在生產(chǎn)、運輸環(huán)節(jié)出現(xiàn)的異常情況會隨著時間的推進而逐漸明確，即Ui和Ei是隨時間不斷更新的。

(4)模板裝配計劃已定，即任意作業(yè)的模板開始時間和模板裝配模式已確定。對飛機裝配項目而言，為了避免出現(xiàn)作業(yè)即將開始而物料尚未到達的情形，作業(yè)的實際開始時間不應(yīng)早于模板計劃開始時間。作業(yè)一旦出現(xiàn)延期執(zhí)行的情況，將造成人員、配送、倉儲等與之相耦合的環(huán)節(jié)發(fā)生變動而產(chǎn)生一定成本。作業(yè)更改原有裝配模式會導(dǎo)致作業(yè)資源配置的重新調(diào)整，從而產(chǎn)生額外切換成本。因此，本文考慮的反應(yīng)調(diào)度總成本包含與模板計劃的偏差成本和裝配模式切換成本。

1.2 物料交貨期預(yù)測模型

如1.1節(jié)所述，物料交貨期主要受到物料屬性、車間的生產(chǎn)狀態(tài)、運輸方案、生產(chǎn)運輸環(huán)節(jié)出現(xiàn)的異常情況等多方面因素的影響，因此需建立有效的預(yù)測模型來準確描述物料交貨期與相關(guān)影響因素之間的映射關(guān)系?？紤]到物料交貨期與相關(guān)影響因素之間的非線性關(guān)系以及XGBoost算法在非線性預(yù)測應(yīng)用領(lǐng)域的適用性[23]，本文采用XGBoost算法構(gòu)建物料交貨期預(yù)測模型。

XGBoost算法是基于梯度增強決策樹算法演化而來的集成學(xué)習(xí)算法。該算法以決策樹為基學(xué)習(xí)器，在樣本特征集合中隨機選擇一部分特征，并通過不斷地進行特征分裂來生成一棵決策樹，對于生成的每一棵樹都采用梯度下降法擬合先前已生成樹模型的殘差，擬合過程可獲得當(dāng)前樹的預(yù)測模型，將每棵樹預(yù)測的樣本輸出值累計相加即獲得樣本最終的預(yù)測值。本文以分類回歸樹(Classification and Regression Tree, CART)作為基學(xué)習(xí)器，使用XGBoost算法構(gòu)建物料交貨期的預(yù)測模型，預(yù)測過程如下：

(1)定義目標函數(shù)。

(2)

(3)

其中P表示回歸樹葉子節(jié)點個數(shù)，ωφ表示第φ個葉子節(jié)點的權(quán)重，系數(shù)α和λ分別為葉子樹和葉子權(quán)重懲罰正則項。

(4)

式中C為常數(shù)。為找到一個能使優(yōu)化目標最小的fφ(Xg)，將上式在fφ(Xg)=0處進行二階泰勒展開：

(5)

(6)

(7)

(8)

(3)以最優(yōu)值為基礎(chǔ)，輸入所有樣本數(shù)據(jù)進行建樹。葉子節(jié)點的分裂過程是建樹的核心，在每個節(jié)點處隨機選擇部分樣本特征，并對這些特征選擇最優(yōu)分裂節(jié)點。選擇分裂節(jié)點時，定義增益

(9)

(4)在前一棵樹的基礎(chǔ)上重復(fù)建樹，直至達到樹的總量即迭代次數(shù)為止，完成XGBoost離線訓(xùn)練。

(5)在實際預(yù)測中，根據(jù)待預(yù)測樣本的輸入向量和離線訓(xùn)練模型逐一輸出每棵回歸樹的預(yù)測值，并將這些預(yù)測值累計相加，得到輸入向量的預(yù)測值。

1.3 物料供應(yīng)不確定環(huán)境下的決策框架

由于飛機裝配周期較長，管理人員需對物料供應(yīng)過程中的一系列因素(如倉庫的存儲能力及費用、訂貨費用和訂貨次數(shù)等)進行綜合考量，制定合理的物料采購訂單，使供應(yīng)商按規(guī)定時間向中央倉庫運送待裝配物料，因此物料的實際交貨期通常無法在裝配項目啟動前全部知曉，而是隨著裝配項目的推進逐步明確。此外，在物料到達中央倉庫以前，管理人員只能通過供應(yīng)商提供的最新狀態(tài)數(shù)據(jù)對物料交貨期進行預(yù)先估測。基于上述特點，對于物料交貨期尚未明確的作業(yè)，本文將利用其物料在生產(chǎn)運輸過程中積累的歷史數(shù)據(jù)訓(xùn)練物料交貨期預(yù)測模型，在此基礎(chǔ)上，根據(jù)物料在實際生產(chǎn)運輸中的最新狀態(tài)數(shù)據(jù)，對物料交貨期進行實時預(yù)測。預(yù)測所得的物料交貨期，將用以指導(dǎo)作業(yè)的調(diào)度決策；而對于物料實際交貨期已經(jīng)明確的作業(yè)，若出現(xiàn)因物料交貨期延遲導(dǎo)致作業(yè)無法按原計劃執(zhí)行的情形，則需重新優(yōu)化其裝配開始時間和裝配模式。

如圖1a所示，按照物料實際交貨情況對裝配調(diào)度進行周期劃分：將第q個調(diào)度周期的決策時刻記為Tq；在模板計劃開始執(zhí)行時刻(記為T1)，對于物料交貨期均已明確的作業(yè)(作業(yè)1、2、3和4)，可在第1個調(diào)度周期進行固定性決策；在模板計劃中，找到這些作業(yè)中最遲開始的作業(yè)(作業(yè)4)，將該作業(yè)的啟動備料和配送任務(wù)時刻記為T2；當(dāng)時間推進至T2時刻，按照當(dāng)前物料實際交貨情況重新確定在第2個調(diào)度周期參與固定性決策的作業(yè)(作業(yè)5、6、7、8和9)；當(dāng)時間推進至T3時刻，再次確定在第3個調(diào)度周期參與固定性決策的作業(yè)(作業(yè)10、11、12和13)；……依此類推，直到裝配項目執(zhí)行完畢。綜合上述分析，在任意決策時刻Tq，可將作業(yè)劃分為A、B、C類3類，相應(yīng)的作業(yè)集合記為JA、JB、JC。各類作業(yè)的決策邏輯描述如下：

(1)A類，備料及配送任務(wù)已經(jīng)開始的作業(yè)。此類作業(yè)無需決策，按上一周期的計劃執(zhí)行。

(2)B類，可在當(dāng)前調(diào)度周期內(nèi)啟動備料及配送任務(wù)的作業(yè)。此類作業(yè)的物料交貨期均已明確。對于B類作業(yè)，需引入輔助決策變量uj作為延遲判定因子，用于判斷作業(yè)j是否需要延遲至下一周期進行決策，具體判定方法為：若作業(yè)被延遲至下一周期決策，則uj=1，作業(yè)歸入B1類；若作業(yè)在當(dāng)前周期進行決策，則uj=0，作業(yè)歸入B0類。B0類作業(yè)進行固定性決策，其決策結(jié)果作為新的計劃，將替代該階段的模板計劃并被實際執(zhí)行，B1類與C類進行相同操作。

在各個調(diào)度周期內(nèi)，新的周期計劃得到執(zhí)行，但現(xiàn)場裝配過程中仍會面臨突發(fā)的物料缺失、損壞、不符合裝配要求等擾動。出現(xiàn)此類擾動時，可將該作業(yè)視為一個被延期的新作業(yè)，同時要求倉庫部門緊急配送問題物料的備用件或協(xié)調(diào)供應(yīng)商長期派駐在裝配中心的返工小組，對相應(yīng)問題物料進行緊急返工后重新配送物料，可獲知作業(yè)預(yù)計延期時間為dtj。為了保持新計劃執(zhí)行的穩(wěn)定性，以避免重調(diào)度過于頻繁，本文通過設(shè)計實時的反應(yīng)機制來應(yīng)對此類突發(fā)情況。綜上所述，本文構(gòu)建了一種事件與周期混合驅(qū)動的滾動決策框架如圖1b所示。

1.4 數(shù)學(xué)模型

本節(jié)構(gòu)建任意滾動決策時刻Tq的數(shù)學(xué)模型。模型的符號說明如表1所示。

表1 符號說明

根據(jù)上述符號及其定義，建立如下數(shù)學(xué)模型：

(10)

(11)

M(uj-1)

(12)

(13)

(14)

(15)

?j∈J,?h∈Pj；

(16)

?k∈K,?t∈T；

(17)

bi=F(Oi,Qi,Ui,Si,Ei),?j∈JC,i∈Ij；

(18)

sj-pT≥di+bi,?j∈JC,i∈Ij；

(19)

(20)

(21)

xjmjt∈{0,1},?j∈J,?mj∈Mj,?t∈T；

面對靜寧縣農(nóng)村飲水困難問題突出、供水工程建設(shè)任務(wù)繁重的形勢，要積極謀劃，發(fā)揮公共財政對水利的主導(dǎo)作用，在爭取公共財政投資和金融支持建設(shè)主體工程的同時，多渠道籌集資金，鼓勵農(nóng)民自愿投資投勞建設(shè)供水入戶工程，吸引社會資金投入提高供水入戶標準。建立以公共財政投入和金融支持、農(nóng)民投資投勞、社會資本參與為主要支撐的農(nóng)村供水工程投資穩(wěn)定增長機制。力爭到“十三五”末徹底解決靜寧縣農(nóng)村供水問題，全面提升飲水安全標準，為改善民生、促進經(jīng)濟社會又好又快發(fā)展奠定基礎(chǔ)。

(22)

uj∈{0,1},?j∈JB。

(23)

其中：式(10)以最小化與模板計劃的偏差成本和裝配模式切換成本之和為目標函數(shù)；式(11)表示對A類作業(yè)的決策變量進行賦值；式(12)為決策周期約束，利用輔助決策變量uj將B類作業(yè)劃分為B0和B1兩類作業(yè)，M為足夠大的數(shù)；式(13)和式(14)分別表示決策變量xjmjt與sj、aj間的等式關(guān)系；式(15)表示任意作業(yè)只能選擇一種裝配模式且一旦開始無法變更；式(16)表示作業(yè)間優(yōu)先級關(guān)系約束，即任意作業(yè)必須在其所有緊前作業(yè)完成之后才能開始；式(17)表示任意時刻下各作業(yè)對任意可更新資源的需求量不得超過資源容量上限；式(18)表示任意C類作業(yè)的物料交貨期與相關(guān)影響因素間的映射關(guān)系表達式，可通過預(yù)測模型實現(xiàn)；式(19)和式(20)表示任意B、C類作業(yè)的開始備料時間不得早于其所有物料送達倉庫的時間；式(21)表示任意作業(yè)的開始時間不得早于其模板開始時間；式(22)和式(23)表示各決策變量的定義域。

2 算法設(shè)計

為適應(yīng)本文飛機裝配動態(tài)調(diào)度問題存在多階段決策的需求，設(shè)計了融合在線預(yù)測機制的雙層循環(huán)迭代搜索算法，其基本思路如圖2所示。首先通過TS1上層模塊搜索固定性決策，其決策結(jié)果包括B0與B1類作業(yè)的劃分決策以及B0類作業(yè)的開始時間和裝配模式?；谏鲜鰶Q策結(jié)果，結(jié)合決策時刻所掌握的物料交貨期相關(guān)參數(shù)和物料交貨期預(yù)測模型，在線預(yù)測C類作業(yè)的物料交貨期，然后利用TS2下層模塊搜索B1和C類作業(yè)的預(yù)測決策結(jié)果。本文通過計算兩個階段決策結(jié)果的目標函數(shù)值來評價固定性決策的優(yōu)劣性。雙層循環(huán)迭代搜索算法以作業(yè)列表和模式列表的雙鏈結(jié)構(gòu)為編碼方式，通過TS1、TS2兩層嵌套運用禁忌搜索算法的模式搜索最優(yōu)解，其具體細節(jié)在2.1節(jié)中詳細闡述。此外，對于新計劃執(zhí)行中的突發(fā)性擾動，本文提出基于松弛時間的反應(yīng)機制，其具體步驟在2.2節(jié)中詳細闡述。

2.1 雙層循環(huán)迭代搜索算法

考慮到禁忌搜索算法在鄰域搜索及求解效率方面的優(yōu)勢，雙層循環(huán)迭代搜索算法的上下層均以禁忌搜索算法為算法框架。具體而言，算法上層(TS1)采用作業(yè)列表和模式列表的雙鏈編碼方式對B類作業(yè)的執(zhí)行順序和相應(yīng)裝配模式展開搜索。同時，對搜索到的每一個編碼個體，采用串行調(diào)度生成算法進行解碼。串行解碼過程中，可根據(jù)作業(yè)能否在當(dāng)前周期安排執(zhí)行，對B類作業(yè)進行進一步劃分，B1類作業(yè)的決策將被延遲至預(yù)測決策階段進行。算法下層(TS2)基于TS1作業(yè)劃分的基礎(chǔ)上，采用與TS1相同的編碼方式對B1和C類作業(yè)的執(zhí)行順序和相應(yīng)裝配模式展開搜索。同時，對搜索到的每一個編碼個體，在TS1對B0類作業(yè)的決策結(jié)果基礎(chǔ)上采用串行調(diào)度生成算法進行解碼，并計算調(diào)度計劃的評價指標。雙層循環(huán)迭代搜索算法框架如圖3所示。

2.1.1 TS1:搜索固定性決策

算法上層TS1采用作業(yè)列表和模式列表的雙鏈編碼方式搜索固定性決策，其編碼示例如圖4a所示。每個編碼位的數(shù)字均包含了作業(yè)的編號和裝配模式編號，編碼結(jié)構(gòu)滿足作業(yè)間的優(yōu)先級關(guān)系約束，即每個作業(yè)的編碼位置都應(yīng)置于其直接緊后作業(yè)之前。此外，由于A類作業(yè)無需決策，將其置于編碼的最高優(yōu)先級位置；B類作業(yè)需在本階段進行固定性決策，將其置于次優(yōu)先級位置；C類作業(yè)不在該階段決策，置于編碼的尾部位置。初始編碼按作業(yè)在模板計劃中的開始時間升序排列，并將各作業(yè)的裝配模式編號列入模式列表。為了充分利用雙鏈編碼的信息承載能力及其鄰域構(gòu)造靈活性，TS1中的鄰域生成方式包含兩部分：①從當(dāng)前編碼列表的B類作業(yè)中隨機選取兩個不存在優(yōu)先級關(guān)系的作業(yè)進行位置互換，相應(yīng)裝配模式也隨之互換；②從當(dāng)前編碼列表中隨機選取一個B類作業(yè)，對其裝配模式進行變異操作，即作業(yè)以一定概率重新選擇裝配模式并替換當(dāng)前模式，作業(yè)j對模式mj的選擇概率為Prjmj，

(24)

圖4b和圖4c分別給出單項互換、模式變異操作示例。禁忌對象為迭代過程中使目標函數(shù)最優(yōu)的編碼列表所對應(yīng)的單項互換或模式變異操作，禁忌次數(shù)在上限tabumax和下限tabumin間隨機生成，設(shè)置TS1的終止迭代次數(shù)為iter1。串行調(diào)度解碼算法步驟如下：

步驟1獲取當(dāng)前編碼的作業(yè)列表{j1,j2,…,j|J|}和模式列表{mj1,mj2,…,mj|J|}，令e←1，B1類作業(yè)集合ΩB1←?。

步驟2若作業(yè)je為A類作業(yè)，直接安排其作業(yè)開始時間和裝配模式，否則轉(zhuǎn)步驟3。

步驟5若?t∈[Tje,Tje+pjemje]，?k∈K，rjemjek≤Rk恒成立，則令sje←Tje并轉(zhuǎn)步驟7，否則轉(zhuǎn)步驟6。

步驟6令Tje←Tje+1，轉(zhuǎn)步驟5。

步驟7若sje-pT>Tq+1，令ΩB1←ΩB1∪je并轉(zhuǎn)步驟8，否則直接轉(zhuǎn)步驟8。

步驟8若e<|J|，令e←e+1，轉(zhuǎn)步驟2，否則輸出第1階段固定性決策和ΩB1。

2.1.2 TS2:搜索預(yù)測決策

算法下層的TS2采用與TS1相同的編碼方式搜索預(yù)測決策，其編碼列表由B1和C類作業(yè)構(gòu)成，圖4d給出示例。TS2的編碼初始化、鄰域生成方式、禁忌對象和串行調(diào)度解碼等操作與TS1模塊類似，但需注意：在此階段的禁忌搜索尋優(yōu)過程中，對B1和C類作業(yè)的解碼結(jié)果均補充自同一個固定性決策；在進行串行調(diào)度解碼過程中，對于每個待解碼作業(yè)的物料，需將其待預(yù)測數(shù)據(jù)輸入物料交貨期預(yù)測模型以獲取其物料交貨期的預(yù)測值，確保待解碼作業(yè)的開始時間不早于其物料預(yù)計配送完成時間；對搜索到的每一個編碼個體，在獲得其解碼結(jié)果后，需計算目標函數(shù)以評價TS1中固定性決策的優(yōu)劣。設(shè)置TS2的終止迭代次數(shù)為iter2。

2.2 基于松弛時間的反應(yīng)機制

在執(zhí)行每個周期的固定性決策過程中，當(dāng)作業(yè)受到擾動而被延期執(zhí)行時，新的計劃會被打亂，因此需設(shè)計一套與周期性調(diào)度框架相匹配的反應(yīng)機制加以應(yīng)對?；诖?，本文設(shè)計了基于松弛時間的反應(yīng)機制，其核心思想如圖5所示。

首先將當(dāng)前周期計劃中作業(yè)j的松弛時間stj定義為作業(yè)j在不影響后續(xù)作業(yè)正常執(zhí)行且不破壞決策周期約束情況下的最大可推遲時間。當(dāng)作業(yè)j因物料缺失、損壞、不符合裝配要求等突發(fā)擾動而延期執(zhí)行時，可根據(jù)其預(yù)計延期時間dtj執(zhí)行如下反應(yīng)策略：①若dtj≤stj，將作業(yè)開始時間延后dtj個單位，并維持原有裝配模式；②若dtj>stj且sj+dtj≤Tq+1，則令sj更新為sj+dtj，并按照模式切換成本升序順序逐個安排作業(yè)裝配模式，直至找到可行切換方案(即既滿足資源約束又不影響后續(xù)作業(yè)正常執(zhí)行的模式切換操作)為止，若遍歷所有待切換模式仍無法找到可行切換方案，則直接為作業(yè)j安排最小執(zhí)行工期所對應(yīng)的裝配模式，并通過右移策略即將后續(xù)作業(yè)的開始時間依次順延，無法在當(dāng)前周期開始的作業(yè)將被納入下一周期的B類作業(yè)集合；③若sj+dtj>Tq+1，則直接將作業(yè)j及其直接和間接緊后作業(yè)視為下一周期的B類作業(yè)，其他作業(yè)按計劃正常執(zhí)行。這樣既能確保被干擾作業(yè)能夠盡快開始作業(yè)，又能充分利用當(dāng)前周期計劃中作業(yè)間的松弛時間和空閑資源，防止重調(diào)度過于頻繁，使飛機裝配項目調(diào)度總成本增加。

3 實例應(yīng)用與分析

3.1 實驗平臺

為驗證所提決策框架的有效性，以某型號客機前機身、后機身和機身尾翼裝配工位的部分裝配流程和物料交貨歷史數(shù)據(jù)構(gòu)建實驗算例。裝配流程所包含的裝配作業(yè)數(shù)量分別為23、32、42項，資源包括裝配工人、關(guān)鍵裝配設(shè)備、能源供應(yīng)設(shè)備、線邊存儲空間4類，資源上限數(shù)量分別為[12,7,8,12]，每項作業(yè)存在3種裝配模式。為了構(gòu)建上述裝配流程的模板計劃算例，通過隨機方式生成作業(yè)列表，并為每項作業(yè)隨機選取一種裝配模式，利用串行調(diào)度解碼作業(yè)列表。每項作業(yè)的單位時間延期成本和模式切換成本分別在區(qū)間[0,5]和[0,8]之間隨機生成，將構(gòu)建的算例分別記為E23、E32、E42。物料交貨期預(yù)測模型和對比算法均通過Python 3.6進行編程，測試計算機配置為Inter i7-4790U處理器，3.6 GHz，8 G內(nèi)存，CPLEX軟件版本號為12.6.3。

3.2 物料交貨期預(yù)測模型效果驗證

(25)

(26)

實驗結(jié)果如表2所示，不同算例下XGBoost算法的預(yù)測準確率均值達到98.61%、97.24%、97.84%，不僅優(yōu)于SVR和FCM-BPN算法，還將預(yù)測值與實際值間的平均偏差控制在3%以內(nèi)，表明XGBoost算法在處理物料交貨相關(guān)數(shù)據(jù)方面具有更高的預(yù)測準確性。從絕對誤差的根均方差指標方面看，相比其他算法，XGBoost算法的預(yù)測誤差波動程度更低，表明其具有更優(yōu)的魯棒性。此外，不同算例下XGBoost算法的單次預(yù)測平均耗時也更低，表明其預(yù)測響應(yīng)時間優(yōu)于其他方法。因此，本文所提方法能較好地應(yīng)用于物料交貨期預(yù)測，為調(diào)度決策提供可靠的依據(jù)。

表2 預(yù)測算法對比結(jié)果

3.3 滾動決策框架效果驗證

本文為E23、E32、E42三個算例各生成10組實驗，每組實驗的隨機延期干擾次數(shù)設(shè)為8，延期干擾時間在區(qū)間[5,10]中隨機取值。對于每組實驗，采用雙層循環(huán)迭代的禁忌搜索(Double-layer-loop-iterative Tabu Search，DTS)框架進行連續(xù)5個周期的滾動決策，同時在執(zhí)行每個周期的新計劃階段，采用基于松弛時間的反應(yīng)機制(Slack Time based Reaction, STR)來應(yīng)對干擾。為了驗證本文滾動決策框架的適用性以及雙層循環(huán)迭代搜索算法的有效性，每組實驗在相同干擾環(huán)境下，進行如下對比方法實驗：

(1)CPLEX：基于后驗信息(即在提前知曉所有物料的實際交貨時間和延期干擾信息的條件下)，此時可視所有作業(yè)為B類作業(yè)，使用CPLEX軟件求解本文數(shù)學(xué)模型。

(2)CPLEX-STR：采用非滾動決策方式，即在決策初期利用所有作業(yè)的物料交貨信息(包括決策初期獲得的作業(yè)物料實際到達時間和各個物料交貨期預(yù)測模型的輸入數(shù)據(jù))，以本文目標函數(shù)為優(yōu)化目標，通過本文的物料交貨期預(yù)測模型和CPLEX軟件預(yù)先求得新的計劃，在執(zhí)行新計劃過程中采用基于松弛時間的反應(yīng)機制來應(yīng)對延期擾動。

(3)GA-STR：借鑒并改編文獻[9]中的前攝—反應(yīng)決策框架，在決策初期利用所有作業(yè)的物料交貨信息，以前攝計劃的項目工期(即質(zhì)量魯棒性代理指標)與文獻[9]采用的松弛時間代理指標之和為優(yōu)化目標，通過本文的物料交貨期預(yù)測模型和遺傳算法預(yù)先求得新的計劃。在執(zhí)行新計劃過程中采用基于松弛時間的反應(yīng)機制來應(yīng)對延期擾動。其中，遺傳算法的染色體編碼方式、種群初始化、選擇、交叉、變異等操作均借鑒文獻[6]中的方法。

上述各方法應(yīng)對隨機擾動的評價指標為裝配項目實際執(zhí)行后產(chǎn)生的反應(yīng)調(diào)度總成本(記為Z)即所有作業(yè)實際開始時間與模板計劃開始時間的偏差總成本與所有作業(yè)的裝配模式切換總成本之和。表3～表5分別給出了E23、E32、E42三個算例的實驗結(jié)果。其中：G1為本文方法(DTS)與CPLEX方法所得Z的差值百分比，G2為其他對比方法與DTS方法所得Z的差值百分比。從表中可以看出，不同算例規(guī)模下，DTS與CPLEX方法所得Z的差值百分比G1的均值分別為7.58%、6.37%、6.20%，其原因為：相比于DTS，CPLEX方法利用了后驗信息進行精確求解，但在實際決策中無法提前知曉這些后驗信息，因此CPLEX方法所得解是無法實現(xiàn)的理想解。這一結(jié)果對比不僅體現(xiàn)了飛機實際裝配過程受物料供應(yīng)不確定性的影響較大，也說明了裝配項目推進過程中不確定性信息的動態(tài)變化特點使本文問題的優(yōu)化求解更加復(fù)雜。不同算例規(guī)模下，CPLEX-STR方法與DTS方法所得Z的差值百分比G2的均值分別為4.44%、5.80%、6.24%，可見本文的滾動決策方式相比非滾動決策方式具有一定優(yōu)勢，且其優(yōu)勢隨算例規(guī)模的增大而愈加明顯，其主要原因為：相比于DTS方法在各個滾動周期借助最新獲得的預(yù)測信息主動改善原有模板計劃，CPLEX-STR方法僅利用了決策初期的信息來更新原有計劃，其在后續(xù)執(zhí)行過程中仍采取被動應(yīng)對干擾策略，導(dǎo)致其反應(yīng)調(diào)度總成本較高。在不同算例規(guī)模下，GA-STR方法與DTS方法所得Z的差值百分比G2的均值分別為4.51%、5.45%、5.51%，表明本文的滾動決策框架相比于現(xiàn)有的前攝—反應(yīng)決策框架，具有更優(yōu)的調(diào)度效果。具體來說，前攝—反應(yīng)決策框架雖然在決策初期為各作業(yè)安排了一定量的時間緩沖，使生成的前攝計劃具備較強的魯棒性，但缺乏對不確定性信息不斷更新的反饋措施，易導(dǎo)致作業(yè)間的松弛時間不足或過大的情況，使得其調(diào)度總成本較高，而DTS方法能充分利用不斷更新的不確定性信息獲得較優(yōu)的決策結(jié)果。

表3 E23的實驗結(jié)果

表4 E32的實驗結(jié)果

續(xù)表4

表5 E42的實驗結(jié)果

3.4 反應(yīng)機制效果驗證

為了進一步驗證STR在應(yīng)對突發(fā)擾動方面的優(yōu)勢，以3.3節(jié)中E42的10組實驗為基礎(chǔ)，在相同擾動環(huán)境下，補充如下對比實驗：

基于雙層循環(huán)迭代禁忌搜索的右移算法(Double-layer-loop-iterative Tabu-search based Right-shift, DTR)：采用與DTS方法相同的滾動決策方式，但在執(zhí)行新計劃過程中采用右移算法(Right Shift，RS)來修復(fù)延期擾動對新計劃產(chǎn)生的影響。其中，右移算法作為實際生產(chǎn)中常用的修復(fù)規(guī)則，將發(fā)生物料延期擾動的作業(yè)推遲dtj，同時后續(xù)作業(yè)按原有執(zhí)行順序依次順延。

表6中Zd表示所有作業(yè)實際開始時間與模板計劃開始時間的偏差總成本，Zs表示所有作業(yè)的裝配模式切換總成本。從表中可以發(fā)現(xiàn)，在同樣使用滾動決策框架的情況下，STR能更有效地降低因物料突發(fā)延期擾動而產(chǎn)生的反應(yīng)調(diào)度成本。值得注意的是，在Zd指標上，以STR作為反應(yīng)規(guī)則的DTS方法優(yōu)于DTR方法，但在Zs指標上，DTR方法反而具有一定優(yōu)勢。上述情況的主要原因為：相比于RS，STR不僅利用了周期計劃中作業(yè)間的松弛時間，還利用了不同作業(yè)裝配模式下潛在的空閑資源，雖然會產(chǎn)生更多的模式切換成本，但能使周期計劃內(nèi)的作業(yè)盡快開始，防止部分作業(yè)被延至下一決策周期進行重新，確保實際執(zhí)行計劃與原有模板計劃的偏差不至于過大。

表6 STR與RS的算法性能對比

4 結(jié)束語

本文分析了飛機實際裝配過程中物料交貨期與相關(guān)影響因素間的映射關(guān)系，以物料的歷史交貨數(shù)據(jù)為基礎(chǔ)，構(gòu)建了基于XGBoost算法的物料交貨期預(yù)測模型。

在預(yù)測模型基礎(chǔ)上，研究了物料供應(yīng)不確定性在飛機裝配計劃執(zhí)行過程中的表現(xiàn)形式，構(gòu)建了基于事件與周期混合驅(qū)動策略的滾動決策框架，在各滾動決策時刻建立了基于兩階段近似優(yōu)化的周期性調(diào)度模型，并設(shè)計了雙層循環(huán)迭代搜索算法進行求解。針對滾動周期內(nèi)的物料突發(fā)延期擾動，設(shè)計了基于松弛時間的反應(yīng)機制進行計劃修復(fù)。

實驗結(jié)果表明，基于XGBoost算法的物料交貨期預(yù)測模型可獲得較優(yōu)的預(yù)測效果，能為調(diào)度決策提供可靠的依據(jù)；雙層循環(huán)迭代搜索算法能有效應(yīng)對物料供應(yīng)不確定性在飛機裝配過程中的變化，同時可獲得較優(yōu)的決策結(jié)果，驗證了該算法的適用性和有效性；基于松弛時間的反應(yīng)機制能充分利用作業(yè)間的松弛時間和潛在的空閑資源，從而降低反應(yīng)調(diào)度總成本，驗證了該方法的優(yōu)勢。

未來可進一步研究供應(yīng)商實時狀態(tài)對飛機采購計劃、物料配送調(diào)度計劃的影響情況。