李嘯 牛冠凱

（中國航空制造技術研究院，北京 100024）

航空工業(yè)始終站在世界高技術發(fā)展前沿，是世界主要國家的戰(zhàn)略性產(chǎn)業(yè)，是一個國家綜合國力的重要體現(xiàn)。近年來，我國航空工業(yè)取得了快速發(fā)展，極大地促進了冶金、化工、材料、電子、機械和信息等領域的技術發(fā)展，引領了國家的創(chuàng)新。

與一般機械產(chǎn)品不同，飛機產(chǎn)品的制造過程十分復雜，且飛機裝配一般占整架飛機生產(chǎn)周期的50%～70%。飛機總裝的技術能力和管控能力一直是飛機制造面臨的核心難題，因此如何建立和維護高效的飛機總裝生產(chǎn)線成為研究重點。

飛機總裝一般有固定式裝配和移動式裝配兩種方式，移動式裝配又分為連續(xù)移動和間歇移動兩種模式，其中按照一定周期間歇移動的總裝模式稱為“脈動式”。

飛機移動式裝配生產(chǎn)線起源于二戰(zhàn)時期的美國福特汽車公司，戰(zhàn)爭造成的大量需求和飛機本身簡單固定的構型使該條長達1 英里的L型移動式裝配線十分成功，該條生產(chǎn)線一個小時就可以生產(chǎn)一架飛機[1]。但現(xiàn)代飛機往往構型多變、技術復雜，并且同一構型的飛機需求不大，所以長期以來都采用固定式裝配。隨著數(shù)字化技術和智能制造的發(fā)展，固定式裝配方法已經(jīng)不能滿足精益化和數(shù)字化的要求，且傳統(tǒng)的固定式裝配方式無法避免地會產(chǎn)生大量的拖期問題，這些問題會嚴重影響飛機的裝配進度。移動式裝配線的使用可以使裝配更加專業(yè)化和精益化，使生產(chǎn)進度更加便于管理，同時也可以減少拖期情況的發(fā)生，并降低工序拖期的影響。

飛機脈動式總裝是指在車間內(nèi)劃分一定數(shù)量的站位[2]，如圖1 所示，將整個總裝工藝的工序任務分配在各個站位內(nèi)，每個站位上都可以執(zhí)行一架飛機的裝配任務。當所有站位上的裝配任務完成后，站位上所有的飛機都向下一個站位移動，飛機在最后一個站位上裝配完成。飛機脈動式裝配線具有明顯節(jié)奏性、工位專業(yè)化程度高、裝配進度易于掌握和自動化程度高等特點。

圖1 飛機脈動式總裝生產(chǎn)線示意圖

波音717 總裝線是第一條現(xiàn)代飛機的移動式裝配生產(chǎn)線，設2 個固定站位和6 個移動站位，縮短了50%的裝配周期。與同時期建設的阿帕奇武裝直升機的脈動裝配線經(jīng)過長達10 年的改進相比，波音717 總體裝配周期縮短了85%，該條生產(chǎn)線更是獲得了新鄉(xiāng)獎（被譽為制造業(yè)的諾貝爾獎）。隨后，波音公司擴大了對移動式裝配技術的應用，在波音多型號飛機移動式裝配線的技術基礎上，結合模塊化裝配理念最終建成了先進的波音787 脈動式總裝線[3]，如圖2 所示。新一代波音787 應用脈動生產(chǎn)線技術創(chuàng)造了每三天制造出一架寬體大型客機的生產(chǎn)紀錄。

圖2 波音787 飛機總裝脈動生產(chǎn)線

由于脈動式裝配線較固定式裝配線可以提高裝配效率和裝配質(zhì)量，降低總裝成本等優(yōu)勢，洛克希德·馬丁公司、阿古斯特維斯特蘭公司分別建立了F-35 和W159 型武裝直升機的脈動式裝配線[4]。我國突破了多自由度調(diào)姿定位技術、大部件自動化對接技術、數(shù)字化測量技術和軌道移動等關鍵技術，部分型號飛機總裝也采取脈動式裝配方法，如中航工業(yè)西飛公司和中航工業(yè)洪都公司均建成了飛機總裝脈動生產(chǎn)線。

一、研究現(xiàn)狀

