資源空窗期及任務(wù)可拆分的資源投入問題研究

陸志強(qiáng) 周皓雪

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

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

中圖分類號(hào)：F273 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)志碼：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

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

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

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

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

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

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

1.1? ?問題描述

假設(shè)項(xiàng)目由若干項(xiàng)任務(wù)構(gòu)成，記給定項(xiàng)目工期為T，項(xiàng)目中包含J項(xiàng)任務(wù)，任務(wù)執(zhí)行時(shí)間為dj，pre（j）為第j項(xiàng)任務(wù)的緊前任務(wù)構(gòu)成的集合，j*為任務(wù)j的緊前任務(wù)，suc（j）為其緊后任務(wù)構(gòu)成的集合. J項(xiàng)任務(wù)各有Mj（j∈J）種執(zhí)行模式，其中存在K項(xiàng)任務(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)鍵資源存在空窗期，部分時(shí)刻不可用，普通資源在任意時(shí)刻皆可使用;Wp為資源在項(xiàng)目周期T內(nèi)的可用時(shí)間窗集，普通資源滿足Wp = [1，T]，引入?yún)⒘縕pt，表示資源p在t時(shí)刻是否可用，若t∈Wp，則Zpt = 1，否則Zpt = 0. 任務(wù)間存在著一定的時(shí)序關(guān)系，當(dāng)滿足緊前任務(wù)皆完成調(diào)度且所需資源充足的情況下，任務(wù)即可開始執(zhí)行. 將時(shí)間進(jìn)行離散處理，各任務(wù)在時(shí)刻t對(duì)資源p的總需求量用Rtp表示. 最小化各時(shí)刻t（t = 1，2，…，T）每種資源p的最大需求量Rtp的總成本之和是模型的優(yōu)化目標(biāo).

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

2? ?算法設(shè)計(jì)

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

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

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

2.2? ?實(shí)數(shù)交叉

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

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

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

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

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

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

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

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

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

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

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

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

情形2：nk > Mg1，k?Ba

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

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

2.4.2? ?算法步驟

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

3? ?數(shù)值實(shí)驗(yàn)

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

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

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

3.2? ?數(shù)值實(shí)驗(yàn)分析

3.2.1? ?算法對(duì)比

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

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

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

3.2.3? ?討論與分析

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

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

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

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

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

4? ?結(jié)? ?論

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

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

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

參考文獻(xiàn)

[1]? ? 王琰，陸志強(qiáng). 基于多重約束的飛機(jī)移動(dòng)裝配線作業(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]? ? 宗保氏，陸志強(qiáng). 項(xiàng)目拆分與資源投入調(diào)度問題的集成優(yōu)化[J]. 上海交通大學(xué)學(xué)報(bào)，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]? 任逸飛，陸志強(qiáng).多技能資源投入項(xiàng)目調(diào)度問題的建模與優(yōu)化[J]. 同濟(jì)大學(xué)學(xué)報(bào)（自然科學(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]? 廖廣瑞，劉振元，畢陽. 多技能資源時(shí)間窗約束下項(xiàng)目調(diào)度研究[C]// 第26屆中國控制與決策會(huì)議論文集. 長沙：控制與決策，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]? 綦方中，胡丹，葉雷宏. 基于時(shí)間窗和關(guān)鍵鏈的多項(xiàng)目資源分配問題的研究[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]? 陸志強(qiáng)，石婷.作業(yè)任務(wù)可拆分的資源投入問題的建模與優(yōu)化[J]. 計(jì)算機(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í)數(shù)遺傳算法交叉策略的改進(jìn)[J]. 電子學(xué)報(bào)，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）