考慮物料供應(yīng)干擾的飛機(jī)移動生產(chǎn)線動態(tài)調(diào)度

盧斌，陸志強(qiáng)

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

飛機(jī)移動生產(chǎn)線制造模式作為一項長期精益實踐的成果，具有生產(chǎn)效率高、生產(chǎn)連續(xù)穩(wěn)定、信息化程度高等特點，受到各大航空制造企業(yè)的青睞。飛機(jī)移動生產(chǎn)線由多個前后銜接的“虛擬大工位”構(gòu)成，飛機(jī)主體在每個大工位上以相同速度移動，并完成一定數(shù)量的裝配作業(yè)。國內(nèi)外學(xué)者對飛機(jī)移動生產(chǎn)線調(diào)度相關(guān)問題進(jìn)行了較為充分的研究［1-4］，其研究大多致力于模板裝配計劃的制定，在決策裝配作業(yè)的開始時間時均假定物料能準(zhǔn)時供應(yīng)。然而在實際裝配環(huán)境中，飛機(jī)裝配所需的零部件種類復(fù)雜且數(shù)量巨大［5］，各供應(yīng)商的產(chǎn)能、服務(wù)水平、運(yùn)輸條件等因素易受外部環(huán)境或突發(fā)事件影響，物料供應(yīng)的準(zhǔn)時性難以保證，裝配作業(yè)推遲執(zhí)行的情況時有發(fā)生。物料供應(yīng)延期不僅影響到裝配作業(yè)本身，還會影響到后續(xù)其他作業(yè)的調(diào)度執(zhí)行，導(dǎo)致模板裝配計劃不可行，使得生產(chǎn)管理人員不得不對模板計劃進(jìn)行響應(yīng)調(diào)整，從而增加了裝配現(xiàn)場資源調(diào)配負(fù)擔(dān)。因此，在生產(chǎn)線的實時運(yùn)作過程中，提供一種能夠有效應(yīng)對物料供應(yīng)延期干擾的反應(yīng)調(diào)度方法具有重要的實際意義?；谠搶嶋H需求，本文對物料供應(yīng)干擾環(huán)境下的飛機(jī)移動生產(chǎn)線調(diào)度問題進(jìn)行了研究。

物料供應(yīng)干擾環(huán)境下的飛機(jī)移動生產(chǎn)線調(diào)度問題本質(zhì)上是一類不確定環(huán)境下的項目調(diào)度問題，現(xiàn)有文獻(xiàn)針對此類問題進(jìn)行了較為充分的研究。部分學(xué)者從前攝調(diào)度方法入手，考慮了作業(yè)時長的不確定性，通過插入緩沖時間來提高模板調(diào)度計劃的穩(wěn)定性，設(shè)計了基于抽樣仿真評價的啟發(fā)式和元啟發(fā)式算法來優(yōu)化分配整個調(diào)度中的緩沖區(qū)［6-9］。Lambrechts［10］和Ma［11］等考慮了資源可用性的不確定性，設(shè)計了前攝-反應(yīng)調(diào)度框架，前攝階段以調(diào)度計劃解魯棒性為優(yōu)化指標(biāo)生成模板調(diào)度計劃，執(zhí)行階段采用反應(yīng)式調(diào)度策略，以最小化與模板調(diào)度計劃的偏差為目標(biāo)函數(shù)生成新調(diào)度計劃。van de Vonder等［12］針對作業(yè)突發(fā)中斷問題，提出了魯棒串行和并行調(diào)度機(jī)制，結(jié)合優(yōu)先級規(guī)則和啟發(fā)式算法，設(shè)計了魯棒反應(yīng)式調(diào)度程序。Chakrabortty等［13］分別考慮資源中斷干擾場景，建立了混合整數(shù)規(guī)劃模型，提出了多種啟發(fā)式算法來求解模型。Davari和 Demeulemeester［14］針對作業(yè)時長的不確定性，綜合考慮前攝調(diào)度和反應(yīng)調(diào)度所產(chǎn)生的成本，提出了基于多階段動態(tài)規(guī)劃的數(shù)學(xué)模型來解決最優(yōu)化問題。Chand等［15］針對資源干擾環(huán)境的項目調(diào)度問題，建立了多目標(biāo)規(guī)劃模型，并設(shè)計了基于遺傳規(guī)劃的改進(jìn)優(yōu)先規(guī)則啟發(fā)式程序進(jìn)行求解。針對物料供給延期干擾，陸志強(qiáng)等［16］建立了以最小化調(diào)度計劃變動成本和資源額外投入成本加權(quán)和為目標(biāo)函數(shù)的調(diào)度模型，設(shè)計了基于支持向量數(shù)據(jù)描述的動態(tài)調(diào)度算法進(jìn)行求解。