飛機總裝脈動線的成功實施需要研究裝配工序如何合理下發(fā)到各個站位上進而使各個站位上完成時間接近一致，解決站位上如何調(diào)度才能盡早地完成全部工序、站位上受影響的工序如何重新調(diào)度等問題。飛機的總裝過程采取脈動式裝配方法，但仍存在站位間節(jié)拍不平衡和執(zhí)行過程干擾頻發(fā)的問題。該問題可以抽象為飛機總裝脈動生產(chǎn)線平衡問題和資源受限的項目調(diào)度問題。這兩類問題都是典型的NP-hard問題，求解這些問題可以采用精確算法和啟發(fā)式算法兩類方法。

精確求解方法是以求得全局最優(yōu)解為目標的一類方法，Cavdur[5]采用混合整數(shù)規(guī)劃的方法，以最小站位節(jié)拍為優(yōu)化目標求解考慮工序返工影響的裝配線平衡問題，同時提出隨著規(guī)模增長會發(fā)生模型過大的現(xiàn)象。張宇哲[6]等人采用并證明了分支定界算法對規(guī)模在90 工序及以下的資源受限項目調(diào)度問題，具有較好的求解性能。事實上，對于大規(guī)模的實際問題來說，最優(yōu)解的求解耗時往往呈“爆炸式”增長，難以在有效時間內(nèi)得到結果，所以工程上一般不采取精確算法來解決實際問題。

啟發(fā)式算法分為元啟發(fā)式算法和基于優(yōu)先級的規(guī)則啟發(fā)式算法。元啟發(fā)式算法相較于精確求解算法耗時較少，文獻中所研究的求解調(diào)度問題的元啟發(fā)式算法包括但不限于多目標離散粒子群優(yōu)化算法（MODPSO）[7]、快速非支配排序的多目標優(yōu)化遺傳算法（NSGA-II）[8]、改進多種群遺傳算法[9]和三階段算法[10]，所用的算例規(guī)模均在120 工序及以下，遠達不到動輒近千道工序的飛機脈動式總裝生產(chǎn)線平衡和調(diào)度問題的規(guī)模。而規(guī)則啟發(fā)式算法具有計算速度快、算法實現(xiàn)簡單且在許多實際問題中求解效果良好等優(yōu)點。Browning[11]比較了20 種優(yōu)先規(guī)則，發(fā)現(xiàn)各種算法的表現(xiàn)在不同情形下存在差異。

為了應對計劃執(zhí)行過程中的干擾，飛機的總裝車間主要采取前攝性調(diào)度和反應性調(diào)度兩種策略。前攝性調(diào)度是在作生成計劃時就預測有可能發(fā)生的擾動因素，并采用預留時間[12]、資源緩沖[13]或優(yōu)先完成不穩(wěn)定性高的任務[14]等方法提高計劃的魯棒性。但僅提高計劃的魯棒性無法達到完全規(guī)避實際干擾因素的目的。因此，飛機的總裝車間采取反應性調(diào)度策略來應對頻發(fā)的干擾。反應性調(diào)度是在發(fā)生擾動后對計劃進行及時調(diào)整的手段。

綜上所述，本文采取BIMSLK 算法輔助飛機總裝脈動線初始計劃的制定，優(yōu)化目標為最小站位節(jié)拍和站位間節(jié)拍平衡，并采取反應性調(diào)度策略，使用MSLK 算法對計劃執(zhí)行過程進行維護，優(yōu)化目標為最短工期。

二、飛機總裝脈動生產(chǎn)線調(diào)度模型

本文涉及的變量及說明見表1。

表1 模型涉及的變量及說明

（一）問題描述

飛機總裝工藝圖可以用有向無環(huán)圖表示，如圖3 所示。

圖3 示例工藝

圖3 中節(jié)點代表工序，指向箭頭（?。┐韮晒ば蛑g存在前后邏輯約束。對于正排策略來說，箭頭終點工序的開始時間應不早于箭頭起點工序的結束時間；對于倒排策略來說，箭頭起點工序的結束時間應不晚于箭頭終點工序的開始時間。飛機脈動式總裝生產(chǎn)線存在站位約束，圖上的工序節(jié)點會被分發(fā)到各個站位上并限定只能在該站位上完成。此外，工序的調(diào)度還受到資源約束，即任意時刻車間能提供的資源都是有限的。

