陸志強 周皓雪

摘? ?要：考慮飛機裝配過程中任務(wù)可拆分及資源存在空窗期的兩大特性，對飛機移動生產(chǎn)線資源投入問題進行模型與算法研究. 針對部分任務(wù)存在已知拆分模式及拆分懲罰的情形，設(shè)計了求解該問題的改進遺傳算法，對傳統(tǒng)實數(shù)交叉操作進行優(yōu)化，提出了基于染色體適應(yīng)值的交叉方法，并在數(shù)值實驗中對相關(guān)參數(shù)的取值范圍進行了敏感性分析;同時，提出了基于任務(wù)開始時間選擇概率的變異機制. 對滿足優(yōu)化條件的任務(wù)調(diào)度方案，結(jié)合空窗期的位置，評判各可拆分任務(wù)可否通過選取新的拆分模式重新調(diào)度執(zhí)行，對不同情形進行總結(jié)歸納，通過局部操作進一步降低目標資源量. 數(shù)值實驗表明：通過本文算法對求解帶資源空窗期的任務(wù)不可拆分問題與基本問題的結(jié)果對比，得到任務(wù)數(shù)分別為10、16、30、60、90算例的目標值平均增量達到4.3%;對求解本文問題與任務(wù)不可拆分問題的結(jié)果對比，平均優(yōu)化率達3.5%，證明了本文算法的有效性，同時證明將任務(wù)拆分納入考慮資源空窗期的資源投入問題中，可提高問題求解的靈活性，從而獲得較好的調(diào)度結(jié)果.

關(guān)鍵詞：資源投入問題;資源空窗期;任務(wù)拆分;遺傳算法

中圖分類號：F273 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標志碼：A

Abstract：Considering the two characteristics of activity splitting and resource window in the process of aircraft assembly，the model and algorithm of Resource Investment Problem on aircraft mobile production line were studied. Aiming at the situation that some activities have known splitting mode and splitting punishment，an improved genetic algorithm for solving this problem was designed. The traditional real value crossover operation was optimized，and a crossover method based on chromosome fitness value was proposed. Sensitivity analysis was carried out on the range of values of the relevant parameters. A mutation mechanism based on the probability of selection of activity start time was also proposed. For a scheduling scheme that satisfies the optimization conditions，combined with the position of the resource window，after judging whether the splitting activities can be re-scheduled and executed by selecting a new splitting mode and summarizing the different situations，the target resources were further reduced by local operations. The numerical experiments show that，compared with the results of solving the problem of non-split activities with resource window and the basic problem，the average value of the target for the 10，16，30，60，90 activities is 4.3%. For the comparison between the results of solving this problem and the non-split problem，the average optimization rate is 3.5%，which proves the effectiveness of the algorithm. At the same time，it is proved that the activity splitting is included in the Resource Investment Problem considering the resource window，which can improve the flexibility of problem solving and obtain better scheduling results.

Key words：resource investment problem;resource window;activity splitting;genetic algorithm

目前，我國的飛機總裝大部分仍沿用傳統(tǒng)的固定站位式裝配模式，批量生產(chǎn)能力匱乏. 隨著社會經(jīng)濟的發(fā)展，民用機的需求激增，在航空制造中深入推行基于精益思想的飛機移動式裝配線模式，可提高裝配效率和質(zhì)量，按需批量生產(chǎn)是中國飛機制造向世界水平邁進的必經(jīng)之路. 裝配線上單架飛機的總裝調(diào)度決策問題依據(jù)不同的生產(chǎn)目的，可將其抽象地分為資源受限項目調(diào)度問題[1]（Resource-Constrained Project Scheduling Problem，RCPSP）和資源投入型問題[2]（Resource Investment Problem，RIP）. 后者即在給定的制造期限約束下，優(yōu)化配置完成項目所需的線邊裝配人員、工裝、工具及儀器設(shè)備等各類資源，達到最小化資源投入總成本的目的.

