航空發動機脈動裝配生產線排產算法研究*

張 波，王園園，宋迎軍，魏小紅，黃 健

（1.中國航空規劃設計研究總院有限公司，北京 100120；2.西安航空發動機有限公司，西安 710021）

0 引言

脈動式裝配是對傳統固定站位式裝配方式的巨大革新，也是世界主流的發展趨勢[1-3]。這種裝配方式通過在生產組織、調度安排、物流配送、人員技能等各個方面進行相應地適應和調整來解決傳統固定站位式裝配過程中面臨的種種問題[4]。在脈動式裝配過程中，隨著站位和節拍的引入，生產過程更加緊湊，個別裝配任務的拖期對整個裝配流程的影響和沖擊很容易得以凸顯和放大[5-6]。由于裝配過程和供應鏈管理的復雜性，要完全消除這些拖期幾乎是不可能的。面對數十乃至數百道裝配工序，各種各樣的約束條件，一線生產管理人員很難臨時快速做出高質量的排產調度決策。為此，采用科學、高效的排產調度方法，在發生拖期的情況下臨時對裝配任務進行重新安排，減少對整個裝配流程的不利影響。對于脈動式裝配，學術界歷來關注的重點是站位的平衡問題，即在確定的節拍下力求站位數量最少（第一類平衡問題），或在確定的站位下力求節拍最短（第二類平衡問題）[7-8]。并且在進行站位平衡時，通常關注的是裝配工時在站位之間的協調性，不考慮裝配人員工作負荷的飽滿性和平衡性。這使得脈動式裝配生產線在實際運行過程中往往面臨以下困難：（1）裝配順序仍需進一步確定；（2）人員調度仍需進一步解決；（3）無法適應生產過程中出現的各種異常。汪圓[9]、蔡瑋[10]等借助元啟發式算法對于飛機脈動裝配過程中的中小型的人員調度問題進行了求解，取得了較好的效果。然而，發動機裝配過程中涉及的任務數量更多，工時更短，對排產的響應速度要求更高，相關研究較少。本文從工藝過程和生產管理要求出發，深入地分析了其排產面臨的約束條件與優化目標；在對比多種排產算法的基礎之上，提出了多規則融合算法。與常規的元啟發式算法相比，多規則融合算法對約束的遵守力度更高，擴展更為便利，其結果具有確定性，求解速度高，適合工程應用。

1 約束條件與優化目標

1.1 約束條件

發動機脈動裝配過程中，多臺分別處于不同裝配狀態的發動機被吊裝在軌道吊車上，按照統一的節拍改變站位。完成所有站位的裝配工作后，軌道吊車返回到第一站位，接受新的發動機裝配任務。排產時面臨的約束條件主要包括以下幾個方面。

（1）工藝約束。工藝約束即裝配過程中必須遵守的先后順序。裝配任務之間的先后順序通常比較復雜，表現為網絡狀。除了關鍵路線上的裝配任務，其余任務的執行時段都可以在一定范圍內浮動。

（2）站位約束。由于采用了脈動式的裝配方式，一些裝配過程中所需使用的專用設備被固定設置在特定的站位上。這使得與之相應的裝配任務必須在這些特定的站位上才能執行。

（3）資源約束。盡管總裝部份出于縮短裝配周期的考慮，為各項裝配任務配備了專用的資源，大大減少了資源共用的情況，使得從理論上來講可以消除許多資源約束。但是，為了應對可能的設備故障、人員短缺等各種意外情況，依然有必要把各類資源的數量作為參數納入排產調度的計算模型中，以便于在需要的時候可以通過簡單地修改參數，實現對異常情況的快速響應。

（4）班制約束。發動機裝配是勞動力密集的制造環節，因此在排產調度的過程中非常有必要把安全生產和人性化的因素納入考慮。為此，排產調度結果應當盡可能地與班制時間吻合。例如，在8 h的工作班制下，盡可能地使得裝配工作不要跨越上、下午的兩個4 h的工作時段，也盡力不要跨越工作日。這是因為跨越工作時段的裝配工步，一方面容易對裝配工人產生精神壓力；另一方面容易造成工作遺漏和安全事故。

（5）空間約束。發動機的裝配需要多人共同協作。而為了實現并行工作，縮短裝配周期，常常還需要增加裝配的人員數量。這可能會導致裝配人員因為間距太近而導致相互之間形成動作干涉，影響裝配效率。為此有必要在一些裝配環節，例如，風扇主體外殼的支架安裝，劃分相互獨立的工作區域。一個工作區域內在一個時刻只能允許一個裝配任務。由于大量裝配人員并行操作是造成工作區域緊張的主要原因，所以減少并行操作是規避空間約束的有力措施。為了簡化算法、提高求解速度，也可以在工藝過程梳理部分將許多人員密集型的并行操作進行強制化的串行處理，從而規避上述空間約束。