飛機總裝脈動生產(chǎn)線制定計劃階段的生產(chǎn)線平衡問題需要考慮邏輯約束、資源約束和站位約束，以最小站位節(jié)拍為第一目標。在確保第一目標的前提下考慮站位間節(jié)拍平衡，并以最大站位完成時間（即站位節(jié)拍）與最小站位完成時間差值與站位節(jié)拍之間的比率衡量。計劃維護階段資源受限的項目調(diào)度問題以最短工期為優(yōu)化目標。

（二）數(shù)學模型

正（倒）排邏輯約束、資源約束和站位約束說明見表2。

表2 約束說明

計劃制定階段：

計劃執(zhí)行階段：

其中，在同一調(diào)度過程中，各調(diào)度階段需同時滿足（1）式中正排或倒排邏輯約束中的一種。

三、算法設計

調(diào)度機制主要有串行調(diào)度和并行調(diào)度兩種。串行調(diào)度機制是在調(diào)度階段內(nèi)只完成一道工序的調(diào)度，隨著I個階段的調(diào)度后，所有工序完成調(diào)度集合為一個工藝的調(diào)度，顯然對于串行調(diào)度來說I=N。并行調(diào)度機制是在階段內(nèi)至少完成一個工序的調(diào)度，直到當前階段沒有符合條件的可調(diào)度工序才進入下一個調(diào)度階段，對于并行調(diào)度來說I≤N。

本文采取并行調(diào)度機制，對于每個階段都設定一個時鐘值，并使調(diào)度階段內(nèi)被調(diào)度的工序開始時間為當前時鐘值。

調(diào)度階段采取時鐘推進的方法，即當此階段無可調(diào)度的工序時，時鐘推進到下一個存在可排工序的時間節(jié)點上，較容易發(fā)現(xiàn)，這個節(jié)點一般為可用資源量發(fā)生增加的點，即工序結束時發(fā)生資源釋放的時間，所以將時鐘試探性地推進到大于當前時鐘的某個工序結束時間。若該時鐘下的調(diào)度階段存在可調(diào)度工序，則調(diào)度階段推進到此時。

最小松弛時間優(yōu)先（MSLK）算法是以任務的緊急情況為標準確定任務優(yōu)先級的方法。當一個時鐘越接近工序的最晚開始時間時，則認為該工序越緊急，一旦時鐘推進到最晚開始時間之后，且該工序仍然沒有開始，則認為一定發(fā)生了拖期，為了減少拖期時間需要優(yōu)先開始該工序，所以這是一種非常符合現(xiàn)場執(zhí)行狀態(tài)的優(yōu)先級算法，松弛度為工序最晚開始時間和當前時鐘值之差。

對于存在工序限定站位的工藝來說，只采取一次MSLK 算法可能會產(chǎn)生無解或站位節(jié)拍不均衡的情況，為此需要按照步長?CT對CT進行更新并迭代調(diào)度。

站位節(jié)拍變動步長?CT與不均衡數(shù)UM相關。

不平衡數(shù)UM的取值分兩種情況，當站位間節(jié)拍取值為CTj且無解時，取所有不滿足約束的工序的加工時間之和作為不平衡數(shù)的值；當有解但站位間節(jié)拍不平衡時，由于使用盡快完成更多任務的調(diào)度模式，所以一般空閑時間集中在最后一個站位上，此時取最后一個站位完成時間與站位節(jié)拍的差值作為不平衡數(shù)。

初始情況下，設CT0為最大工序加工時間，該值為可能存在有解情況下的CT0最小取值。

為了保證收斂速度，對CT的取值區(qū)間采取二分下降的方法，最小閾值為1 個時間單位，因此需要通過UM確定CT解的取值區(qū)間（a，b），按照本文CT0的取值，可認為在執(zhí)行第一次調(diào)度計算前，CT取值區(qū)間為（CT0，∞），當?shù)趈次后，首次出現(xiàn)?CT<0（若CT0足夠大，使初排時有解且不平衡，則為首次出現(xiàn)?CT>0，按照本文CT0的取值，一般j=1）。

確定CT解的取值范圍后，此時不平衡數(shù)的作用為指向作用，?CT的取值朝著UM的指向改變。

并且縮小CT解的取值范圍。

BIMSLK 算法流程如下：

Step 1：確定CT0；

Step 2：在僅考慮邏輯約束的條件下完成工序倒排；

Step 3：生成調(diào)度階段滿足資源約束和邏輯約束的工序集