資源投入問題最早由Morhing[3]在一個橋梁建設(shè)項目中提出，其證明了此問題為NP-hard，提出了求解該問題的圖解精確算法;Drexl等[4]基于拉格朗日松弛和列生成方法針對RIP提出了兩個下界算法，并且通過算例實驗與Morhing[3]提出的算法進行了比較;Demeulemeester[5]參照針對RCPSP問題提出的基于深度優(yōu)先的分支定界方法，構(gòu)建了求解RIP的優(yōu)化算法. 上述精確算法雖然求解精度較好，但是只能應(yīng)用于小規(guī)模問題，對于諸如飛機生產(chǎn)制造的大規(guī)模問題，大量國內(nèi)外學(xué)者提出啟發(fā)式算法與元啟發(fā)式算法進行求解. Zhu等[6]將RIP問題的求解劃分為排序問題與資源決策問題兩個部分，提出了一種多起點迭代搜索的啟發(fā)式方法;Song等[7]利用帶有局部搜索的進化算法求解，在優(yōu)化過程中不允許項目延遲;Qi等[8]提出了改進的粒子群優(yōu)化算法求解多模式下資源可用性成本問題的調(diào)度生成方案;Javanmard等[9]設(shè)計了一種基于遺傳和粒子群的算法，通過校準參數(shù)和染色體結(jié)構(gòu)，保證解的可行性;任逸飛等[10]通過基于全局資源水平影響的任務(wù)調(diào)度評估策略，提出改進型遺傳算法優(yōu)化非關(guān)鍵任務(wù)的調(diào)度位置，然而該評估策略在求解大規(guī)模算例時效率較低.

上述文獻均為對基本RIP的研究，存在大量的假設(shè)，模型偏理想化，對工況條件復(fù)雜的飛機總裝過程缺乏指導(dǎo)意義;從算法設(shè)計上來看，多數(shù)算法局限于將RIP轉(zhuǎn)化成RCPSP的求解思路，導(dǎo)致某些資源組合可能超出工期約束，針對資源的搜索方向性較差，求解效率低. 現(xiàn)代化的飛機生產(chǎn)制造工序繁瑣，技術(shù)復(fù)雜性高，總裝過程需要大量不同的專業(yè)性人才. 因此，在實際生產(chǎn)過程中往往會存在由于關(guān)鍵技術(shù)人員緊缺而必須延遲調(diào)度的情形，將資源存在的不可用時間段稱為資源空窗期. 將資源空窗期約束引入到RIP模型構(gòu)建中，更加貼合飛機移動式裝配線應(yīng)用背景. 現(xiàn)有文獻中僅考慮資源空窗期的RCPSP，考慮資源特點的RIP研究很少. 廖廣瑞等[11]針對資源的多技能和時間窗屬性，設(shè)計了一種基于優(yōu)先規(guī)則的Rollout求解算法，并嵌入了一種啟發(fā)式資源分配方法對資源進行快速分配;Jirachai等[12]研究了考慮資源空窗期的多模式RCPSP問題，假定任務(wù)可拆分執(zhí)行，設(shè)計了求解小規(guī)模該類問題的分支定界算法;綦方中等[13]研究了基于時間窗的多項目資源分配問題，提出了增加時間窗參數(shù)以及懲罰因子的多項目管理資源分配模型. 總結(jié)上述研究可以發(fā)現(xiàn)，空窗期的引入會導(dǎo)致任務(wù)調(diào)度的靈活性下降，從而加劇空窗期前后位置的資源投入量，增加項目的成本支出.

另一方面，現(xiàn)有RIP問題的研究通常假設(shè)任務(wù)不可拆分，但從飛機裝配工藝過程中可以發(fā)現(xiàn)，某些任務(wù)過程并不是連續(xù)的，是可以拆分執(zhí)行的. 從Javanmard等[9]和陸志強等[14]對于任務(wù)可拆分條件下RIP的研究中可以看出，考慮任務(wù)可拆分特性能增加任務(wù)調(diào)度的柔性，均衡資源使用，降低成本投入. 而在以上文獻中，雖然考慮了任務(wù)可拆分執(zhí)行的情形，卻并未設(shè)置相應(yīng)的拆分懲罰機制. 在飛機實際裝配生產(chǎn)中，某項任務(wù)在執(zhí)行過程中中斷，待到后續(xù)某時刻繼續(xù)執(zhí)行時，需要重新進行裝配準備工作，勢必造成時間成本或資源成本的增加.

綜上所述，本文將任務(wù)拆分及伴有拆分懲罰的情形納入考慮資源空窗期的資源投入問題中，構(gòu)建符合實際應(yīng)用條件的模型，重點分析同時考慮任務(wù)可拆分及資源存在空窗期這兩大特性的交互影響，設(shè)計相應(yīng)的改進型遺傳算法及優(yōu)化操作進行求解和驗證. 最后通過實例分析，以某型號支線客機駕駛艙裝配工位的調(diào)度為例，驗證了本文算法的有效性.

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