1.2 優化目標

與其他生產線排產時追求工期最短不同，脈動生產線的工期由生產線的節拍決定，因此在這方面沒有優化的空間。在此，管理部門關注的優化目標包括：人員工作量的均衡，以及對于排產需求的快速響應。

發動機裝配過程中存在著大量可以并行執行的任務，如果不加優化地直接并行，很有可能各時段對包括人力在內的各類資源的需求極不均衡，從而導致各人員的工作量也因此極不均衡。大體而言，有兩種方式來提高人員工作量的均衡度：一種方法是直接建立各人員工作時間的統計量，通過控制方差來實現均衡；另一種方法是盡量減少工作人員的總數，通過力爭實現各人員滿負荷工作來間接地實現工作量的均衡。顯然，第二種方式更加具有積極意義，為此，本文采用第二種方式。

盡管發動機裝配的周期可能長達幾天，分解到具體裝配任務上的時間其實并不長，通常只有幾分鐘到幾十分鐘。因此，排產調度的響應時間也必須控制在幾分鐘之內，最好幾十秒以內。實際上，在發動機脈動裝配的過程中裝配時間的嚴重偏移（提前或拖延）將會是引發重新排產的重要因素。因此，各個裝配任務結束時都有可能引發重新排產。所以，重新排產的時間間隔與各個裝配任務的工時長度密切相關。以某型號發動機為例，由于各裝配任務的工時長度接近指數分布，如圖1所示。可以預見，裝配過程中的重新排產要求的時間間隔長度也將符合指數分布。如果從響應速度上要覆蓋99%重排事件，需要排產的時間小于μ/100，約32 s。考慮到重新觸發排產的過程中可能還需要一些人工的手動操作（例如登錄系統、刷新數據、啟動排產等），真正留給排產計算的時間可能只有幾秒。

2 優化算法

2.1 算法選擇與對比

當前主流的排產算法主要包括基于大規模搜索的精確解法[11]和線性規劃方法[12]，基于約束理論的傳統算法[13-14]，基于迭代進化的各類元啟發式算法[15]和基于貪心策略的規則算法[16-17]。另外，還有學者提出了基于多代理競爭的分布式決策算法[18-19]，這種采用的分散決策機制具有較強的創新性，但是實際應用較少。

發動機脈動裝配線排產問題涉及的任務數量多，約束條件多且復雜，數學表達的難度大，計算速度要求高，不適宜采用精確解法和元啟發式算法。脈動式裝配中各項生產資源相對比較均衡，瓶頸效應并不突出，所以也不宜采用基于約束理論的傳統算法。為此，對于發動機脈動裝配線排產而言，比較適合采用規則算法。特別地，為了適應不同約束條件對排產提出的要求，應采用多規則融合算法。

多規則融合算法是對基于規則的普通排產算法的升級。在多規則融合算法中工藝約束和資源約束被以算法流程的形式加以貫徹和實施，以避免對這些“剛性約束”的突破。例如，通過建立裝配任務的篩選機制和資源時鐘更新機制，使得只有那些完成了其所有前序工序的任務和在所需時段內未被占用的資源才能納入排產計算。

在不違反剛性約束的前提下，算法將利用綜合評價的方式對滿足約束條件的多個生產任務進行評估，從中選擇最佳的任務，優先安排生產。具體而言，包括以下幾個方面的經驗性規則：優先處理等待時間最短的任務；優先處理松弛時間最短的任務；優先處理與剩余可用工作時間最接近的任務；優先處理對資源占用最少的任務。

由于這些經驗性的規則常常會分別指向不同的結果，因此，需要通過某種量化的方式來對規則進行綜合，即多規則融合。常見的綜合算法包括加權求和法、加權求積法等。

需要特別說明的是，對于脈動裝配線的排產而言，為了避免任務拖延打亂既定的裝配節拍，通常需要在懲罰函數的計算過程中給予松弛時間賦予較高的權重。這可能會導致某些原本等待時間較短的任務讓位于那些松弛時間較短的任務，從而增加生產過程中的等待時間。為此，在選擇懲罰函數最小的任務后，還應檢查能否在可執行的任務中找出在懲罰函數最小的任務開始之前就能完成的其他任務。顯然，如果存在這樣的任務，將其插入不會對懲罰函數最小任務的執行造成任何不利的影響。

