陸志強(qiáng)，周皓雪

(同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804)

基于精益思想的飛機(jī)移動式裝配線已成為飛機(jī)裝配生產(chǎn)的新模式，具有裝配效率高、質(zhì)量穩(wěn)定、可按需批量生產(chǎn)等特點，近年來被世界各大航空制造企業(yè)競相采用.實際上，對于每架飛機(jī)而言，移動式裝配線上的總裝任務(wù)調(diào)度問題具有裝配工序繁多、裝配任務(wù)復(fù)雜、裝配過程受到多重約束限制等特點.調(diào)度過程可根據(jù)實際應(yīng)用的目的抽象為資源受限項目調(diào)度問題(RCPSP)以及與之關(guān)聯(lián)的資源投入型問題(RIP)兩大類.前者與裝配線的規(guī)劃、設(shè)計和決策相關(guān)，而后者與裝配線的運作決策關(guān)聯(lián).對裝配線的日常運作決策而言，通常需要在給定工期的條件下，優(yōu)化裝配線的各類資源配置及分配使用，達(dá)到最小化資源投入總成本的目的，即資源投入型問題.對于一般裝配線來說，裝配線復(fù)雜度較低，工作可替代性強(qiáng).飛機(jī)移動式裝配線的工序繁瑣復(fù)雜、工作專業(yè)性強(qiáng)，對于特殊人力資源要求極高.同時，整個裝配周期較長，關(guān)鍵技術(shù)人員稀少并且可能存在不可用時間段，對于飛機(jī)裝配生產(chǎn)線考慮資源利用區(qū)間是重要且必要的.因此，在基本RIP的基礎(chǔ)上，考慮到飛機(jī)裝配生產(chǎn)中某些關(guān)鍵資源具有提前已知的不可用時間段，即引入資源空窗期約束，提出帶資源空窗期的資源投入型問題.

資源投入型問題作為RCPSP的對偶問題，最早由M?hring[1]引入，并且該問題被證明為NP-hard問題.以RCPSP的算法求解為基礎(chǔ)，得到了求解該問題的圖解精確算法.Drexl等[2]基于拉格朗日松弛和列生成方法為RIP提出了兩個下界算法，并且通過算例實驗與M?hring[1]的算法進(jìn)行了比較.Rodrigues等[3]提出了一種改進(jìn)型割平面法，通過啟發(fā)式算法得到初始解并不斷更新低界，縮小解空間，從而提高計算效率.由于精確算法只能求解小規(guī)模問題，因此大量國內(nèi)外學(xué)者針對大規(guī)模問題提出啟發(fā)式算法與元啟發(fā)式算法.Song等[4]提出帶局部搜索的進(jìn)化算法，允許項目延期但是設(shè)有極高的延期懲罰.Myszkowski等[5]在混合蟻群算法中嵌入啟發(fā)式優(yōu)先級規(guī)則對資源進(jìn)行分配.Van Peteghem等[6]提出了一種應(yīng)用于RIP的人工免疫算法.He等[7]設(shè)計了基于動態(tài)優(yōu)先級規(guī)則的啟發(fā)式算法，并對任務(wù)開始時間決策區(qū)間內(nèi)的所有位置進(jìn)行評測.Qi等[8]提出了一種新的粒子群算法，在解碼階段設(shè)計了多種啟發(fā)式規(guī)則以修復(fù)不可行解.由于現(xiàn)有考慮資源特點的RIP相關(guān)研究稀缺，因此帶資源空窗期的RCPSP的研究方法對本研究具有參考意義.胡淑芳[9]針對資源時間窗和任務(wù)可拆分特性，設(shè)計了小規(guī)模單技能及多技能項目調(diào)度問題求解的分支定界算法.廖廣瑞等[10]考慮資源的多技能和時間窗屬性，設(shè)計了基于優(yōu)先規(guī)則的Rollout求解算法，并嵌入了啟發(fā)式資源分配方法對資源進(jìn)行快速分配.綦方中等[11]研究了基于時間窗的多項目資源分配問題，提出了帶時間窗參數(shù)以及懲罰因子的多項目管理資源分配模型.