從上述文獻(xiàn)來看，考慮的不確定性因素主要集中在作業(yè)時長、作業(yè)所需資源可用性等方面，對考慮作業(yè)所需物料供應(yīng)不確定性的項目調(diào)度問題研究較為匱乏。文獻(xiàn)［16］雖然在飛機(jī)移動生產(chǎn)線背景下考慮了物料供應(yīng)不確定環(huán)境，但在問題描述中僅考慮后續(xù)作業(yè)的物料預(yù)計可送達(dá)時間，簡化了對物料供應(yīng)不確定性的處理。實際上，隨著飛機(jī)裝配進(jìn)度的推進(jìn)及對物料供應(yīng)過程的實時監(jiān)測，生產(chǎn)管理人員除了能準(zhǔn)確獲知某些作業(yè)的物料延期到達(dá)時間以外，還能對后續(xù)作業(yè)的物料到達(dá)時間概率分布進(jìn)行預(yù)測。在物料延期干擾發(fā)生時，生產(chǎn)管理人員希望利用最新掌握的物料供應(yīng)信息，兼顧調(diào)度決策的反應(yīng)性和預(yù)見性，從而最大程度地降低物料供應(yīng)干擾環(huán)境對飛機(jī)移動生產(chǎn)線正常運(yùn)作的影響。針對此需求，本文以物料供應(yīng)干擾環(huán)境下的飛機(jī)移動生產(chǎn)線裝配作業(yè)調(diào)度問題為研究對象，借鑒文獻(xiàn)［17］中針對多階段隨機(jī)優(yōu)化過程的、基于二階段近似優(yōu)化模型的決策框架，提出了物料供應(yīng)干擾環(huán)境下的動態(tài)調(diào)度框架，建立了滾動決策點的二階段近似優(yōu)化模型。針對模型的決策邏輯，設(shè)計了以兩階段禁忌搜索算法為框架的啟發(fā)式算法進(jìn)行求解。通過數(shù)值實驗，驗證了所提動態(tài)調(diào)度方法的有效性。

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

1.1 問題描述與基本假設(shè)

物料供應(yīng)干擾環(huán)境下的飛機(jī)移動生產(chǎn)線裝配作業(yè)調(diào)度問題，是在物料供應(yīng)延期導(dǎo)致裝配作業(yè)無法按原始計劃執(zhí)行的情況下，通過反應(yīng)調(diào)度優(yōu)化決策未開始作業(yè)的開始時間，以減少實際執(zhí)行計劃與模板裝配計劃的偏差和裝配工期，從而達(dá)到最小化反應(yīng)調(diào)度總成本的目的。針對飛機(jī)移動生產(chǎn)線裝配工位特點，給出如下基本假設(shè)：①裝配工位的模板裝配計劃已定；②將裝配工位調(diào)度問題抽象為資源受限項目調(diào)度問題，即裝配作業(yè)的調(diào)度應(yīng)同時滿足作業(yè)優(yōu)先級、可用資源上限等基本約束；③如圖1所示，在飛機(jī)移動生產(chǎn)線各個裝配工位中考慮多類共享的可更新資源，包括裝配工人、關(guān)鍵裝配設(shè)備、能源供應(yīng)設(shè)備、線邊存儲空間等；④裝配作業(yè)所需物料動態(tài)到達(dá)且為齊套準(zhǔn)時化配送；⑤時間軸作離散化處理。

表1匯總了參數(shù)及決策變量，其中作業(yè)編號0與n＋1為虛作業(yè)，其執(zhí)行工期與資源需求量為0。

圖1 飛機(jī)移動生產(chǎn)線裝配工位布局圖Fig.1 Assembly station layout of aircraft mobile production line

表1 參數(shù)與決策變量Table 1 Parameters and decision variables

1.2 物料供應(yīng)干擾環(huán)境下的動態(tài)調(diào)度框架

本文所考慮的物料供應(yīng)干擾具體體現(xiàn)為2個方面：①當(dāng)前某一作業(yè)的物料供應(yīng)發(fā)生延期且延期到達(dá)時間已知，此類干擾直接導(dǎo)致作業(yè)推遲執(zhí)行；②部分未開始作業(yè)的物料到達(dá)時間服從某概率分布，換言之，這些作業(yè)的物料到達(dá)情況具備多個可能的場景，每個場景均可能發(fā)生物料延期干擾，這些干擾雖尚未發(fā)生，但隱含在后續(xù)計劃執(zhí)行過程中。由此，本文將受干擾作業(yè)的物料延期到達(dá)時間歸為確定性信息，將部分未開始作業(yè)的物料到達(dá)時間概率分布定義為不確定性信息。

由于部分作業(yè)的物料供應(yīng)方式為JIT供貨方式，其物料供應(yīng)過程易受外部環(huán)境影響，此類作業(yè)的物料到達(dá)時間具有不確定性。對于此類作業(yè)，在其物料開始配送之前，管理人員只能通過預(yù)測獲得其物料到達(dá)時間的概率分布，且概率分布的方差（即預(yù)測準(zhǔn)確度）會隨著預(yù)測時間的臨近越來越小。此外，當(dāng)干擾事件發(fā)生時，即作業(yè)的物料到達(dá)時間晚于計劃配送時間時，觸發(fā)反應(yīng)調(diào)度動作，此時延期物料的到達(dá)時間變?yōu)榇_定性信息，同時后續(xù)作業(yè)的物料到達(dá)時間概率分布得到更新。

