航空發(fā)動(dòng)機(jī)脈動(dòng)裝配生產(chǎn)線排產(chǎn)算法研究*

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

（1.中國(guó)航空規(guī)劃設(shè)計(jì)研究總院有限公司，北京 100120；2.西安航空發(fā)動(dòng)機(jī)有限公司，西安 710021）

0 引言

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

1 約束條件與優(yōu)化目標(biāo)

1.1 約束條件

發(fā)動(dòng)機(jī)脈動(dòng)裝配過程中，多臺(tái)分別處于不同裝配狀態(tài)的發(fā)動(dòng)機(jī)被吊裝在軌道吊車上，按照統(tǒng)一的節(jié)拍改變站位。完成所有站位的裝配工作后，軌道吊車返回到第一站位，接受新的發(fā)動(dòng)機(jī)裝配任務(wù)。排產(chǎn)時(shí)面臨的約束條件主要包括以下幾個(gè)方面。

（1）工藝約束。工藝約束即裝配過程中必須遵守的先后順序。裝配任務(wù)之間的先后順序通常比較復(fù)雜，表現(xiàn)為網(wǎng)絡(luò)狀。除了關(guān)鍵路線上的裝配任務(wù)，其余任務(wù)的執(zhí)行時(shí)段都可以在一定范圍內(nèi)浮動(dòng)。

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

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

（4）班制約束。發(fā)動(dòng)機(jī)裝配是勞動(dòng)力密集的制造環(huán)節(jié)，因此在排產(chǎn)調(diào)度的過程中非常有必要把安全生產(chǎn)和人性化的因素納入考慮。為此，排產(chǎn)調(diào)度結(jié)果應(yīng)當(dāng)盡可能地與班制時(shí)間吻合。例如，在8 h的工作班制下，盡可能地使得裝配工作不要跨越上、下午的兩個(gè)4 h的工作時(shí)段，也盡力不要跨越工作日。這是因?yàn)榭缭焦ぷ鲿r(shí)段的裝配工步，一方面容易對(duì)裝配工人產(chǎn)生精神壓力；另一方面容易造成工作遺漏和安全事故。

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

1.2 優(yōu)化目標(biāo)

與其他生產(chǎn)線排產(chǎn)時(shí)追求工期最短不同，脈動(dòng)生產(chǎn)線的工期由生產(chǎn)線的節(jié)拍決定，因此在這方面沒有優(yōu)化的空間。在此，管理部門關(guān)注的優(yōu)化目標(biāo)包括：人員工作量的均衡，以及對(duì)于排產(chǎn)需求的快速響應(yīng)。

發(fā)動(dòng)機(jī)裝配過程中存在著大量可以并行執(zhí)行的任務(wù)，如果不加優(yōu)化地直接并行，很有可能各時(shí)段對(duì)包括人力在內(nèi)的各類資源的需求極不均衡，從而導(dǎo)致各人員的工作量也因此極不均衡。大體而言，有兩種方式來提高人員工作量的均衡度：一種方法是直接建立各人員工作時(shí)間的統(tǒng)計(jì)量，通過控制方差來實(shí)現(xiàn)均衡；另一種方法是盡量減少工作人員的總數(shù)，通過力爭(zhēng)實(shí)現(xiàn)各人員滿負(fù)荷工作來間接地實(shí)現(xiàn)工作量的均衡。顯然，第二種方式更加具有積極意義，為此，本文采用第二種方式。

盡管發(fā)動(dòng)機(jī)裝配的周期可能長(zhǎng)達(dá)幾天，分解到具體裝配任務(wù)上的時(shí)間其實(shí)并不長(zhǎng)，通常只有幾分鐘到幾十分鐘。因此，排產(chǎn)調(diào)度的響應(yīng)時(shí)間也必須控制在幾分鐘之內(nèi)，最好幾十秒以內(nèi)。實(shí)際上，在發(fā)動(dòng)機(jī)脈動(dòng)裝配的過程中裝配時(shí)間的嚴(yán)重偏移（提前或拖延）將會(huì)是引發(fā)重新排產(chǎn)的重要因素。因此，各個(gè)裝配任務(wù)結(jié)束時(shí)都有可能引發(fā)重新排產(chǎn)。所以，重新排產(chǎn)的時(shí)間間隔與各個(gè)裝配任務(wù)的工時(shí)長(zhǎng)度密切相關(guān)。以某型號(hào)發(fā)動(dòng)機(jī)為例，由于各裝配任務(wù)的工時(shí)長(zhǎng)度接近指數(shù)分布，如圖1所示。可以預(yù)見，裝配過程中的重新排產(chǎn)要求的時(shí)間間隔長(zhǎng)度也將符合指數(shù)分布。如果從響應(yīng)速度上要覆蓋99%重排事件，需要排產(chǎn)的時(shí)間小于μ/100，約32 s?？紤]到重新觸發(fā)排產(chǎn)的過程中可能還需要一些人工的手動(dòng)操作（例如登錄系統(tǒng)、刷新數(shù)據(jù)、啟動(dòng)排產(chǎn)等），真正留給排產(chǎn)計(jì)算的時(shí)間可能只有幾秒。

2 優(yōu)化算法

2.1 算法選擇與對(duì)比