1.1? ?問題描述

假設(shè)項目由若干項任務(wù)構(gòu)成，記給定項目工期為T，項目中包含J項任務(wù)，任務(wù)執(zhí)行時間為dj，pre（j）為第j項任務(wù)的緊前任務(wù)構(gòu)成的集合，j*為任務(wù)j的緊前任務(wù)，suc（j）為其緊后任務(wù)構(gòu)成的集合. J項任務(wù)各有Mj（j∈J）種執(zhí)行模式，其中存在K項任務(wù)，構(gòu)成集合U，滿足Mk>1（k∈K），存在拆分執(zhí)行模式，其余任務(wù)滿足Mj = 1（j∈J，j?K），不能拆分執(zhí)行. r1

全部任務(wù)共享P種可更新資源，每種資源的單位使用成本為Cp（p∈P）. 其中資源分關(guān)鍵資源和普通資源，關(guān)鍵資源存在空窗期，部分時刻不可用，普通資源在任意時刻皆可使用;Wp為資源在項目周期T內(nèi)的可用時間窗集，普通資源滿足Wp = [1，T]，引入?yún)⒘縕pt，表示資源p在t時刻是否可用，若t∈Wp，則Zpt = 1，否則Zpt = 0. 任務(wù)間存在著一定的時序關(guān)系，當滿足緊前任務(wù)皆完成調(diào)度且所需資源充足的情況下，任務(wù)即可開始執(zhí)行. 將時間進行離散處理，各任務(wù)在時刻t對資源p的總需求量用Rtp表示. 最小化各時刻t（t = 1，2，…，T）每種資源p的最大需求量Rtp的總成本之和是模型的優(yōu)化目標.

式（1）為目標函數(shù)，表示該問題是優(yōu)化整個周期內(nèi)各資源使用的最大總成本;式（2）為約束條件，表示任務(wù)只能選擇一種執(zhí)行模式;式（3）表示任務(wù)在整個項目工期內(nèi)的執(zhí)行時間之和必須滿足該任務(wù)工期約束;式（4）計算了各時間段t內(nèi)每種資源p的使用量;式（5）表示任務(wù)只有在所需資源皆可用時才能執(zhí)行;任務(wù)之間需滿足時序約束（式（6）），即滿足一定的優(yōu)先關(guān)系;式（7）表示所有任務(wù)的最晚結(jié)束時間不應(yīng)大于項目給定工期;式（8）定義了決策變量xjmt與yjm的可行域.

2? ?算法設(shè)計

本文采用直接確定任務(wù)位置來獲得任務(wù)調(diào)度計劃及資源使用情況的算法設(shè)計思路，通過確定任務(wù)開始時間的方式來間接獲得項目中的資源投入量，針對可拆分任務(wù)，將其結(jié)束時間也在編碼中體現(xiàn). 以遺傳算法為搜索框架，設(shè)計基于染色體適應(yīng)值的實數(shù)交叉方式及基于任務(wù)開始時間選擇概率的變異方式進行遺傳操作，在解碼過程中針對各染色體調(diào)度計劃，結(jié)合資源空窗期與可拆分任務(wù)的拆分模式，進行拆分任務(wù)的模型更換，進一步降低項目資源投入量，優(yōu)化目標資源成本.

2.1? ?基于任務(wù)開始時間的編碼

本文在可行范圍內(nèi)，采用對任務(wù)開始時間進行編碼的方式，直觀展現(xiàn)各任務(wù)調(diào)度位置;為體現(xiàn)拆分任務(wù)的拆分與否，同時對可拆分任務(wù)的結(jié)束時間進行編碼. 當項目中存在J項任務(wù)和M項可拆分任務(wù)時，編碼的長度為J + M，其中編碼第1到J位表示任務(wù) j的開始時間;編碼第J + 1到J + M位表示第m個可拆分任務(wù)的結(jié)束時間. 以圖1所示算例為例，編碼第8位表示可拆分任務(wù)3的結(jié)束時間為時刻3，故可知該任務(wù)選擇的是連續(xù)執(zhí)行的模式.

2.2? ?實數(shù)交叉