在反應(yīng)調(diào)度動作層面，本文所提出的動態(tài)調(diào)度方法是由干擾事件驅(qū)動的，干擾事件發(fā)生的時間點為滾動決策點。與常規(guī)重調(diào)度方法不同的是，本文將后續(xù)作業(yè)的調(diào)度決策分為兩階段進(jìn)行：將第q次干擾發(fā)生的時刻記為Tq，將Tq后具有完全確定性信息的時間段記為固定決策階段，將Tq后首次出現(xiàn)不確定性信息的時間點記為Tq＋1，則Tq到Tq＋1之間的時間為固定決策階段，該階段的決策模型為確定性模型，其決策用以替代該階段的原始計劃；而Tq＋1后的時間為預(yù)測決策階段，該階段的決策模型為不確定性模型，通過構(gòu)建場景的方法建模求解，其決策無需實際執(zhí)行，僅用于評價固定決策階段的決策。

依據(jù)上述分析，在Tq時刻，將作業(yè)劃分為3類集合，如圖2所示。圖中：虛線框為物料配送作業(yè)，實線框為裝配作業(yè)。3類作業(yè)的決策屬性描述如下：

圖2 Tq時刻的甘特圖Fig.2 Gantt chart at Tq

1）JF類。物料配送作業(yè)已經(jīng)完成或已經(jīng)開始但未完成的作業(yè)（作業(yè)1、2），按原始計劃執(zhí)行。

2）JD類。物料計劃配送時間位于固定決策階段內(nèi)的作業(yè)，包括物料延期到達(dá)的作業(yè)（作業(yè)3），以及物料到達(dá)時間已確定的作業(yè)（作業(yè)4、5、6），將進(jìn)行固定決策。

3）JP類。物料計劃配送時間在Tq＋1（作業(yè)7的物料到達(dá)時間不確定）后的作業(yè)（作業(yè)7、8、9、10、11、12、13），將進(jìn)行不同場景下的預(yù)測決策。

為了明確描述相鄰滾動決策點間的決策更新情況，以圖2中Tq時刻的甘特圖為例進(jìn)行說明。此時JD類作業(yè)將進(jìn)行固定決策，決策結(jié)果將替代原始計劃并實際執(zhí)行；當(dāng)時間推進(jìn)至Tq＋1，得到圖3所示的甘特圖，其中作業(yè)3、4、5、6的開始時間為Tq時刻進(jìn)行固定決策的結(jié)果，對于作業(yè)7、8、9、10、11、12、13而言，由于物料到達(dá)信息的更新，保留了其在Tq＋1進(jìn)行決策更新的權(quán)利。在Tq＋1，作業(yè)1、2、3、4、5、6更新為JF類作業(yè)，作業(yè)7、8、9、10更新為JD類作業(yè)，作業(yè)11、12、13更新為JP類作業(yè)。

結(jié)合信息和操作層面的分析，以及對不同作業(yè)類型決策屬性的描述，給出物料供應(yīng)干擾環(huán)境下的動態(tài)調(diào)度框架，如圖4所示。

圖3 Tq＋1時刻的甘特圖Fig.3 Gantt chart at Tq＋1

1.3 二階段近似優(yōu)化模型

根據(jù)1.2節(jié)的兩階段決策邏輯，本節(jié)建立二階段近似優(yōu)化模型。由于飛機(jī)裝配復(fù)雜度高，集成在生產(chǎn)線上的裝配資源種類較多，模板裝配計劃耦合了大量的裝配資源配置計劃。一旦出現(xiàn)作業(yè)因物料供應(yīng)延期而推遲執(zhí)行的干擾，模板裝配計劃將不再可行，實際執(zhí)行的調(diào)度結(jié)果會產(chǎn)生不可避免的偏差，將加重裝配資源調(diào)配負(fù)擔(dān)，同時裝配工位實際工期也將被迫延長。因此，本文的目標(biāo)函數(shù)同時考慮了實際執(zhí)行計劃與模板裝配計劃的偏差和裝配工期2類指標(biāo)。根據(jù)企業(yè)實際需求，可為2類優(yōu)化指標(biāo)設(shè)定單位時間成本權(quán)重ω1和ω2，并采用加權(quán)求和的標(biāo)量化方法將2個不同的優(yōu)化指標(biāo)轉(zhuǎn)化為單目標(biāo)函數(shù)。由此，本文以最小化與模板裝配計劃的偏差及工期的加權(quán)和作為調(diào)度決策（記為S）的綜合成本衡量指標(biāo)f（S），可寫為

圖4 動態(tài)調(diào)度框架Fig.4 Framework of dynamic scheduling