從現(xiàn)有文獻(xiàn)可以看出，對于RIP的研究范圍仍偏重于基本問題，而基本RIP通常設(shè)有大量假設(shè)條件，屬于較為理想化的純理論問題，因此RIP的研究成果難以與更為復(fù)雜的實際生產(chǎn)過程有效結(jié)合.此外，從算法設(shè)計上來看，大部分啟發(fā)式算法在任務(wù)開始時間的決策區(qū)間內(nèi)取值時，計算效率不高，并且易限于局部考慮而忽略全局影響.常見的搜索算法可分為以下兩類：一類以資源量進(jìn)行編碼，但這樣編碼容易導(dǎo)致資源上、下界差距較大，搜索效率低，難以找到結(jié)果較好的可行解；一類以任務(wù)開始時間進(jìn)行編碼，但這類編碼大多數(shù)未考慮問題特點，搜索的方向性不強(qiáng)，導(dǎo)致算法效率低.基于此，在進(jìn)行算法設(shè)計時重點考慮資源空窗期約束，首先提出求解RIP的啟發(fā)式算法.區(qū)別于基本RIP，設(shè)計了非關(guān)鍵任務(wù)優(yōu)先級、關(guān)鍵任務(wù)排入以及非關(guān)鍵任務(wù)調(diào)度的三階段啟發(fā)式算法,對模型進(jìn)行求解.通過進(jìn)一步的分析發(fā)現(xiàn)，啟發(fā)式算法處理大規(guī)模算例時具有局限性，因此在啟發(fā)式算法的基礎(chǔ)上設(shè)計了以非關(guān)鍵任務(wù)優(yōu)先級和關(guān)鍵任務(wù)開始時間為雙鏈表編碼的遺傳算法，并將啟發(fā)式規(guī)則嵌套在遺傳算法的解碼和評估階段，提高了求解的精確性.最后，通過數(shù)值實驗驗證了啟發(fā)式算法和遺傳算法的有效性，同時證實了空窗期約束的存在對于算法設(shè)計具有影響.

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

假設(shè)飛機(jī)裝配項目由若干項任務(wù)構(gòu)成，任務(wù)之間存在著一定的時序關(guān)系，任務(wù)的執(zhí)行需要消耗相應(yīng)的資源.記給定項目總工期為T，包含J項任務(wù)，每項任務(wù)j(j=1,2,…,J)的執(zhí)行時間為tj，p(j)為第j項任務(wù)的緊前任務(wù)集合，s(j)為第j項任務(wù)的緊后任務(wù)集合，tES,j、tLS,j、tEF,j和tLF,j分別為任務(wù)j(j=1,2,…,J)的最早開始時間、最晚開始時間、最早結(jié)束時間以及最晚結(jié)束時間,tTF,j表示任務(wù)j開始時間的浮動長度,即tTF,j=tLS,j-tES,j.項目中使用的可更新資源種類為P，每種資源的單位使用成本為Cp(p=1,2,…,P).rjp表示任務(wù)j(j=1,2,…,J)需要的單位資源p(p=1,2,…,P)的數(shù)量,rj,max表示任務(wù)j需要的所有資源中需求量最大的資源值.關(guān)鍵資源pk在特定的一段或多段時間區(qū)域內(nèi)不能工作，即資源的空窗期約束.Ae代表需要用到關(guān)鍵資源pk的任務(wù)集合.對時間進(jìn)行離散化處理，模型的求解目標(biāo)是優(yōu)化各時刻t(t=1,2,…,T)每種資源p(p=1,2,…,P)的最大需求量Rtp的總成本.

模型中決策變量包括：xjt為0、1變量，1表示任務(wù)j(j=1,2,…,J)在時刻t被執(zhí)行，否則取0；zjm為0、1變量，1表示任務(wù)j∈Ae在第m個非空窗期區(qū)間內(nèi)完成，否則取0.

1.2 空窗期

在飛機(jī)裝配的實際生產(chǎn)中，關(guān)鍵資源的使用時間往往不是連續(xù)的，某些時段可用，某些時段不可用，將這種約束稱為資源空窗期約束.參考劉振元等[12]相關(guān)論文，對空窗期相關(guān)參數(shù)進(jìn)行定義.

如圖1所示，假設(shè)有M個空窗期，m=1,2,3,…,M，tb,m和te,m分別為第m個空窗期的開始和結(jié)束時間.在空窗期內(nèi)資源可用數(shù)量為零，在非空窗期內(nèi)資源可用數(shù)量為常數(shù)R0.lm表示第m個空窗期的長

圖1 資源空窗期示意圖