2.2 排產流程與算法

2.2.1 數據準備

該部分的主要任務是獲取排產所需的裝配節拍、工藝數據、站位數據、班制數據。工藝數據主要包括：各裝配任務的編號、工時、用人數量、緊前任務編號、緊后任務編號、所屬站位、最早開始時間、最晚結束時間等信息；站位數據主要包括：各站位的編號、人員編號；班制數據主要包括：開工時間、休工時間。

特別需要說明的是，與一般裝配過程不同，采用脈動式裝配后，由于各站位上并行安裝的發動機相互獨立，而且這些發動機只有在完成其當前站位上所有裝配任務以后才能進入到其下一個站位，所以各站位上裝配任務的緊前、緊后任務都只限于是同屬于該站位的其他任務。在利用裝配任務網絡計算各個任務的最早開始時間和最晚結束時間時，必須使用同站位的緊前任務和緊后任務。

為了確保排產計算順利正確地執行，有必要在此部分對獲取的數據進行多角度的合理性檢查，并在必要時給出相應的提示或警告。

2.2.2 計劃排產

該部分負責安排各裝配任務的開始時間，并指定相關的操作人員。本文采用多規則融合算法，具體實現過程如下：

（1）讀取待排產的任務列表tasksToSchedule，并初始化已排產任務列表tasksScheduled；

（2）篩選出可以執行的裝配任務tasksValid，篩選的標準主要是檢查緊前任務是否已經被納入已排產列表tasksScheduled；

（3）確定各可執行任務的最早開始時間、松弛時間等信息；

（4）根據上述信息對各可執行任務進行評價，計算其懲罰函數值；

（5）找出懲罰函數最小的任務，將其確定為最佳任務taskBest；

（6）如果存在完成時間早于上述最佳任務的其他任務taskOther，將該任務確定為新的最佳任務taskBest；

（7）將最佳任務taskBest納入已排產任務列表tasksScheduled，并將其從待排產任務列表tasksToScehdule中移除；

（8）更新最佳任務taskBest和相關人員的狀態和完成/就緒時間；

（9）返回第（2）步，直到待排產的任務列表tasks-ToScehdule被清空。

排產算法流程如圖2所示。

3 案例分析

以某型號發動機為例對上述算法進行驗證。該型號發動機的裝配被劃分為118個任務，并被安排到5個站位，脈動周期設計為8 h，其裝配任務網絡如圖3所示。其中，不同站位的任務用不同的節點顏色加以區分。

圖3 某型號發動機的裝配任務網絡

為充分利用人力資源，需要部分人員承擔跨站位的裝配任務。為此，將人員分為6組，其中5組分別是各站位的常備人員，他們只負責本站位的裝配任務；剩下的1組（應急中心），負責在需要時臨時支持各站位。預計投入的裝配人員總數為35人，其中1～4站位常備4人，第5站位常備3人，應急中心配備16人。

根據上述約束，利用排產算法進行了求解。如圖4所示，各站位的裝配時間都不大于8 h，其中最大者為480 min，最小者為455 min。各站位的裝配時間比較均衡。如圖5所示，各人員的工時分布也較為均衡，平均工時為436.86 min，約占總工作時間的91%。

圖4 任務甘特圖

圖5 各人員的工時

4 結束語

航空發動機脈動裝配線排產以提高人員勞動生產率為目標，它具有問題規模大，約束條件多且復雜，響應速度要求高等特點。規則算法和元啟發式算法是求解工程實際排產問題的兩大主流方法。然而，面對動態調度對求解速度提出的苛刻要求，依賴反復疊代和群體計算的元啟發式算法無法勝任。此外，元啟發式算法在轉化生產規則方面的手段較為單一，對于復雜規則過度依賴于功效函數，雖然大多數情況下也能找到符合要求的結果，但是其代價卻是更為復雜的功效函數或更大的搜索范圍——而此舉又會進一步加劇求解速度的不足。

本文提出的多規則融合算法是對基于規則的普通排產算法的升級。在多規則融合算法中剛性約束被以算法流程的形式加以貫徹和實施；在不違反剛性約束的前提下，算法利用綜合評價的方式對滿足約束條件的多個生產任務進行評估，從中選擇最佳的任務，優先安排生產。與元啟發式算法相比，多規則融合算法對約束的遵守力度更高，擴展更為便利；更重要的是，由于避免了隨機擾動，反復疊代和群體計算，多規則融合算法具有確定性，其求解速度非常高，特別適合應用于航空發動機脈動裝配線。