設(shè)Aj表示作業(yè)j的物料到達(dá)時間。對于物料到達(dá)時間已知的作業(yè)，直接獲取其物料到達(dá)時間確定值；對于物料到達(dá)時間不確定的作業(yè)，采用蒙特卡羅抽樣法，從已知概率分布中隨機(jī)抽樣，獲取其物料到達(dá)時間樣本值。對每個概率分布進(jìn)行單次抽樣后，含有n個作業(yè)物料到達(dá)時間的序列Y可表示為

Y=（A1，A2，…，An）

式（2）可通過不同場景下的預(yù)測決策，評估固定決策的自身效能及應(yīng)對不同場景的反應(yīng)能力，達(dá)到兼顧調(diào)度決策反應(yīng)性和預(yù)見性的目的。為了使模型表達(dá)更為簡潔，決策變量統(tǒng)一用場景進(jìn)行表述。補(bǔ)充參數(shù)并修正決策變量，修正后的參數(shù)和決策變量如表2所示。

表2 修正的參數(shù)與決策變量Table 2 Modified parameters and decision variables

修正參數(shù)與決策變量后，式（2）可改寫為目標(biāo)函數(shù)式（3），目標(biāo)函數(shù)受式（4）～式（12）的約束。

式（4）表示任意場景下任意JF類作業(yè)的決策一致；式（5）表示對JD類作業(yè)的固定決策在任意場景下保持一致；式（6）表示決策變量sj，θ與xjt，θ之間的關(guān)系；式（7）表示任意場景下任意作業(yè)均應(yīng)滿足作業(yè)優(yōu)先級約束；式（8）表示任意場景下任意時刻所有執(zhí)行的作業(yè)對任意種類的資源需求量均不大于該資源供給上限；式（9）表示任意場景下任意作業(yè)一旦開始不能中斷；式（10）表示任意場景下任意作業(yè)的物料開始配送時間不應(yīng)早于物料到達(dá)時間；式（11）表示任意場景下任意JD和JP類作業(yè)的物料開始配送時間不應(yīng)早于干擾發(fā)生時刻；式（12）表示決策變量xjt，θ的可行域。

2 算法設(shè)計

依據(jù)模型的決策邏輯，本文設(shè)計了以兩階段禁忌搜索算法為框架的啟發(fā)式算法（Two-stage Tabu Search Based Heuristic，TTSBH），其中解碼算法采用了基于局部前瞻搜索的串行調(diào)度機(jī)制。算法設(shè)計思路如下：TTSBH算法分2層嵌套運(yùn)用禁忌搜索算法，依次搜索JD類作業(yè)的固定決策和不同場景下JP類作業(yè)的預(yù)測決策。具體而言，對于搜索到的每一個固定決策結(jié)果（即JD類作業(yè)的調(diào)度結(jié)果），進(jìn)一步地，在該固定決策結(jié)果基礎(chǔ)上，重復(fù)搜索不同場景θ（θ∈Θ）下JP類作業(yè)的預(yù)測決策結(jié)果，通過計算目標(biāo)函數(shù)值，來反饋評估該固定決策結(jié)果的優(yōu)劣。TTSBH 算法采用作業(yè)列表進(jìn)行編碼，編碼順序代表作業(yè)的調(diào)度順序。依據(jù)3類作業(yè)的決策屬性，對編碼進(jìn)行拆分，如圖5所示。其中，對于JF類作業(yè)的固定編碼按照實際執(zhí)行順序升序排列，每經(jīng)過一次滾動決策都將進(jìn)行更新；對應(yīng)JD類作業(yè)的固定決策編碼，其初始列表（記為L1）按模板裝配計劃開始時間升序排列；對應(yīng)JP類作業(yè)的預(yù)測決策編碼，其初始列表（記為L2）按模板裝配計劃中的開始時間升序排列。TTSBH算法框架及流程如圖6所示。

圖5 作業(yè)列表編碼拆分示意圖Fig.5 Schematic diagram of job list coding splitting

圖6 TTSBH算法流程Fig.6 Flowchart of TTSBH algorithm

2.1 第一階段禁忌搜索TS1

2.2 第二階段禁忌搜索TS2

第二階段禁忌搜索TS2為JP類作業(yè)搜索不同場景下的預(yù)測決策。禁忌搜索的鄰域生成方式、禁忌對象設(shè)置與TS1相同，禁忌表長度為TL-2，迭代次數(shù)為Iter-2。在獲取TS1中待評估作業(yè)列表基礎(chǔ)上，對搜索到的每一個作業(yè)列表，采用基于局部前瞻搜索的串行調(diào)度機(jī)制進(jìn)行解碼，得到當(dāng)前場景下的調(diào)度結(jié)果。需要注意，在各個場景下重復(fù)進(jìn)行禁忌搜索尋優(yōu)過程中，對JP類作業(yè)的決策結(jié)果均補(bǔ)充自同一個固定決策。

2.3 基于局部前瞻搜索的串行調(diào)度機(jī)制

