規(guī)則啟發(fā)式算法在大規(guī)模飛機(jī)脈動(dòng)式總裝生產(chǎn)線的應(yīng)用研究

李嘯 牛冠凱

（中國(guó)航空制造技術(shù)研究院，北京 100024）

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

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

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

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

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

圖1 飛機(jī)脈動(dòng)式總裝生產(chǎn)線示意圖

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

圖2 波音787 飛機(jī)總裝脈動(dòng)生產(chǎn)線

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

一、研究現(xiàn)狀

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

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

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

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

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

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

本文涉及的變量及說(shuō)明見(jiàn)表1。

表1 模型涉及的變量及說(shuō)明

（一）問(wèn)題描述

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

圖3 示例工藝

圖3 中節(jié)點(diǎn)代表工序，指向箭頭（弧）代表兩工序之間存在前后邏輯約束。對(duì)于正排策略來(lái)說(shuō)，箭頭終點(diǎn)工序的開(kāi)始時(shí)間應(yīng)不早于箭頭起點(diǎn)工序的結(jié)束時(shí)間；對(duì)于倒排策略來(lái)說(shuō)，箭頭起點(diǎn)工序的結(jié)束時(shí)間應(yīng)不晚于箭頭終點(diǎn)工序的開(kāi)始時(shí)間。飛機(jī)脈動(dòng)式總裝生產(chǎn)線存在站位約束，圖上的工序節(jié)點(diǎn)會(huì)被分發(fā)到各個(gè)站位上并限定只能在該站位上完成。此外，工序的調(diào)度還受到資源約束，即任意時(shí)刻車(chē)間能提供的資源都是有限的。

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

（二）數(shù)學(xué)模型

正（倒）排邏輯約束、資源約束和站位約束說(shuō)明見(jiàn)表2。

表2 約束說(shuō)明

計(jì)劃制定階段：

計(jì)劃執(zhí)行階段：

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

三、算法設(shè)計(jì)

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

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

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

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

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

站位節(jié)拍變動(dòng)步長(zhǎng)?CT與不均衡數(shù)UM相關(guān)。

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

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

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

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

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

BIMSLK 算法流程如下：

Step 1：確定CT0；

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

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

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

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

BIMLSK 算法流程如圖4 所示。

圖4 BIMLSK 算法流程圖

四、算例驗(yàn)證

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

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

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

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

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

續(xù)表 3 測(cè)試結(jié)果

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

測(cè)試結(jié)果表明：

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

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

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

五、結(jié)論與展望

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

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

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

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

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