度，易得lm=te,m-tb,m；δ(m-1,m)表示第m個非空窗期的長度，易得δ(m-1,m)=tb,m-te,m-1.假設(shè)tb,0=te,0=0.

1.3 數(shù)學(xué)模型

目標(biāo)函數(shù)為

(1)

約束為

(2)

(3)

(4)

(5)

t=1,2,…,T

(6)

txjt≤T,t=1,2,…,T

(7)

目標(biāo)函數(shù)(1)表示該問題是優(yōu)化整個周期內(nèi)各資源使用的最大總成本.約束條件(2)表明時刻t資源p的使用量；式(3)表示任務(wù)在整個周期內(nèi)的執(zhí)行時間滿足該任務(wù)工期約束；任務(wù)之間應(yīng)該滿足約束(4)，即滿足一定的優(yōu)先關(guān)系；式(5)說明需要關(guān)鍵資源的任務(wù)必須滿足空窗期約束；式(6)說明任務(wù)一旦開始，在完成之前不允許被中斷；式(7)說明所有任務(wù)的最晚結(jié)束時間不應(yīng)大于項目給定工期.

2 啟發(fā)式算法設(shè)計

啟發(fā)式算法的設(shè)計思路為：基于關(guān)鍵路徑法(CPM)獲得項目中的關(guān)鍵鏈，確定關(guān)鍵任務(wù)和非關(guān)鍵任務(wù).將關(guān)鍵任務(wù)納入調(diào)度計劃，決策關(guān)鍵任務(wù)排入方式為連續(xù)排入或預(yù)留時間間隔排入；在此基礎(chǔ)上安排非關(guān)鍵任務(wù)，提出四種規(guī)則確定非關(guān)鍵任務(wù)優(yōu)先級，然后以最小資源需求量為目標(biāo)，確定非關(guān)鍵任務(wù)的決策區(qū)間，再通過局部規(guī)則判斷基準(zhǔn)在決策區(qū)間內(nèi)的取值，最終確定非關(guān)鍵任務(wù)調(diào)度位置.通過以上分析可知，該啟發(fā)式算法可根據(jù)決策重點分為三個階段.

2.1 第一階段：生成非關(guān)鍵任務(wù)優(yōu)先級列表

吳怡薇等[13]在求解資源水平問題時提出采用資源用量規(guī)則和自由度規(guī)則來確定非關(guān)鍵任務(wù)優(yōu)先級.本研究在基本RIP上考慮空窗期約束，為了減少空窗期對任務(wù)的交互影響，增加工期規(guī)則以及最早開始時間(EST)規(guī)則，使可能對調(diào)度結(jié)果產(chǎn)生更大影響的任務(wù)擁有更多可排空間，盡早排入.

(1) 工期規(guī)則

任務(wù)工期越長，與已排定任務(wù)重疊度越高，在有空窗期的條件下，與空窗期重疊的可能性也越大.RIP目標(biāo)的本質(zhì)就是通過調(diào)度使得任務(wù)間重疊度降低，所以tj越長，非關(guān)鍵任務(wù)j的優(yōu)先級越高.

(2) EST規(guī)則

一般而言，在RIP中任務(wù)調(diào)度順序與各任務(wù)在項目網(wǎng)絡(luò)圖中位置不完全一致.EST規(guī)則可作為前三種規(guī)則的補(bǔ)充，避免優(yōu)先級相同的情況出現(xiàn)，因此可定義tES,j越小，非關(guān)鍵任務(wù)j的優(yōu)先級越高.

任務(wù)的工期對開始時間決策區(qū)間的大小影響很大，而任務(wù)的資源用量直接影響資源投入總成本，故工期規(guī)則及資源用量規(guī)則作為優(yōu)先規(guī)則考慮.具體操作時，按照上述四種規(guī)則順序依次比較非關(guān)鍵任務(wù)j的tj、rj,max、tTF,j以及tES,j，最終確定非關(guān)鍵任務(wù)優(yōu)先級列表Lp.

第一階段算法步驟如下所示：

步驟1建立已安排任務(wù)集合S=?，未安排任務(wù)集合S′=J.

步驟2確定需要關(guān)鍵資源pk的任務(wù)集合Ae.

步驟4根據(jù)CPM獲得任務(wù)j∈J的tES,j、tLS,j、tEF,j、tLF,j和tTF,j.

步驟5確定關(guān)鍵任務(wù)為集合Cr，余下任務(wù)即為非關(guān)鍵任務(wù).