結(jié)合目標(biāo)函數(shù)中所考慮的優(yōu)化指標(biāo)，本文設(shè)計了基于局部前瞻搜索的串行調(diào)度機(jī)制對作業(yè)列表進(jìn)行解碼，算法具體步驟如下：

步驟1獲取場景θ所對應(yīng)的作業(yè)物料到達(dá)時間序列（A1，θ，A2，θ，…，An，θ），合并2個決策階段的作業(yè)列表，得到作業(yè)數(shù)量為I的調(diào)度序列｛j1，j2，…，jI｝，令i=1。

步驟10若i

為了更好地說明基于局部前瞻搜索的串行調(diào)度機(jī)制，以圖5中作業(yè)列表編碼為例，依次決策作業(yè)3、4、5、6的開始時間，解碼過程如圖7所示。對于作業(yè)3，其待決策值僅為5，直接決策作業(yè)3的開始時間為5；對于作業(yè)4，其待決策值集合為｛7，8，9，10｝，對每個待決策值進(jìn)行局部前瞻搜索，計算其所生成局部調(diào)度計劃的適應(yīng)度，將其中最小適應(yīng)度所對應(yīng)的待決策值9作為作業(yè)4的最佳開始時間；作業(yè)5、6的解碼方式與作業(yè)4相同，不再贅述。依次解碼作業(yè)列表，直至確定完全部作業(yè)的開始時間。

圖7 解碼過程示例Fig.7 An example of decoding process

3 數(shù)值實驗

以文獻(xiàn)［16］中模板裝配計劃實例為參考，結(jié)合所研究問題的特點，進(jìn)行算例擴(kuò)充，構(gòu)造作業(yè)數(shù)量為20、30、60、90、120等5類規(guī)模的數(shù)據(jù)，分別生成10組算例。取ω1=0.5，ω2=0.5。設(shè)置物料配送提前期為10。假設(shè)受干擾作業(yè)占作業(yè)數(shù)量的10%。其余作業(yè)的物料到達(dá)時間均已知，且與物料計劃配送時間的偏差值在［10，20］內(nèi)隨機(jī)選取。受干擾作業(yè)的物料實際延期時間在區(qū)間［20，30］內(nèi)隨機(jī)選取。將進(jìn)度時間距離作業(yè)模板開始時間的差值記為λ，在λ所在的不同范圍（λ>90，50<λ≤90，10<λ≤50），其預(yù)估的物料到達(dá)時間與實際到達(dá)時間的偏差分別服從正態(tài)分布N（0，2），N（0，1），N（0，0.5）。在每個滾動決策點設(shè)置場景池，大小為2 000，TS2從中抽取30個場景作為物料到達(dá)場景集合。實驗通過MATLAB（2014b）平臺進(jìn)行，計算機(jī)配置為Intel i7-4790U處理器，3.6 GHz主頻，8 GB內(nèi)存。獲取后驗精確解使用的CPLEX軟件版本號為12.6.3。以作業(yè)規(guī)模為120的10個算例作為預(yù)實驗對象，確定TTSBH算法所用的參數(shù)：Iter-1為10，TL-1為4，Iter-2為2，TL-2為1。選取其中一個算例的測試結(jié)果，給出TTSBH算法的收斂曲線，如圖8所示。

圖8 TTSBH算法收斂曲線Fig.8 Convergence curve of TTSBH algorithm

3.1 與CPLEX后驗求解結(jié)果對比

為了驗證TTSBH算法的精確性及解碼算法的有效性，本節(jié)利用后驗信息（即所有作業(yè)的物料實際到達(dá)時間提前已知），設(shè)計了如下對比實驗：

1）實驗1。使用CPLEX軟件單次求解數(shù)學(xué)模型。

2）實驗2。采用簡化的動態(tài)調(diào)度框架和TTSBH算法（固定決策階段的作業(yè)為前兩次干擾發(fā)生時刻之間的作業(yè)，后續(xù)作業(yè)利用后驗信息進(jìn)行預(yù)測決策），單次求解數(shù)學(xué)模型。

3）實驗3。設(shè)計類似實驗2，但兩階段禁忌搜索算法中的解碼算法采用傳統(tǒng)的串行調(diào)度機(jī)制（SSGS），該機(jī)制將作業(yè)開始時間安排為最早可開始時間。將該實驗的算法命名為基于串行調(diào)度機(jī)制的兩階段禁忌搜索算法，簡記為TTS-SSGS。

由于CPLEX不適用于求解大規(guī)模算例，表3給出作業(yè)規(guī)模V為20、30、60各10組不同算例的求解結(jié)果，其中Z為目標(biāo)函數(shù)值，t為求解時間，G為其他算法得到的Z值與CPLEX求解結(jié)果的差值百分比，帶“*”的算例編號表示該算例在使用CPLEX求解時僅能獲得3 h內(nèi)所得的最優(yōu)低界值。