經(jīng)過輪盤賭選擇機制獲得的種群，根據(jù)交叉概率Pc選擇需要進行交叉操作的染色體組成集合C，Pc由式（9）求得，其中，Pc1、Pc2為預(yù)先定義的參數(shù)，favg、 fmin分別為所有染色體的平均適應(yīng)度值和最小適應(yīng)度值.

為提高染色體交叉后的多樣性，本文結(jié)合文獻[15]設(shè)計了一種新的基于染色體適應(yīng)值的交叉方式. 不同父體之間適應(yīng)值的差異不僅對繁殖過程有所裨益，而且可能會為生成更優(yōu)異的后代提供潛在的搜索方向. 定義搜索方向v為：

式中：fitnessh和fitnessl分別表示父代中適應(yīng)值較大和較小的染色體.染色體i的適應(yīng)值fitnessi通過式（11）求得，Oi為該染色體編碼對應(yīng)的資源使用量，LB為項目最低資源用量，通過式（12）求取，其中rjp表示任務(wù)需要的單位資源的數(shù)量.

2.3? ?基于任務(wù)開始時間選擇概率的變異

經(jīng)過交叉之后得到的染色體，根據(jù)變異概率Pm選擇需要進行變異操作的染色體組成集合M，Pm同樣通過式（9）求得.

由于項目存在工期上限，因此各任務(wù)j的開始時間Sj存在決策區(qū)間[ESj，LSj]. 各任務(wù)不同開始時間的組合對應(yīng)不同項目目標資源量，隨著遺傳算法不斷迭代搜索，較低的目標值被發(fā)現(xiàn)的同時，所得調(diào)度計劃中的任務(wù)開始時間也趨向于更小的決策區(qū)間[ES′j，LS′j]，甚至趨向于某一精確值. 定義任務(wù)開始時間選擇概率P′S（ES≤S≤LS）和該開始時間下需要多投入的資源量R′S. 在初始種群中，令R′S = 1. 之后的每條染色體都根據(jù)當代的資源用量R更新R′S為：

2.4? ?局部優(yōu)化操作

當部分任務(wù)存在可拆分執(zhí)行模式，且該模式下某一拆分子任務(wù)的執(zhí)行過程中無需使用存在空窗期的資源時，可考慮通過調(diào)整可拆分任務(wù)的執(zhí)行模式及其余部分任務(wù)的執(zhí)行位置，降低相應(yīng)資源的占用量.

2.4.1? ?可拆分任務(wù)優(yōu)化調(diào)整

針對空窗期位置及任務(wù)拆分模式等信息，當資源g滿足g≠k，最大使用量出現(xiàn)的時刻Hg = 1，tsj≤Mg1≤tfj時，以下兩種情形通過更換可拆分任務(wù)的拆分模式來降低資源g的投入量. 記對應(yīng)染色體下各資源p（p∈P）的最大使用量和最大使用量出現(xiàn)的時刻分別為Vp、Mph（h = 1，…，Hp）（可能存在多個位置資源用量相同），資源k（k∈P）存在空窗期[mk，nk]，可拆分任務(wù)j（j∈J）在該調(diào)度計劃下的執(zhí)行時刻為[tsj， ffj]，可選拆分模式下前后兩段所用資源種類分別為集合Baj和Bbj.

情形1：mk > Mg1，k?Bbj，區(qū)間[Mg1，nk]屬于任務(wù)j的浮動區(qū)間. 資源k的空窗期位于最大資源時刻之后，任務(wù)j可以在區(qū)間[Mg1，nk]內(nèi)任意時刻開始執(zhí)行，且其拆分模式后半段無需使用資源k，該情形下可通過更換任務(wù)j為拆分模式執(zhí)行，重調(diào)度區(qū)間[Mg1，nk]內(nèi)的任務(wù)，降低資源k的Vk值.

仍以圖1（a）所示項目網(wǎng)絡(luò)圖為例，假設(shè)資源2存在空窗期[5，6]，任務(wù)3為可拆分任務(wù)，拆分模式為2/2/2和1/2/0，拆分任務(wù)的懲罰時間成本為θ = 1. 對應(yīng)染色體編碼下初始調(diào)度結(jié)果如圖2（a）所示，其中縱坐標R代表資源總用量，R1和R2為每個任務(wù)執(zhí)行時所消耗的兩種資源量，橫坐標表示時間. 時刻6內(nèi)無可執(zhí)行任務(wù)，資源1和資源2的最大資源用量時刻皆為時刻1，資源用量分別為7和6. 鑒于可拆分任務(wù)3滿足情形1，選取拆分模式執(zhí)行后，將任務(wù)2的開始時間提前一個單位，任務(wù)3分別在時間段[0，2]、[4，6]內(nèi)執(zhí)行，資源1的用量V1降低了2個單位，調(diào)度結(jié)果如圖2（b）所示.