步驟6生成非關(guān)鍵任務(wù)優(yōu)先級列表Lp.

2.2 第二階段：關(guān)鍵任務(wù)排入方式的確定

2.2.2關(guān)鍵任務(wù)調(diào)整基準(zhǔn)

圖2 相關(guān)關(guān)鍵任務(wù)調(diào)整

第二階段算法步驟如下所示：

步驟1將集合Cr內(nèi)的所有關(guān)鍵任務(wù)連續(xù)排入.

步驟7t=t+1；返回步驟5.

2.3 第三階段：非關(guān)鍵任務(wù)的調(diào)度決策

2.3.1相關(guān)任務(wù)與相關(guān)距離dij

能夠影響任務(wù)j的開始時間tST,j的決策區(qū)間的任務(wù)為和任務(wù)j具有時序關(guān)系的任務(wù)，稱該任務(wù)為任務(wù)j的相關(guān)任務(wù).定義Re={i∈S|ij}為對任務(wù)j進(jìn)行調(diào)度時已經(jīng)完成調(diào)度的相關(guān)任務(wù).對于兩個相關(guān)任務(wù)i、j而言，定義相關(guān)距離dij為任務(wù)i到任務(wù)j的最長路徑的長度，易得dij=-dji.

2.3.2任務(wù)j∈J開始時間tST,j可排區(qū)間點集

(8)

(9)

(10)

從而形成最終的tST,j可排區(qū)間離散點集

Smove,j={tST,j1,tST,j2,…,tST,jn}

(11)

2.3.3任務(wù)j∈J開始時間tST,j可變區(qū)間點集

(12)

任務(wù)j開始時間tST,j的可變區(qū)間點集即為任務(wù)j開始時間tST,j的決策區(qū)間.

2.3.4局部最優(yōu)判斷基準(zhǔn)

對于任意非關(guān)鍵任務(wù)j而言，易得Schange,j?Smove,j，而Schange,j中的點實際上為只考慮任務(wù)j的資源總量最小解集，顯然集合內(nèi)的所有點未必都能對應(yīng)全局下的最小資源總成本.

根據(jù)優(yōu)先級排入非關(guān)鍵任務(wù)，待排任務(wù)的位置確定受后序任務(wù)的影響.因此，通過考慮任務(wù)j的調(diào)度位置對后序任務(wù)的排入影響來進(jìn)一步確定tST,j，即使得連續(xù)排入的兩個任務(wù)間結(jié)果最優(yōu).

第三階段算法步驟如下所示：

步驟2生成當(dāng)前任一時刻t的資源列表Rtp.

步驟3按照優(yōu)先級順序選擇非關(guān)鍵任務(wù)優(yōu)先級列表Lp中任務(wù)j，獲得其對應(yīng)的Re={i∈S|ij}，對于任意任務(wù)i∈Re求出相關(guān)距離dij，繼而得出tST,j可排區(qū)間點集Smove,j.

步驟7result[]中的最小值為最終結(jié)果，輸出該結(jié)果，算法結(jié)束.

3 遺傳算法設(shè)計

分析啟發(fā)式算法的設(shè)計過程，發(fā)現(xiàn)非關(guān)鍵任務(wù)的優(yōu)先級以及關(guān)鍵任務(wù)的開始時間會對最終結(jié)果產(chǎn)生較大的影響，而啟發(fā)式算法中并未對這兩項進(jìn)行更多可能性的嘗試.因此，本研究遺傳算法的上層算法中，對于決策項目非關(guān)鍵任務(wù)的優(yōu)先級和關(guān)鍵任務(wù)的開始時間，下層解碼算法采用第2節(jié)中提出的啟發(fā)式規(guī)則，決策各非關(guān)鍵任務(wù)的開始、結(jié)束時間，并以此方案的目標(biāo)函數(shù)值作為遺傳算法的適應(yīng)度值，返回到上層遺傳算法，再不斷復(fù)制、交叉、變異，通過循環(huán)迭代的方式，得到近似最優(yōu)解.

3.1 編碼