通過與CPLEX實驗對比可以發(fā)現(xiàn)，TTSBH算法在各個規(guī)模算例中均能獲得較優(yōu)解，且在部分算例中獲得了精確解。在各個作業(yè)規(guī)模下，與CPLEX求解結(jié)果的G均值分別為1.4%、2.8%和2.8%，證明了TTSBH算法的有效性。隨著作業(yè)規(guī)模增加，CPLEX求解所需時間迅速上升，在作業(yè)規(guī)模為60下，平均時間達(dá)到了105 min，部分算例甚至無法在可接受時間得到理想低界。而TTSBH算法不僅能在較短時間內(nèi)得到優(yōu)質(zhì)解，且求解時間穩(wěn)定，說明TTSBH算法在求解時間上也具有較大優(yōu)勢。TTS-SSGS算法雖然在求解時間方面略優(yōu)于TTSBH算法，但求解結(jié)果在各作業(yè)規(guī)模下的G均值分別達(dá)到4.4%、3.5%和4.8%，其求解質(zhì)量劣于TTSBH算法，表明基于局部前瞻搜索的串行調(diào)度機(jī)制相比于傳統(tǒng)SSGS具有一定優(yōu)勢，解碼效果更優(yōu)。

表3 基于后驗信息的實驗結(jié)果Table 3 Experiment results based on posterior information

3.2 物料供應(yīng)干擾環(huán)境下的對比實驗

為了驗證本文動態(tài)調(diào)度方法的求解效果，本節(jié)設(shè)計了物料供應(yīng)干擾環(huán)境下的對比實驗：

1）實驗4。采用本文的動態(tài)調(diào)度框架和TTSBH算法，滾動求解數(shù)學(xué)模型。

2）實驗5。以各個概率分布的期望值構(gòu)建期望場景，預(yù)測決策階段僅利用期望場景下的預(yù)測決策結(jié)果對固定決策階段決策進(jìn)行評價，滾動求解數(shù)學(xué)模型。

3）實驗6。采用單階段決策方法，即僅進(jìn)行固定決策，并利用TTSBH中的TS1算法和解碼算法滾動求解簡化后的數(shù)學(xué)模型。

4）實驗7。采用典型的右移策略（Right Shift，RS），滾動應(yīng)對執(zhí)行過程中發(fā)生的物料延期干擾。

5）實驗8。采用文獻(xiàn)［18］中的前攝-反應(yīng)決策框架，即在計劃執(zhí)行前預(yù)先考慮已知的物料到達(dá)時間概率分布，在原始模板裝配計劃的基礎(chǔ)上使用該文獻(xiàn)中基于代理目標(biāo)評價的自適應(yīng)遺傳算法建立前攝性計劃，反應(yīng)階段使用右移策略應(yīng)對實際發(fā)生的延期干擾。其中，代理目標(biāo)函數(shù)考慮前攝計劃的工期（即質(zhì)量魯棒性指標(biāo)）和文獻(xiàn)［18］采用的松弛時間代理指標(biāo)2項指標(biāo)，松弛時間為作業(yè)在不影響后續(xù)作業(yè)情況下可推遲執(zhí)行的最大時間，自適應(yīng)遺傳算法的編碼、種群初始化、交叉、變異、選擇等操作均借鑒文獻(xiàn)［4］中的方法，并采用傳統(tǒng)的串行調(diào)度機(jī)制對作業(yè)列表解碼。

采用3.1節(jié)中的CPLEX求解結(jié)果作為對比基準(zhǔn)。由于CPLEX在作業(yè)規(guī)模為60時已出現(xiàn)部分算例無法在可接受時間內(nèi)求解，因此作業(yè)規(guī)模為90和120的算例不再進(jìn)行實驗1的求解。實驗2是采用后驗信息進(jìn)行求解的，由表3可知其與CPLEX所求解足夠接近，因此在更大規(guī)模下采用實驗2的算法結(jié)果作為后驗對比基準(zhǔn)。表4和表5分別給出規(guī)模為20、30、60和規(guī)模為90、120的求解結(jié)果，Z值為滾動求解后的實際執(zhí)行計劃與模板裝配計劃偏差與實際工期的加權(quán)和，GAP1為本文方法的Z值與后驗結(jié)果的差值百分比，GAP2、GAP3、GAP4和GAP5分別為其他方法與本文方法的Z值差值百分比。