情形2：nk > Mg1，k?Ba

j，區(qū)間[mk，Mg1]屬于任務(wù)j的浮動區(qū)間. 資源k的空窗期位于最大資源時刻之前，任務(wù)j可以在區(qū)間[mk，Mg1]內(nèi)任意時刻開始執(zhí)行，且其拆分模式前半段無需使用資源k，該情形下可通過更換任務(wù)j為拆分模式執(zhí)行，重調(diào)度區(qū)間[mk，Mg1]內(nèi)的任務(wù)，降低資源k的Vk值.

以圖1（a）所示項目網(wǎng)絡(luò)圖為例，假設(shè)資源2存在空窗期[0，1]，任務(wù)3為可拆分任務(wù)，拆分模式分別為2/2/0和1/2/2，拆分任務(wù)的懲罰時間成本為θ = 1. 對應(yīng)染色體編碼下初始調(diào)度結(jié)果如圖3（a）所示，時刻1內(nèi)無可執(zhí)行任務(wù)，資源1和資源2的最大資源用量時刻皆為時刻1，資源用量分別為7和6. 鑒于可拆分任務(wù)3滿足情形2，選取拆分模式執(zhí)行后，將任務(wù)2的開始時間提前兩個單位，任務(wù)3分別在時間段[0，2]、[4，6]內(nèi)執(zhí)行，資源1的用量V1降低了2個單位，同時資源2的用量V2降低了1個單位，調(diào)度結(jié)果如圖3（b）所示.

2.4.2? ?算法步驟

步驟1? ?對染色體F進行解碼操作，得到各資源 p（p∈P）的最大使用量和最大使用量出現(xiàn)的時刻Vp、Mph（h=1，…，Hp）及項目資源水平X，記資源k（k∈P）的空窗期為[mk，nk]，可拆分任務(wù)j（j∈J）的執(zhí)行時刻為[Sj，F(xiàn)j]，可選拆分模式下前后兩段工期分別為daj和dbj. 令p = 1，轉(zhuǎn)步驟2.

3? ?數(shù)值實驗

為驗證上述改進遺傳算法對于求解考慮資源空窗期及任務(wù)可拆分特性下的資源投入問題的有效性，本文運用C#（Visual Studio 2013）編程實現(xiàn)該算法. 測試平臺為Intel Core i5處理器，2.40 GHz主頻，8 G內(nèi)存. 通過對PSPLIB中的算例進行改造，獲得了本文所用的測試算例，對于實驗所需而基本算例中未提供的參數(shù)，通過隨機數(shù)的方式來確定，其中工期上限T取關(guān)鍵路徑長的1.2倍，資源空窗期通過在項目工期內(nèi)隨機產(chǎn)生不同長度的區(qū)間獲得. 基于不同規(guī)模的算例，對小規(guī)模算例選擇2項任務(wù)作為可拆分任務(wù)，生成拆分模式下的執(zhí)行時間及資源需求;對中大規(guī)模算例選擇5項任務(wù)作為可拆分任務(wù). 設(shè)定任務(wù)拆分的懲罰時間為θ = 1，即可拆分任務(wù)的后半段執(zhí)行時間延長一個單位.

3.1? ?算法參數(shù)分析

本文遺傳算法設(shè)計中交叉操作部分基于傳統(tǒng)實數(shù)交叉方法進行了改進，設(shè)計了新的基于染色體適應(yīng)值的交叉方式，采用參數(shù)α1、α2控制所生成染色體的方向. 選取標準算例庫PSPLIB中包含J30、J60和J90共3種規(guī)模算例的任務(wù)對α1、α2進行敏感性分析，平均gap表示所有規(guī)模下不同算例誤差百分比的均值. 圖5為參數(shù)α1、α2的敏感性分析結(jié)果，分別比較取值范圍為[0，1]和[1，2]下各算例的計算結(jié)果. 遺傳算法設(shè)定的種群規(guī)模N=100.

3.2? ?數(shù)值實驗分析

3.2.1? ?算法對比

