考慮物料供應干擾的飛機移動生產線動態調度

盧斌，陸志強

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

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

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

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

1 問題描述與數學模型

1.1 問題描述與基本假設

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

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

圖1 飛機移動生產線裝配工位布局圖Fig.1 Assembly station layout of aircraft mobile production line

表1 參數與決策變量Table 1 Parameters and decision variables

1.2 物料供應干擾環境下的動態調度框架

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

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

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

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

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

1）JF類。物料配送作業已經完成或已經開始但未完成的作業（作業1、2），按原始計劃執行。

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

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

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

結合信息和操作層面的分析，以及對不同作業類型決策屬性的描述，給出物料供應干擾環境下的動態調度框架，如圖4所示。

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

1.3 二階段近似優化模型

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

圖4 動態調度框架Fig.4 Framework of dynamic scheduling

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

Y=（A1，A2，…，An）

式（2）可通過不同場景下的預測決策，評估固定決策的自身效能及應對不同場景的反應能力，達到兼顧調度決策反應性和預見性的目的。為了使模型表達更為簡潔，決策變量統一用場景進行表述。補充參數并修正決策變量，修正后的參數和決策變量如表2所示。

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

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

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

2 算法設計

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

圖5 作業列表編碼拆分示意圖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類作業搜索不同場景下的預測決策。禁忌搜索的鄰域生成方式、禁忌對象設置與TS1相同，禁忌表長度為TL-2，迭代次數為Iter-2。在獲取TS1中待評估作業列表基礎上，對搜索到的每一個作業列表，采用基于局部前瞻搜索的串行調度機制進行解碼，得到當前場景下的調度結果。需要注意，在各個場景下重復進行禁忌搜索尋優過程中，對JP類作業的決策結果均補充自同一個固定決策。

2.3 基于局部前瞻搜索的串行調度機制

結合目標函數中所考慮的優化指標，本文設計了基于局部前瞻搜索的串行調度機制對作業列表進行解碼，算法具體步驟如下：

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

步驟10若i

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

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

3 數值實驗

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

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

3.1 與CPLEX后驗求解結果對比

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

1）實驗1。使用CPLEX軟件單次求解數學模型。

2）實驗2。采用簡化的動態調度框架和TTSBH算法（固定決策階段的作業為前兩次干擾發生時刻之間的作業，后續作業利用后驗信息進行預測決策），單次求解數學模型。

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

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

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

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

3.2 物料供應干擾環境下的對比實驗

為了驗證本文動態調度方法的求解效果，本節設計了物料供應干擾環境下的對比實驗：

1）實驗4。采用本文的動態調度框架和TTSBH算法，滾動求解數學模型。

2）實驗5。以各個概率分布的期望值構建期望場景，預測決策階段僅利用期望場景下的預測決策結果對固定決策階段決策進行評價，滾動求解數學模型。

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

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

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

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

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

表4 小規模算例實驗結果Table 4 Experiment results of small-scale example

表5 大規模算例實驗結果Table 5 Experiment results of lar ge-scale example

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

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

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

3.4 不同目標權重比下的方法性能對比

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

3.5 應用案例

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

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

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

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

圖11 后驗求解調度結果（Z=280.5）Fig.11 Scheduling results of posteriori solution（Z=280.5）

圖12 本文方法調度結果（Z=284.5）Fig.12 Scheduling results of proposed method（Z=284.5）

圖13 單階段決策方法調度結果（Z=310）Fig.13 Scheduling results of single stage decision method（Z=310）

圖14 期望場景方法調度結果（Z=307.5）Fig.14 Scheduling results of expectation scenario method（Z=307.5）

圖15 RS方法調度結果（Z=339）Fig.15 Scheduling results of right shift method（Z=339）

圖16 前攝-反應方法調度結果（Z=309.5）Fig.16 Scheduling results of proactive-reactive method（Z=309.5）

4 結 論

1）以物料供應干擾環境下的飛機移動生產線裝配作業調度問題為研究對象，建立了動態調度框架，將滾動決策點的調度決策劃分為固定決策階段和預測決策階段，并建立了二階段近似優化模型。

2）設計了以兩階段禁忌搜索為框架的啟發式算法來求解二階段近似優化模型，算法中內嵌了基于局部前瞻搜索的串行調度機制。數值實驗表明，算法在求解質量方面具有良好的性能。

3）物料供應干擾環境下的數值實驗和應用案例表明，預測決策階段充分利用了最新獲得的不確定性信息，能有效輔助固定決策階段做出更優的決策結果，增強了調度決策的后驗優化能力，驗證了動態調度方法的有效性和可行性。

后續研究將進一步考慮物料供應干擾環境下的飛機移動生產線周期性調度問題，以完善飛機移動生產線的干擾管理方法。