通過表4和表5可以發(fā)現(xiàn)，在采用了本文方法的情況下，各個作業(yè)規(guī)模的GAP1均值分別為2.9%、3.5%、3.1%、3.9%和4.5%，且個別算例求解結(jié)果能獲得精確解，可見不同場景下的預(yù)測決策能有效輔助固定決策階段作出更優(yōu)的決策，體現(xiàn)本文方法的后驗優(yōu)化能力。對比實驗4和實驗5，不同作業(yè)規(guī)模下的GAP2均值為0.5%、0.6%、1.3%、2.3%和4.8%，表明僅利用期望信息，雖在小規(guī)模算例中達(dá)到了和本文方法相似的調(diào)度效果，但隨著規(guī)模不斷增加，其調(diào)度效果呈現(xiàn)越來越劣的趨勢，顯示出隨機(jī)場景信息在預(yù)測決策階段的價值。對比實驗4和實驗6，不同規(guī)模下的GAP3均值為0.7%、1.0%、3.0%、13.5%和24.4%，表明隨著算例規(guī)模增大，單階段決策方法的全局優(yōu)化能力越來越差，體現(xiàn)了本文方法中的固定決策在不同場景的預(yù)測決策評估影響下具備了較強(qiáng)的全局優(yōu)化能力，顯示出本文的動態(tài)調(diào)度方法具有兼顧調(diào)度反應(yīng)性和預(yù)見性的優(yōu)勢。對比實驗4和實驗7，不同規(guī)模下的GAP4均值為24.0%、7.1%、8.9%、23.5%和31.3%，顯示出右移策略在應(yīng)對干擾時的被動性，體現(xiàn)了本文方法在應(yīng)對物料延期干擾事件時所具有的明顯優(yōu)勢，也體現(xiàn)了充分利用物料到達(dá)場景信息的重要性。對比實驗4和實驗8，不同作業(yè)規(guī)模下的GAP5均值為3.9%、3.5%、4.0%、10.3%和12.7%，表明本文方法相比于現(xiàn)有的前攝-反應(yīng)方法，具有更優(yōu)的調(diào)度效果。具體而言，前攝-反應(yīng)方法雖然能確保生成的前攝計劃具有較強(qiáng)的魯棒性，但缺乏對不確定性信息更新的反饋，易造成作業(yè)間松弛時間過大或不足的情況，導(dǎo)致調(diào)度效果較差，側(cè)面體現(xiàn)了本文方法能充分利用不斷更新的不確定性信息，進(jìn)而做出更有效的決策。

表4 小規(guī)模算例實驗結(jié)果Table 4 Experiment results of small-scale example

表5 大規(guī)模算例實驗結(jié)果Table 5 Experiment results of lar ge-scale example

3.3 不同干擾程度影響下的方法性能對比

飛機(jī)裝配在不同環(huán)境中會受到不同干擾程度的影響，本節(jié)通過改變干擾發(fā)生次數(shù)（即干擾作業(yè)數(shù)量），對本文方法的優(yōu)化效果進(jìn)行有效性驗證。以作業(yè)規(guī)模為90的10組算例為測試對象，將干擾發(fā)生次數(shù)從0逐漸增大到9，記錄不同方法下求得Z值，結(jié)果如圖9所示?？芍?，本文方法在不同干擾次數(shù)下得到的調(diào)度結(jié)果均優(yōu)于其他方法，且能夠保持接近后驗結(jié)果的求解性能。隨著干擾次數(shù)增加，本文方法與單階段決策方法、RS方法、前攝-反應(yīng)方法的求解效果差距越來越明顯。與期望場景方法對比，當(dāng)干擾次數(shù)小于6時，本文方法的求解優(yōu)勢較小，當(dāng)干擾次數(shù)達(dá)到6以上時，求解優(yōu)勢開始呈現(xiàn)越來越明顯的趨勢。由分析可知，本文方法在不同干擾程度影響下能獲得較優(yōu)的調(diào)度效果，能較大程度降低物料供應(yīng)干擾環(huán)境對飛機(jī)裝配過程的影響。

圖9 不同干擾次數(shù)下的方法性能對比Fig.9 Performance comparison of methods under different interference times

3.4 不同目標(biāo)權(quán)重比下的方法性能對比

上述實驗均取ω1=0.5，ω2=0.5，然而在實際生產(chǎn)調(diào)度中，權(quán)重需根據(jù)企業(yè)實際需求確定。因此，本節(jié)通過改變目標(biāo)函數(shù)中2個子目標(biāo)的權(quán)重比，對本文方法的適應(yīng)性進(jìn)行測試。以作業(yè)規(guī)模為90的10組算例為測試對象，將工期權(quán)重從0逐漸增大到1，記錄不同方法所求得的評價指標(biāo)Z值及2類子目標(biāo)指標(biāo)的均值，結(jié)果如圖10所示?？芍?，隨著工期權(quán)重的增加，不同方法的Z值均逐漸降低。本文方法在不同權(quán)重比下得到的Z值均接近后驗結(jié)果的Z值，且隨著工期權(quán)重增加，越來越逼近后驗結(jié)果，表明動態(tài)調(diào)度方法具有良好的求解質(zhì)量和適應(yīng)性。當(dāng)工期權(quán)重為1時，不同方法求得的結(jié)果相差不大，相比較于其他4種方法，動態(tài)調(diào)度方法沒有明顯優(yōu)勢。在工期權(quán)重從0增大到1的過程中，本文方法求得的結(jié)果均顯著優(yōu)于單階段決策方法、RS方法和前攝-反應(yīng)方法。從柱形圖中可以看出，不同工期權(quán)重下各個方法的工期目標(biāo)值相差不大，但在與模板裝配計劃的偏差值方面，本文方法均能獲得更優(yōu)的求解結(jié)果，表明該方法能較好地兼顧調(diào)度計劃的穩(wěn)定性和調(diào)度質(zhì)量，即本文提出的動態(tài)調(diào)度方法可適用于解決不同權(quán)重下的飛機(jī)裝配反應(yīng)調(diào)度問題。