為了驗證本文所提出的改進型遺傳算法的有效性，選取任務(wù)數(shù)分別為10、30、60的各10個算例為樣本，與粒子群算法求解的結(jié)果進行對比，求解時間統(tǒng)一設(shè)定為60 s，結(jié)果如圖6所示，GA為遺傳算法求解結(jié)果，PSO為粒子群算法求解結(jié)果.從圖6可以看出，雖然兩種算法結(jié)果相近，但是遺傳算法結(jié)果更優(yōu)，說明本文所提出的改進型遺傳算法具有優(yōu)越性.

3.2.2? ?數(shù)值結(jié)果

選取任務(wù)數(shù)分別為10、16、30、60、90的各50個算例為樣本進行數(shù)值實驗分析，結(jié)果如表1～表5所示. GA及GA·NP分別代表每組為5個算例下本文算法和本文算法在考慮任務(wù)不可拆分情形下求得的目標值的均值;gap1為這兩列值間的差異，用以體現(xiàn)任務(wù)拆分的意義. 由于當不考慮空窗期時本文中對于任務(wù)拆分的設(shè)定條件無任何意義，故GA·N表示本文算法考慮任務(wù)不可拆分及資源無空窗期情形下求得的目標值，gap2為GA·NP與GA·N值間的差異，用以體現(xiàn)空窗期對任務(wù)調(diào)度的影響.v表示每組為5個算例下每種算法求得的目標值的均值，t表示求解時間的均值，單位為s.

3.2.3? ?討論與分析

從表6可以看出，本文針對求解考慮資源空窗期及任務(wù)可拆分條件下的資源投入問題所設(shè)計的遺傳算法，能在較短時間內(nèi)求得較優(yōu)解. 對比本文算法改進下的求解任務(wù)不可拆分問題的結(jié)果與基本資源投入問題的結(jié)果，平均增量達4.3%;對比本文算法與改進下的求解任務(wù)不可拆分問題的結(jié)果，平均優(yōu)化比率達3.5%. 結(jié)果表明本文提出的改進型遺傳算法在求解中具有優(yōu)越性.

從模型角度來看，在飛機實際裝配過程中，空窗期約束的存在是客觀事實，同時現(xiàn)實中部分任務(wù)可以被拆分執(zhí)行;由于文中對任務(wù)拆分的模式假定是針對空窗期所設(shè)計，可選模式的執(zhí)行方案也是根據(jù)空窗期進行設(shè)置，故能在一定程度上提高問題調(diào)度的柔性，從而獲得更加貼合實際的調(diào)度方案.

3.3? ?實例應(yīng)用分析

以某型號支線客機駕駛艙裝配工位的調(diào)度為例對算法進行驗證. 該工位共包含14項裝配任務(wù)，任務(wù)間的時序約束關(guān)系、工期及所需資源量如表7所示，任務(wù)1與任務(wù)14表示虛任務(wù)，任務(wù)7及任務(wù)13為可拆分任務(wù)，存在拆分執(zhí)行模式. 主要考慮關(guān)鍵人力資源R1、關(guān)鍵設(shè)備資源R2、物料配送能力R3和線邊空間存儲能力R4共4類對飛機生產(chǎn)過程影響較大的資源類型，已知關(guān)鍵人力資源R1存在空窗期[4，6].

圖7和圖8中，橫軸表示時間，由于項目的執(zhí)行需要4種資源，無法用一張圖表明各資源使用量，所以縱坐標不代表任何參量. 圖示兩種方法求得實例的資源成本均為59，說明本文算法在此實例下能夠求得最優(yōu)解.

4? ?結(jié)? ?論

本文以飛機移動式裝配線為背景，在研究基本資源投入問題的基礎(chǔ)上，同時考慮任務(wù)可拆分及資源存在空窗期兩大特性，設(shè)計了改進型遺傳算法進行求解，結(jié)果表明：

1）考慮空窗期下的問題調(diào)度缺乏靈活性，調(diào)度結(jié)果所用資源成本相對較高;將任務(wù)拆分納入考慮資源空窗期的資源投入問題中，能通過任務(wù)拆分調(diào)度的靈活性降低空窗期對問題調(diào)度帶來的不良影響，利用對任務(wù)不同調(diào)度位置的決策，合理配置現(xiàn)有資源的使用，從而獲得相對較好的調(diào)度結(jié)果.

2）本文算法在求解效率及求解精度上表現(xiàn)良好，且能用于求解大規(guī)模算例.