對于有J項任務(wù)的項目，假設(shè)其中關(guān)鍵任務(wù)數(shù)量為a，非關(guān)鍵任務(wù)數(shù)量為b，易得a+b=J.每組編碼的第一層對應(yīng)各非關(guān)鍵任務(wù)的調(diào)度優(yōu)先級列表，長度為b.若編碼第k位為j，則代表任務(wù)編號為j的任務(wù)調(diào)度優(yōu)先級為k.第二層對應(yīng)項目中各關(guān)鍵任務(wù)開始時間，長度為a，對于關(guān)鍵任務(wù)1假定開始時間為定值tST,1=1，后續(xù)關(guān)鍵任務(wù)開始時間在開始時間的可排區(qū)間點集內(nèi)隨機(jī)確定,如圖3所示.

圖3 編碼示例

3.2 遺傳操作

3.2.1初始種群

初始種群由兩部分組成：一是按照第2.1節(jié)中啟發(fā)式算法非關(guān)鍵任務(wù)的優(yōu)先級列表以及第2.2節(jié)中連續(xù)排入的關(guān)鍵任務(wù)作為一個初始解；二是在可行范圍內(nèi)隨機(jī)生成.

3.2.2選擇

運用隨機(jī)聯(lián)賽選擇算子，適應(yīng)值小的進(jìn)入下一代種群.適應(yīng)值函數(shù)為

(13)

3.2.3交叉

本研究采用單點交叉的方法.由于遺傳算法采用雙鏈表編碼模式，對非關(guān)鍵任務(wù)優(yōu)先級以及關(guān)鍵任務(wù)開始時間進(jìn)行編碼，交叉操作后可能出現(xiàn)不可能解，因此需要進(jìn)行額外操作消除不可行解.對于非關(guān)鍵任務(wù)鏈表需要消除交叉后可能出現(xiàn)的重復(fù)現(xiàn)象，對于關(guān)鍵任務(wù)開始時間鏈表需要保證交叉后的時間在該任務(wù)開始時間的可行范圍之內(nèi)，具體過程如圖4所示.

(1) 對非關(guān)鍵任務(wù)優(yōu)先級的鏈表進(jìn)行交叉操作.對染色體C2，選擇與染色體C1中x位置之前的基因不相同的基因鏈，與染色體C1中x位置之后的基因段互換，生成新的染色體Sg；對染色體C1，同理生成新的染色體D.

(2) 對關(guān)鍵任務(wù)開始時間的鏈表進(jìn)行交叉操作.對染色體C2，選擇與染色體C1中x位置之前的基因鏈，與染色體C1中x位置之后的基因段互換，若互換后的開始時間點處在區(qū)間[tES,tLS]內(nèi)，則直接互換；若互換后的開始時間點小于tES，則互換后的基因取值為tES；若互換后的開始時間點大于tLS，則互換后的基因取值為tLS；生成新的染色體Sg；對染色體C1，同理生成新的染色體D.

圖4 交叉操作示例

3.2.4變異

本研究采用基本位變異的方法，分以下兩步進(jìn)行:

(1) 對k=1,2,…,b，在[1,b]之間隨機(jī)產(chǎn)生兩個數(shù)x、y，交換x、y兩位置所對應(yīng)的任務(wù)的優(yōu)先級，生成新的列表.

(2) 對k=2,3,…,a，在[2,a]之間隨機(jī)產(chǎn)生一個數(shù)z，改變位置z所對應(yīng)任務(wù)的開始時間，并重新生成位置z后序所有關(guān)鍵任務(wù)的開始時間.具體過程如圖5所示.

圖5 變異操作示例

3.3 解碼

利用上述遺傳算法，得到了非關(guān)鍵任務(wù)優(yōu)先級列表以及關(guān)鍵任務(wù)的開始時間，接下來對所得到的染色體根據(jù)第2節(jié)中介紹的啟發(fā)式規(guī)則，進(jìn)行相應(yīng)鏈表的解碼操作.

4 數(shù)值實驗

實驗中所用測試算例基于測試問題庫PSPLIB中的算例進(jìn)行改造，對于未提供的參數(shù)，采用在一定大小范圍內(nèi)通過random函數(shù)隨機(jī)產(chǎn)生自然數(shù)的方式來確定，其中工期上限T取資源不受限下基于最早開始時間調(diào)度得到的任務(wù)最晚完成時間的1.2倍.空窗期數(shù)M=1，空窗期開始時間和結(jié)束時間隨機(jī)生成，長度不超過0.1T.遺傳算法設(shè)定的種群規(guī)模N=100，最大迭代次數(shù)λmax=50，交叉概率Pc=0.8，變異概率Pm=0.1.測試平臺為Intel Core i5處理器，2.20 GHz主頻，4.00G內(nèi)存.