Step 6：時鐘推進到下一個調(diào)度階段，重復執(zhí)行Step3~6，直至所有工序完成調(diào)度；

Step 7：若不滿足?CTj<1，計算UM和?CT，縮小CT取值區(qū)間，并更新CT取值，重復Step2~7 步。

BIMLSK 算法流程如圖4 所示。

圖4 BIMLSK 算法流程圖

四、算例驗證

本文仿照經(jīng)典算例PSPLIB 的格式隨機生成工序規(guī)模N分別為1000、2000、3000、4000、5000 的工藝文件，每種規(guī)模下生成弧數(shù)量AN有差別的5 種工藝，共25 種工藝，每種工藝進行10 組實驗，分別測試制定計劃階段針對每種工藝求解的平均計算時間T、迭代次數(shù)J、CT值、F1值；執(zhí)行階段站位工序達到相同規(guī)模時的計劃調(diào)整所需計算時間TMSLK值和最小工期值，并分別以評價TDR算法和MIS 算法與MSLK 算法計算的最小工期F2之間的相對差距，該值越大說明二者越劣于MSLK 算法。

工藝參數(shù)：R=10，P=7,RNr∈[0,10],?tn∈[1,10],資源在各站位上總量設為10，資源均為可再生資源，即工序開始時占用，完成時釋放。

算法在windows11 操作系統(tǒng)上用C 語言實現(xiàn)，硬件信息：AMD R7-5800H 處理器，3.2GHz主頻，16G 內(nèi)存。測試結果見表3。

在計劃制定階段求解生產(chǎn)線平衡問題時，隨著問題規(guī)模的增長，BIMSLK 算法的求解時間也隨之增長，1000 工序規(guī)模的求解時間不超過7s，5000 工序規(guī)模的求解時間不超過100s。但弧數(shù)量AN的增長對于求解時間的影響較小，以5000 工序規(guī)模的工藝為例，弧數(shù)量為80.97 萬和弧數(shù)量為227.59 萬的工藝分別使用BIMSLK算法，求解時間的增長在3s 左右。

AN和N的增長都會使站位間節(jié)拍CT變大。F1值隨著N的增大而減小，規(guī)模為1000 時F1波動較大且最大值達到了1.24%，當問題規(guī)模達到5000 時，F(xiàn)1最大值僅有0.006%。

續(xù)表 3 測試結果

在計劃執(zhí)行階段，MSLK 算法求解耗時大于TDR 和MIS 算法，但差距較小，對于5000 規(guī)模時該差距最大但也不超過0.5s。TDR 和MIS 算法求得的最短工期長于MSLK 算法，其中最小值為8.92%；最最大值達到19.76%大值達到14.60%，最小值為2.72%。

測試結果表明：

（1）BIMSLK 算法可以在有效時間內(nèi)得到大規(guī)模問題的站位間平衡的解；

（2）隨著問題規(guī)模的上升，BIMSLK 算法求得的解的穩(wěn)定性和平衡性也趨向更好；

（3）MSLK 算法可以在較短時間內(nèi)完成對大規(guī)模工藝的計劃修正，并且相較于TDR 算法和MIS 算法求得的解，工期更短。

五、結論與展望

本文針對飛機脈動生產(chǎn)線計劃下發(fā)和執(zhí)行過程涉及的調(diào)度問題，采用BIMSLK 算法輔助大規(guī)模的飛機總裝脈動線初始計劃的制定，結果表明該算法可以在有效時間內(nèi)生成一個較為平衡的解；采取MSLK 算法模擬對站位內(nèi)的大規(guī)模工序進行反應性調(diào)度，與TDR 算法和MIS 算法相比，三種算法均能在短時間內(nèi)求得可行解，但MSLK 算法得到的解更優(yōu)。但本方法仍存在一些不足之處：

（1）為了確保算法可以執(zhí)行，本文選取了一個最小的CT0的取值，使迭代前的區(qū)間范圍過大，導致迭代次數(shù)較多；

（2）由于規(guī)則啟發(fā)式算法存在不穩(wěn)定性，對于小規(guī)模的問題得到的解可能較差；

（3）實際生產(chǎn)中排產(chǎn)需要制定具體消耗某個資源，本文以資源的容量為約束的排產(chǎn)模式，雖然可以降低計算難度，但需要在后續(xù)添加的任務分配工作才可以用于實際；

（4）本文并未考慮資源的利用率均衡等問題。