參考文獻

[1]? ? 王琰，陸志強. 基于多重約束的飛機移動裝配線作業(yè)任務(wù)調(diào)度優(yōu)化[J]. 工業(yè)工程與管理，2011，16（6）：115-120.WANG Y，LU Z Q. Job scheduling optimization of aircraft moving assembly line under multiple constraints[J]. Industrial Engineering and Management，2011，16（6）：115-120.（In Chinese）

[2]? ? 宗保氏，陸志強. 項目拆分與資源投入調(diào)度問題的集成優(yōu)化[J]. 上海交通大學(xué)學(xué)報，2018，52（7）：793-800.ZONG B S，LU Z Q. Integrated optimization of project splitting and resource investment project scheduling[J]. Journal of Shanghai Jiaotong University，2018，52（7）：793—800. （In Chinese）

[3]? ? MORHING R H. Minimizing costs of resource requirements in project networks subject to a fixed completion time[J]. Operations Research，1984，32（1）：89—120.

[4]? ? DREXL A，KIMMS A. Optimization guided lower and upper bounds for the resource investment problem[J]. Operational Research Society，2001，52（3）：340—351.

[5]? ? DEMEULEMEESTER E L. Minimizing resource availability costs in time-limited project networks[J]. Operations Research and the Management Science，1995，41（10）：1590—1598.

[6]? ? ZHU X，RUIZ R，LI S Y，et al. An effective heuristic for project scheduling with resource availability cost[J]. European Journal of Operational Research，2016，257 （3）：746—762.

[7]? ? SONG Y，LIU J，WIMMERS M O，et al. A differential evolution algorithm with local search for resource investment project scheduling problems[C]//Evolutionary Computation. Sendai：IEEE，2015：1725—1731.

[8]? ? QI J J，LIU Y J，JIANG P，et al. Schedule generation scheme for solving multi-mode resource availability cost problem by modified particle swarm optimization[J]. Journal of Scheduling，2015，18（3）：285.

[9]? ? JAVANMARD S，AFSHAR-NADJAFI B，NIAKI S T A. Preemptive multi-skilled resource investment project scheduling problem：Mathematical modelling and solution approaches[J]. Computers & Chemical Engineering，2017，96（4）：55—68.

[10]? 任逸飛，陸志強.多技能資源投入項目調(diào)度問題的建模與優(yōu)化[J]. 同濟大學(xué)學(xué)報（自然科學(xué)版），2017，45（11）：1713—1721.REN Y F，LU Z Q. Modeling and optimization of resource investment project scheduling problem with multi-skill[J]. Journal of Tongji University（Natural Science），2017，45（11）：1713—1721.（In Chinese）

[11]? 廖廣瑞，劉振元，畢陽. 多技能資源時間窗約束下項目調(diào)度研究[C]// 第26屆中國控制與決策會議論文集. 長沙：控制與決策，2014：4885—4891.LIAO G R，LIU Z Y，BI Y. Project Scheduling with Time Window Constraints on Multi-Skill Resources[C]// 26th Chinese Control and Decision Conference （CCDC）. Changsha：Control and Decision，2014：4885—4891. （In Chinese）

[12]? JIRACHAI B，DAVID S K. Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting[J]. European Journal of Operational Research，2006，175（1）：279—295.

[13]? 綦方中，胡丹，葉雷宏. 基于時間窗和關(guān)鍵鏈的多項目資源分配問題的研究[J]. 科技管理研究，2013，33（13）：229—232.QI F Z，HU D，YE L H. Study on resource allocation of multi-project based on time window and critical chain[J]. Science and Technology Management Research，2013，33（13）：229—232. （In Chinese）

[14]? 陸志強，石婷.作業(yè)任務(wù)可拆分的資源投入問題的建模與優(yōu)化[J]. 計算機集成制造系統(tǒng)，2018，24（3）：602—611.LU Z Q，SHI T. Modeling and optimization of resource investment problem with activity splitting[J]. Computer Integrated Manufacturing System，2018，24（3）：602—611. （In Chinese）

[15]? 陳小平，于盛林. 實數(shù)遺傳算法交叉策略的改進[J]. 電子學(xué)報，2003，31（1）：71—74.CHEN X P，YU S L. Improvement on crossover strategy of real-valued genetic algorithm[J]. Acta Electronica Sinica，2003，31（1）：71—74.（In Chinese）