3.5 應(yīng)用案例

以某型號客機(jī)尾翼部分的裝配工位為例，驗證本文方法在實際應(yīng)用中的可行性。該工位包含23項裝配作業(yè)，其中作業(yè)1和作業(yè)23為虛作業(yè)，資源包括裝配工人、關(guān)鍵裝配設(shè)備、能源供應(yīng)設(shè)備、線邊存儲空間4類，資源上限數(shù)量分別為［12，7，10，12］，物料配送提前期為5。模板裝配計劃如表6所示。作業(yè)5、19、8為受物料供應(yīng)干擾的作業(yè)，其物料實際延期時間分別為28、31、30。在λ所在的不同范圍（λ>75，40<λ≤75，5<λ≤40），對干擾作業(yè)預(yù)估的物料到達(dá)時間與實際到達(dá)時間的偏差分別服從正態(tài)分布N（2，2），N（1，1），N（0，0.5）。

圖10 不同工期權(quán)重下的方法性能對比Fig.10 Performance comparison of methods under different duration weights

表6 尾翼裝配工位模板裝配計劃Table 6 Template assembly plan of tail assembly station

分別利用本文方法和前述對比方法求解該應(yīng)用案例，結(jié)合調(diào)度結(jié)果繪制甘特圖，如圖11～圖16所示。圖中不同方法所求得的Z值（即實際執(zhí)行計劃與模板裝配計劃的偏差和實際工期的加權(quán)和）分別為280.5、284.5、310、307.5、339和309.5，可見本文方法的求解結(jié)果與后驗信息下的求解結(jié)果相差不大，體現(xiàn)了其較強(qiáng)的后驗優(yōu)化能力。對比本文方法與其他方法的調(diào)度結(jié)果可以看出，本文方法具有更優(yōu)的求解效果。具體而言，本文方法和其他方法所求得的實際工期分別為279、279、278、288和288，實際執(zhí)行計劃與模板裝配計劃的偏差分別為290、341、337、390、331，表明本文所提出的動態(tài)調(diào)度方法不僅能獲得較短的工期，還能使實際執(zhí)行計劃與模板裝配計劃之間的變動性更小，兼顧了調(diào)度質(zhì)量和調(diào)度計劃執(zhí)行的穩(wěn)定性。結(jié)合實驗結(jié)果和應(yīng)用案例可知，本文方法相比于現(xiàn)有方法，具有更優(yōu)的求解效果，且在實際應(yīng)用中具備可行性。

圖11 后驗求解調(diào)度結(jié)果（Z=280.5）Fig.11 Scheduling results of posteriori solution（Z=280.5）

圖12 本文方法調(diào)度結(jié)果（Z=284.5）Fig.12 Scheduling results of proposed method（Z=284.5）

圖13 單階段決策方法調(diào)度結(jié)果（Z=310）Fig.13 Scheduling results of single stage decision method（Z=310）

圖14 期望場景方法調(diào)度結(jié)果（Z=307.5）Fig.14 Scheduling results of expectation scenario method（Z=307.5）

圖15 RS方法調(diào)度結(jié)果（Z=339）Fig.15 Scheduling results of right shift method（Z=339）

圖16 前攝-反應(yīng)方法調(diào)度結(jié)果（Z=309.5）Fig.16 Scheduling results of proactive-reactive method（Z=309.5）

4 結(jié) 論

1）以物料供應(yīng)干擾環(huán)境下的飛機(jī)移動生產(chǎn)線裝配作業(yè)調(diào)度問題為研究對象，建立了動態(tài)調(diào)度框架，將滾動決策點的調(diào)度決策劃分為固定決策階段和預(yù)測決策階段，并建立了二階段近似優(yōu)化模型。

2）設(shè)計了以兩階段禁忌搜索為框架的啟發(fā)式算法來求解二階段近似優(yōu)化模型，算法中內(nèi)嵌了基于局部前瞻搜索的串行調(diào)度機(jī)制。數(shù)值實驗表明，算法在求解質(zhì)量方面具有良好的性能。

3）物料供應(yīng)干擾環(huán)境下的數(shù)值實驗和應(yīng)用案例表明，預(yù)測決策階段充分利用了最新獲得的不確定性信息，能有效輔助固定決策階段做出更優(yōu)的決策結(jié)果，增強(qiáng)了調(diào)度決策的后驗優(yōu)化能力，驗證了動態(tài)調(diào)度方法的有效性和可行性。

后續(xù)研究將進(jìn)一步考慮物料供應(yīng)干擾環(huán)境下的飛機(jī)移動生產(chǎn)線周期性調(diào)度問題，以完善飛機(jī)移動生產(chǎn)線的干擾管理方法。