當(dāng)前主流的排產(chǎn)算法主要包括基于大規(guī)模搜索的精確解法[11]和線性規(guī)劃方法[12]，基于約束理論的傳統(tǒng)算法[13-14]，基于迭代進(jìn)化的各類元啟發(fā)式算法[15]和基于貪心策略的規(guī)則算法[16-17]。另外，還有學(xué)者提出了基于多代理競(jìng)爭(zhēng)的分布式?jīng)Q策算法[18-19]，這種采用的分散決策機(jī)制具有較強(qiáng)的創(chuàng)新性，但是實(shí)際應(yīng)用較少。

發(fā)動(dòng)機(jī)脈動(dòng)裝配線排產(chǎn)問題涉及的任務(wù)數(shù)量多，約束條件多且復(fù)雜，數(shù)學(xué)表達(dá)的難度大，計(jì)算速度要求高，不適宜采用精確解法和元啟發(fā)式算法。脈動(dòng)式裝配中各項(xiàng)生產(chǎn)資源相對(duì)比較均衡，瓶頸效應(yīng)并不突出，所以也不宜采用基于約束理論的傳統(tǒng)算法。為此，對(duì)于發(fā)動(dòng)機(jī)脈動(dòng)裝配線排產(chǎn)而言，比較適合采用規(guī)則算法。特別地，為了適應(yīng)不同約束條件對(duì)排產(chǎn)提出的要求，應(yīng)采用多規(guī)則融合算法。

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

在不違反剛性約束的前提下，算法將利用綜合評(píng)價(jià)的方式對(duì)滿足約束條件的多個(gè)生產(chǎn)任務(wù)進(jìn)行評(píng)估，從中選擇最佳的任務(wù)，優(yōu)先安排生產(chǎn)。具體而言，包括以下幾個(gè)方面的經(jīng)驗(yàn)性規(guī)則：優(yōu)先處理等待時(shí)間最短的任務(wù)；優(yōu)先處理松弛時(shí)間最短的任務(wù)；優(yōu)先處理與剩余可用工作時(shí)間最接近的任務(wù)；優(yōu)先處理對(duì)資源占用最少的任務(wù)。

由于這些經(jīng)驗(yàn)性的規(guī)則常常會(huì)分別指向不同的結(jié)果，因此，需要通過某種量化的方式來對(duì)規(guī)則進(jìn)行綜合，即多規(guī)則融合。常見的綜合算法包括加權(quán)求和法、加權(quán)求積法等。

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

2.2 排產(chǎn)流程與算法

2.2.1 數(shù)據(jù)準(zhǔn)備

該部分的主要任務(wù)是獲取排產(chǎn)所需的裝配節(jié)拍、工藝數(shù)據(jù)、站位數(shù)據(jù)、班制數(shù)據(jù)。工藝數(shù)據(jù)主要包括：各裝配任務(wù)的編號(hào)、工時(shí)、用人數(shù)量、緊前任務(wù)編號(hào)、緊后任務(wù)編號(hào)、所屬站位、最早開始時(shí)間、最晚結(jié)束時(shí)間等信息；站位數(shù)據(jù)主要包括：各站位的編號(hào)、人員編號(hào)；班制數(shù)據(jù)主要包括：開工時(shí)間、休工時(shí)間。

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

為了確保排產(chǎn)計(jì)算順利正確地執(zhí)行，有必要在此部分對(duì)獲取的數(shù)據(jù)進(jìn)行多角度的合理性檢查，并在必要時(shí)給出相應(yīng)的提示或警告。

2.2.2 計(jì)劃排產(chǎn)

該部分負(fù)責(zé)安排各裝配任務(wù)的開始時(shí)間，并指定相關(guān)的操作人員。本文采用多規(guī)則融合算法，具體實(shí)現(xiàn)過程如下：

（1）讀取待排產(chǎn)的任務(wù)列表tasksToSchedule，并初始化已排產(chǎn)任務(wù)列表tasksScheduled；

（2）篩選出可以執(zhí)行的裝配任務(wù)tasksValid，篩選的標(biāo)準(zhǔn)主要是檢查緊前任務(wù)是否已經(jīng)被納入已排產(chǎn)列表tasksScheduled；

（3）確定各可執(zhí)行任務(wù)的最早開始時(shí)間、松弛時(shí)間等信息；

（4）根據(jù)上述信息對(duì)各可執(zhí)行任務(wù)進(jìn)行評(píng)價(jià)，計(jì)算其懲罰函數(shù)值；

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

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

（7）將最佳任務(wù)taskBest納入已排產(chǎn)任務(wù)列表tasksScheduled，并將其從待排產(chǎn)任務(wù)列表tasksToScehdule中移除；

（8）更新最佳任務(wù)taskBest和相關(guān)人員的狀態(tài)和完成/就緒時(shí)間；

（9）返回第（2）步，直到待排產(chǎn)的任務(wù)列表tasks-ToScehdule被清空。

排產(chǎn)算法流程如圖2所示。

3 案例分析

以某型號(hào)發(fā)動(dòng)機(jī)為例對(duì)上述算法進(jìn)行驗(yàn)證。該型號(hào)發(fā)動(dòng)機(jī)的裝配被劃分為118個(gè)任務(wù)，并被安排到5個(gè)站位，脈動(dòng)周期設(shè)計(jì)為8 h，其裝配任務(wù)網(wǎng)絡(luò)如圖3所示。其中，不同站位的任務(wù)用不同的節(jié)點(diǎn)顏色加以區(qū)分。

圖3 某型號(hào)發(fā)動(dòng)機(jī)的裝配任務(wù)網(wǎng)絡(luò)

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

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

圖4 任務(wù)甘特圖

圖5 各人員的工時(shí)

4 結(jié)束語

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

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