表1～3顯示了小規(guī)模問題的算例結(jié)果，算例規(guī)模依次為10、20、30項任務(wù)；每組包含五個算例，C列、H列和G列分別表示CPLEX以及啟發(fā)式算法和遺傳算法在處理本組五個算例時得到的最好解的平均值取整.對于包含60和90項任務(wù)的大規(guī)模問題，啟發(fā)式算法和遺傳算法在求解速度上的差異較為明顯，而CPLEX在規(guī)定運算時間內(nèi)無法求得結(jié)果，故對于大規(guī)模問題分別對提出的兩種算法進(jìn)行求解精度和求解速度的比較.每個算例的空窗期約束在首次隨機(jī)生成后統(tǒng)一設(shè)定，保證比較的合理性.表4～5為大規(guī)模問題的算例結(jié)果，v列表示每組算例在相應(yīng)算法下各運行10次后得到的最小值的平均值，w列表示求得對應(yīng)結(jié)果的平均時間，單位為s.

表1～5中：

(14)

(15)

(16)

表1 10項任務(wù)實驗結(jié)果

表2 20項任務(wù)實驗結(jié)果

從表1～3中g(shù)1項和g2項可以發(fā)現(xiàn)，對任務(wù)數(shù)為10、20、30的小規(guī)模算例，所設(shè)計的啟發(fā)式算法與CPLEX求解得到的最優(yōu)解分別相差4.05%、6.12%、10.85%，遺傳算法求得的結(jié)果與CPLEX求得的最優(yōu)解分別相差1.57%、3.20%、6.73%.可以證實所提出的啟發(fā)式算法和遺傳算法在一定誤差范圍內(nèi)均能求解出較好的結(jié)果，遺傳算法求解精度更高；隨著算例規(guī)模的增大，啟發(fā)式算法在求解精度上的局限性越發(fā)明顯；小規(guī)模算例中啟發(fā)式算法與遺傳算法的g3值相差3%左右.

表3 30項任務(wù)實驗結(jié)果

表4 60項任務(wù)實驗結(jié)果

表5 90項任務(wù)實驗結(jié)果

對于任務(wù)數(shù)為60和90的大規(guī)模算例而言，通過表4、表5中的g3項結(jié)果可以看出，兩種算法的g3值分別為11.87%、13.57%，相差較大，雖無法與精確結(jié)果作比較，但可以說明求解大規(guī)模問題時，與啟發(fā)式算法相比，采用遺傳算法可以明顯提升求解精度.比較兩表中的w列結(jié)果發(fā)現(xiàn)，任務(wù)數(shù)為60時兩種算法的平均求解時間分別為29.54、48.89 s,任務(wù)數(shù)為90時兩種算法的平均求解時間分別為60.60、116.78 s，啟發(fā)式算法的求解速度更快.所設(shè)計的啟發(fā)式算法的時間復(fù)雜性為O(n2)，由于提出的遺傳算法在解碼和評估階段嵌套了相同的啟發(fā)式規(guī)則，隨著算例規(guī)模的增大，兩者在求解時間上的差異也隨之變大.對于大規(guī)模算例，遺傳算法與啟發(fā)式算法相比具有較高的精度，但求解速度較慢.由此表明，提出的兩種算法在不同的層面上具有不同的應(yīng)用價值.

5 總結(jié)與展望

針對飛機(jī)移動式裝配線上存在的關(guān)鍵資源帶有空窗期約束這一特性，提出以連續(xù)排入的兩個非關(guān)鍵任務(wù)間結(jié)果最優(yōu)的啟發(fā)式規(guī)則，分別設(shè)計了構(gòu)造啟發(fā)式算法和改進(jìn)遺傳算法求解帶資源空窗期的RIP，并通過數(shù)值實驗驗證了所提出算法的求解精度和求解速度在不同層面上的有效性.小規(guī)模算例中，兩種算法所得解與最優(yōu)解間的平均差值在11%以內(nèi)；大規(guī)模算例中，遺傳算法的求解精度較高，啟發(fā)式算法的求解速度較快.將飛機(jī)移動式裝配線抽象為項目調(diào)度資源投入問題的研究對于提升我國飛機(jī)制造業(yè)水平、帶動經(jīng)濟(jì)發(fā)展和科技進(jìn)步具有重要意義.