考慮資源空窗期的資源投入問題的建模與優(yōu)化

陸志強(qiáng)，石 婷

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

飛機(jī)制造對于促進(jìn)科技實(shí)力進(jìn)步、帶動(dòng)國民經(jīng)濟(jì)發(fā)展和提升國家綜合實(shí)力有著重要的意義.飛機(jī)的移動(dòng)裝配過程復(fù)雜，裝配工序繁多，傳統(tǒng)的經(jīng)驗(yàn)式調(diào)度安排往往導(dǎo)致線邊資源的極大浪費(fèi).因此，研究飛機(jī)移動(dòng)裝配相關(guān)基礎(chǔ)問題的建模與科學(xué)決策，可以優(yōu)化各裝配任務(wù)的作業(yè)時(shí)間，有效降低裝配過程的成本.事實(shí)上，裝配線上任何單架飛機(jī)總裝過程調(diào)度決策的基礎(chǔ)問題都可看作是一個(gè)資源受限項(xiàng)目調(diào)度問題(RCPSP)，各裝配作業(yè)任務(wù)可認(rèn)為是完成這個(gè)項(xiàng)目的活動(dòng)，完成各裝配作業(yè)任務(wù)所需的線邊裝配人員、工裝、工具及儀器設(shè)備等可視為是完成項(xiàng)目所需的各類資源.資源投入問題作為該問題的對偶問題，其決策是以預(yù)定的工期期限作為約束來控制的，旨在獲得較低的資源投入成本.該問題最早由M?rhing[1]提出，證明了此問題為NP-hard問題，并以求解RCPSP問題的算法為基礎(chǔ)，設(shè)計(jì)了求解該問題的圖解精確算法.Demeulemeester[2]同樣參照對RCPSP問題的研究，將他與Herroelen[3]共同提出的基于深度優(yōu)先的求解RCPSP問題的分支定界算法進(jìn)行了改進(jìn)，構(gòu)建了求解資源投入問題(RIP)的優(yōu)化算法.由于精確算法在求解該類問題時(shí)效率差，無法有效處理大規(guī)模問題，因此學(xué)者們相繼設(shè)計(jì)了相關(guān)元啟發(fā)式算法.Yamashita等[4]最早提出求解該問題的元啟發(fā)式算法，將Multi-Start啟發(fā)式算法和分散搜索(Scatter Search)過程相結(jié)合，用以修復(fù)不可行解并通過路徑重連提高解的質(zhì)量.Najafi等[5]提出了以各作業(yè)浮動(dòng)時(shí)間為編碼方式的遺傳算法，在解碼階段設(shè)計(jì)了2種局部優(yōu)化操作.Van等[6]設(shè)計(jì)了求解該問題的人工免疫算法，為避免早熟對資源列表及變異操作進(jìn)行了改進(jìn).吳怡薇等[7]以遺傳算法為框架，提出非關(guān)鍵任務(wù)調(diào)度優(yōu)先級規(guī)則，利用區(qū)間細(xì)分、全局影響評估任務(wù)可排區(qū)間.Zhu等[8]將RIP問題拆分成排序和資源決策兩類子問題，通過設(shè)計(jì)鄰域搜索、路徑重連及2種啟發(fā)式算法來求解相應(yīng)的子問題，并通過算例實(shí)驗(yàn)驗(yàn)證了算法的有效性.

現(xiàn)有文獻(xiàn)中對于RIP問題的研究都以研究RCPSP問題的算法為框架，主要存在2點(diǎn)不足：① RCPSP本身也是NP-hard問題，對于某一資源水平，無法準(zhǔn)確判斷該資源下調(diào)度結(jié)果能否滿足RIP的工期限制；② 在資源投入調(diào)度方面，對資源組合的搜索方向性不強(qiáng)，不能充分利用迭代過程中的信息使算法向最優(yōu)解方向收斂，同時(shí)也導(dǎo)致算法效率低.因此，本文在算法設(shè)計(jì)中首先通過搜索算法直接確定各作業(yè)開始時(shí)間來間接獲得項(xiàng)目資源投入量，避免了對資源大范圍低效率的搜索；其次，根據(jù)迭代過程中的信息，對遺傳算法變異操作進(jìn)行改進(jìn)，提出基于概率分布的作業(yè)開始時(shí)間選擇方法，不斷優(yōu)化資源使用量，為進(jìn)一步降低所得目標(biāo)值，設(shè)計(jì)分支定界算法用以優(yōu)化部分作業(yè)的開始時(shí)間.

另一方面，裝配線上任何一架飛機(jī)裝配的總周期時(shí)間一般都很長，線上資源特別是關(guān)鍵人力資源通常需要在同架飛機(jī)(同一項(xiàng)目)和線上不同架飛機(jī)(不同項(xiàng)目)的作業(yè)任務(wù)之間共享，因此，往往會(huì)存在因所需資源緊缺而必須延遲調(diào)度的情形，本文將資源存在的不可用時(shí)間段稱為資源空窗期.胡淑芳[9]考慮資源時(shí)間窗和作業(yè)可拆分特性，設(shè)計(jì)了求解小規(guī)模單技能及多技能項(xiàng)目調(diào)度問題的分支定界算法.Lu等[10]結(jié)合微軟的項(xiàng)目調(diào)度軟件，說明資源日歷對項(xiàng)目作業(yè)最早開始時(shí)間的影響，分析了4種時(shí)間關(guān)系在資源日歷下的延遲.Jirachai等[11]研究了作業(yè)可拆分在考慮資源空窗期的多模式RCPSP問題中對調(diào)度結(jié)果的影響，設(shè)計(jì)了求解小規(guī)模該類問題的分支定界算法.針對項(xiàng)目調(diào)度中部分資源存在不可用期的這一實(shí)際，本文在設(shè)計(jì)求解基礎(chǔ)RIP問題算法的基礎(chǔ)上，參照求解帶資源空窗期的RCPSP問題的研究方法，考慮資源存在提前已知的空窗期約束，并著重分析空窗期的引入對問題及算法設(shè)計(jì)的影響，提出適用于該問題的帶局部分支優(yōu)化操作的遺傳算法.

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

1.1 問題描述

項(xiàng)目由J項(xiàng)作業(yè)構(gòu)成，作業(yè)間存在著一定的時(shí)序關(guān)系，各作業(yè)僅在滿足時(shí)序約束并且所需資源充足的條件下才可開始執(zhí)行.記給定項(xiàng)目工期上限為T，作業(yè)集合A={1,2,…,J}，每項(xiàng)作業(yè)j(j∈A)的執(zhí)行時(shí)間為dj，Bpre(j)為項(xiàng)目中第j項(xiàng)作業(yè)的緊前作業(yè)集合，Bsuc(j)為其緊后作業(yè)集合.全部作業(yè)共享K種可更新資源，構(gòu)成資源種類集P={1,2,…,K}，同一種類下的所有資源皆一樣.每種資源p的單位使用成本為Cp(p∈P)，Wp為第p類資源下所有資源在項(xiàng)目工期T內(nèi)的可用時(shí)間窗集，引入?yún)⒘縕pt，Zpt=1表示資源p在t時(shí)刻可以使用，即t∈Wp，否則Zpt=0.各作業(yè)j所需要的資源種類為集合Mj，該集合大小為Sj，rjp表示作業(yè)j需要的單位資源p(p∈Mj)的數(shù)量.Rtp表示各作業(yè)在時(shí)刻t對資源p的使用量之和.對時(shí)間進(jìn)行了離散化處理，模型的求解目標(biāo)是優(yōu)化項(xiàng)目周期內(nèi)各資源p的使用成本.

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

(1)

(2)

?t∈Wp,?p∈P

(3)

?j∈A,?t∈T

(4)

(5)

?j*∈Bpre(j),?t∈T

txjt≤T?j∈A,?t∈T

(6)

(7)

?j∈A,?t∈T

xjt={0,1} ?j∈A,?t∈T

(8)

式(1)為目標(biāo)函數(shù)，表示最小化整個(gè)周期內(nèi)資源使用總成本.式(2)可以計(jì)算各資源p在其可用時(shí)間窗Wp內(nèi)的使用量.式(3)表示作業(yè)只有在所需資源皆可使用的情形下才能執(zhí)行.式(4)表示作業(yè)在整個(gè)項(xiàng)目工期內(nèi)的執(zhí)行時(shí)刻必須滿足該作業(yè)工期要求.式(5)表示時(shí)序約束，即作業(yè)必須在其所有緊前作業(yè)完成后才能進(jìn)行.式(6)表示所有作業(yè)的最晚結(jié)束時(shí)間不應(yīng)大于項(xiàng)目給定工期.式(7)表示作業(yè)一旦開始執(zhí)行就不能中斷.式(8)定義了決策變量xjt的可行域，作業(yè)j在時(shí)刻t執(zhí)行時(shí)xjt=1；否則xjt=0.

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

用RCPSP問題的求解思路解決RIP問題的算法設(shè)計(jì)中都以資源組合進(jìn)行編碼，采用某種優(yōu)先級規(guī)則下調(diào)度生成機(jī)制的解碼方式來評判各組合在給定工期上限內(nèi)的可行性，由于對應(yīng)每一編碼下的子問題仍是NP問題，簡單的啟發(fā)式算法所得結(jié)果往往較差，從而增大將可行資源組合判定為不可行的幾率，不利于求得較好的目標(biāo)值.本文算法設(shè)計(jì)中避免了由資源解碼得到作業(yè)調(diào)度計(jì)劃的過程，通過直接確定作業(yè)開始時(shí)間的方式來間接獲得項(xiàng)目中的資源投入量，解碼算法中只需根據(jù)各作業(yè)執(zhí)行位置計(jì)算各時(shí)刻資源消耗.考慮到后續(xù)的局部優(yōu)化操作，故對項(xiàng)目工期內(nèi)各時(shí)刻執(zhí)行的作業(yè)進(jìn)行編碼.以遺傳算法為搜索框架，充分利用迭代過程中作業(yè)不同開始時(shí)間對應(yīng)不同目標(biāo)值的信息，設(shè)計(jì)基于不同執(zhí)行位置概率分布的作業(yè)開始時(shí)間選擇方法來改進(jìn)變異操作，使資源使用量向最優(yōu)解收斂.在遺傳算法求得較優(yōu)可行解的基礎(chǔ)上，針對所得列表，以各資源最大用量的時(shí)刻為起始點(diǎn)，考慮資源空窗期的影響，對后續(xù)相鄰作業(yè)進(jìn)行局部分支定界搜索，通過部分作業(yè)的重調(diào)度來進(jìn)一步降低資源使用量.

算法框架如圖1所示.圖中：M為未改進(jìn)代數(shù)；m為未改進(jìn)代數(shù)閾值.

圖1 算法框架Fig.1 Algorithm framework

2.1 空窗期分析

(9)

i∈Bpre(j),j=1,2,…,J

(10)

i∈Bsuc(j),j=1,2,…,J

圖2 資源空窗期影響作業(yè)開始時(shí)間示意圖Fig.2 The diagram of starting time of the job affected by the resource vacations

由此可見，當(dāng)作業(yè)所需資源存在空窗期且影響作業(yè)開始時(shí)間的決策區(qū)間時(shí)，空窗期的引入會(huì)導(dǎo)致作業(yè)的可排區(qū)間進(jìn)一步縮小，降低作業(yè)調(diào)度的靈活性，影響調(diào)度結(jié)果，從而加劇空窗期前后位置的資源投入量，增加項(xiàng)目的成本支出.為優(yōu)化考慮資源空窗期對項(xiàng)目調(diào)度的影響，解決此類資源投入問題，本文提出以下遺傳算法及局部搜索算法進(jìn)行求解.

2.2 遺傳算法

2.2.1基于作業(yè)位置的編碼 本設(shè)計(jì)中采用對作業(yè)位置進(jìn)行編碼的方式，項(xiàng)目工期上限為T，則編碼長度為T段，編碼第i段表示該時(shí)刻t下開始執(zhí)行的作業(yè)集合，各編碼段集合大小不一.每一編碼段i上的作業(yè)集合必須保證各作業(yè)之間沒有緊前關(guān)系，且其緊前作業(yè)在該編碼段之前已執(zhí)行完畢.以圖3(a)所示算例為例，該網(wǎng)絡(luò)圖下的一種可行編碼方式為3(b)，其中作業(yè)2～7的開始時(shí)間分別為2、0、0、5、4和8.

圖3 編碼示例Fig.3 Example of code

染色體生成步驟如下：

(1)定義時(shí)刻t=0，已排作業(yè)集Y={1}，可排作業(yè)集H=?，未排作業(yè)集N={1,2,…,J}；

(2)若t=T，轉(zhuǎn)步驟(5)；否則，尋找t時(shí)刻緊前作業(yè)已完成的作業(yè)，加入可排作業(yè)集H，并將該作業(yè)從未排作業(yè)集中刪除；

(3)尋找可排作業(yè)集H中各作業(yè)的全部組合形式，加入集合B；

(4)隨機(jī)選擇集合B中的一種作業(yè)組合，作為時(shí)刻t的執(zhí)行作業(yè)集，令t=t+1，A=?，更新集合Y和N，轉(zhuǎn)步驟(2)；

(5)輸出編碼列表.

2.2.2單點(diǎn)交叉 在經(jīng)過輪盤賭選擇機(jī)制獲得的種群中，根據(jù)交叉概率Pc選擇需要進(jìn)行交叉操作的染色體組成集合C，

Pc=

(11)

式中：Pc1和Pc2均為預(yù)先定義的常數(shù)；favg和fmin分別為所有染色體的平均適應(yīng)度值和最小適應(yīng)度值.

圖4 交叉操作Fig.4 Crossover operation

2.2.3基于作業(yè)執(zhí)行位置選擇概率的變異 對經(jīng)過交叉之后得到的染色體，根據(jù)變異概率Pm選擇需要進(jìn)行變異操作的染色體組成集合G，Pm同樣通過式(11)求得.

對集合G中的染色體，本文設(shè)計(jì)了一種在迭代中改進(jìn)作業(yè)開始時(shí)間的變異機(jī)制，通過不斷調(diào)整迭代過程中各作業(yè)可排區(qū)間內(nèi)各開始時(shí)間取值的概率，排除會(huì)產(chǎn)生極大資源用量的作業(yè)開始時(shí)間值，進(jìn)一步縮小搜索空間，從而找到更好的作業(yè)調(diào)度方案.

定義染色體中變異作業(yè)μ開始時(shí)間選擇概率Ptsμ(tes≤ts≤tls)和該開始時(shí)間下需要多投入的資源量Rtsμ.在初始種群中，令Rtsμ=1.之后的每條染色體，都根據(jù)當(dāng)代的資源用量R更新Rtsμ：

Rtsμ=Rtsμ+max{0,R-R0}

(12)

染色體中需要變異的作業(yè)的開始時(shí)間ts被選中的概率為

(13)

式中：R0為當(dāng)前得到的最低資源用量.

在迭代過程中，資源用量越大的作業(yè)開始時(shí)間ts對應(yīng)的Rtsμ會(huì)不斷增大，使得其被選中的概率Ptsμ不斷減??；反之，越接近R0的作業(yè)開始時(shí)間對應(yīng)的Rtsμ較小，使得相應(yīng)Ptsμ被選中的概率變大，由此可以不斷縮小作業(yè)開始時(shí)間的決策區(qū)間，使得作業(yè)調(diào)度向著產(chǎn)生更好的解的方向收斂.

綜上，遺傳算法步驟如下：

(1)初始化種群，令迭代次數(shù)λ=0，當(dāng)前資源投入量為X；

(2)判斷λ<λmax，若是，轉(zhuǎn)步驟(3)；否則，轉(zhuǎn)步驟(7)；

(3)對各染色體進(jìn)行解碼，求得相應(yīng)的資源使用量；

(4)采用3.2.2和3.2.3中的交叉和變異機(jī)制生成新的種群；

(5)計(jì)算新生成個(gè)體的目標(biāo)函數(shù)值，更新X；

(6)運(yùn)用輪盤賭選擇算子產(chǎn)生下一代種群，λ=λ+1，轉(zhuǎn)步驟(2)；

(7)輸出X.

2.3 局部優(yōu)化算法

在遺傳算法所得作業(yè)調(diào)度方案的基礎(chǔ)上，為進(jìn)一步優(yōu)化調(diào)度結(jié)果，降低資源投入成本，本文提出以分支定界算法為框架的局部優(yōu)化操作，對調(diào)度結(jié)果中各最大資源量處的作業(yè)進(jìn)行完全搜索，尋找較低資源用量的作業(yè)組合方式及執(zhí)行方案，現(xiàn)就其中涉及的分支方法與支配規(guī)則進(jìn)行闡述.

2.3.1分支方法 對所得作業(yè)位置列表，計(jì)算各時(shí)刻各資源消耗量，選擇各資源最大用量處開始執(zhí)行的j項(xiàng)作業(yè)進(jìn)行深度搜索，通過回溯方法驗(yàn)證其鄰域分支，直至完全搜索，具體步驟如下：

(2)確定j項(xiàng)作業(yè)中可以在節(jié)點(diǎn)g處執(zhí)行的作業(yè)組合集合Cg；

(3)從Cg中隨機(jī)選擇作業(yè)組合Eg，更新Cg=Cg-Eg；

(5)若所有分支節(jié)點(diǎn)都滿足Cg=?，則搜索結(jié)束，更新原調(diào)度方案中j項(xiàng)作業(yè)的執(zhí)行位置及資源消耗量.

以圖3(a)所示7項(xiàng)作業(yè)的項(xiàng)目網(wǎng)絡(luò)圖為例，對應(yīng)的搜索樹結(jié)構(gòu)如圖5所示.圖中：節(jié)點(diǎn)O=?表示該時(shí)刻有未執(zhí)行完成的作業(yè)，可以不選擇新的作業(yè)執(zhí)行.

圖5 搜索樹示例Fig.5 Example of search tree

2.3.2支配規(guī)則 為提高分支過程搜索的效率，本文提出4種支配規(guī)則，用以剪除多余不可行或不好的分支.

定義當(dāng)前調(diào)度時(shí)刻為t，當(dāng)前節(jié)點(diǎn)為g，g在時(shí)刻t-1的根節(jié)點(diǎn)為g′，作業(yè)j：

(1)未調(diào)度且其緊前作業(yè)在t之前皆已執(zhí)行完畢，則稱作業(yè)j為時(shí)刻t可排作業(yè)；

(2)未調(diào)度且其tes=t，則稱作業(yè)j為時(shí)刻t必排作業(yè)；

(3)已調(diào)度且其結(jié)束時(shí)間tft>t，則稱作業(yè)j為時(shí)刻t執(zhí)行作業(yè)；

(4)已調(diào)度且其結(jié)束時(shí)間tft≤t，則稱作業(yè)j為時(shí)刻t已排作業(yè)；

(5)不屬于已排作業(yè)，則稱作業(yè)j為時(shí)刻t未排作業(yè).

規(guī)則1若決策集E(t)中存在不包含所有必排作業(yè)集L(t)中的元素的子集Fv(t)，v∈N*，則該子集Fv(t)所在節(jié)點(diǎn)不再分支.

證明所謂必排作業(yè)，即滿足tls=t，tls的值是根據(jù)工期上限和資源空窗期確定的，代表作業(yè)的最晚開始時(shí)間，超出該時(shí)刻執(zhí)行則表明項(xiàng)目一定會(huì)延期，在既定工期上限下無法求得可行解，所以對不包含必排作業(yè)的節(jié)點(diǎn)進(jìn)行截?cái)?

圖6 規(guī)則1示例圖Fig.6 Example of rule 1

證明該問題旨在求得項(xiàng)目最低資源投入成本，當(dāng)前已得可行解X，則任一資源用量不小于X的節(jié)點(diǎn)都無需再枚舉.以圖3(a)算例為例，示意圖如圖7所示.當(dāng)前可行解X=7，該時(shí)刻已完成調(diào)度的作業(yè)為4(作業(yè)2未執(zhí)行完畢)，可排作業(yè)組合為{?，{6}，{3}，{3,6}}，各組合節(jié)點(diǎn)的資源使用成本分別為3/5/7/9，其中節(jié)點(diǎn)O22和O23的資源使用成本≥X，則相應(yīng)節(jié)點(diǎn)被截?cái)?

圖7 規(guī)則2示例圖Fig.7 Example of rule 2

(14)

時(shí)刻t未排作業(yè)及子集Fv(t)中剩余未執(zhí)行工期在[t+1,T]時(shí)間段內(nèi)對各資源p的需求量

R=pg=(RpN(t)-RpFv(t))/(T-t-1)

圖8 規(guī)則3示例圖Fig.8 Example of rule 3

規(guī)則4若時(shí)刻t的決策集F(t)中存在2個(gè)子集Fu(t)和Fv(t)滿足：

則子集Fu(t)所在節(jié)點(diǎn)不再分支.

證明2個(gè)子集Fu(t)和Fv(t)間存在從屬關(guān)系，包含作業(yè)數(shù)多的子集Fv(t)在當(dāng)前不完全調(diào)度下所得局部目標(biāo)函數(shù)值明顯優(yōu)于包含作業(yè)數(shù)少的子集Fu(t)，且不影響全局目標(biāo)函數(shù)值，相對后續(xù)調(diào)度而言，F(xiàn)v(t)能節(jié)省出更多資源及時(shí)間的選擇，降低局部目標(biāo)值提升的概率.

局部優(yōu)化算法步驟如下：

(3)根據(jù)支配規(guī)則判斷當(dāng)前節(jié)點(diǎn)是否能夠剪除，若可以轉(zhuǎn)步驟(4)；否則，繼續(xù)分支.

(4)若所有分支皆已枚舉，則轉(zhuǎn)步驟(5)；否則，回溯搜索樹，繼續(xù)分支，轉(zhuǎn)步驟(3).

(5)選擇集合H的最優(yōu)調(diào)度計(jì)劃，更新原計(jì)劃，若p>K，優(yōu)化結(jié)束；否則，轉(zhuǎn)步驟(2).

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

為驗(yàn)證上述提出的帶局部優(yōu)化操作的遺傳算法對于求解帶資源空窗期的資源投入問題的有效性，本文運(yùn)用C#(Visual Studio 2013)編程實(shí)現(xiàn)該算法，測試平臺為Intel Core i5處理器，2.40 GHz主頻，8 G內(nèi)存.

3.1 實(shí)例驗(yàn)證

選取飛機(jī)裝配過程中包含部分裝配作業(yè)的一個(gè)小規(guī)模裝配實(shí)例對所提算法進(jìn)行驗(yàn)證分析.項(xiàng)目中共計(jì)18項(xiàng)作業(yè)，其中作業(yè)1和作業(yè)18為虛作業(yè)，工期為0且不占用資源.作業(yè)間時(shí)序關(guān)系、作業(yè)工期及所需資源量如表1所示.表中：資源R4存在空窗期 [0,1]和[27,29].分別利用CPLEX、本文提出的GA算法和文獻(xiàn)[6]中設(shè)計(jì)的算法來求解該實(shí)例，調(diào)度方案如圖9所示.圖中：3種方法調(diào)度所得實(shí)例中的資源總成本分別為58、59和61.由于資源R4存在前后2段空窗期，限制了如2、4、15和17等作業(yè)的最早開始時(shí)間，導(dǎo)致其決策區(qū)間縮小，3種算法皆安排未使用資源4的作業(yè)3和作業(yè)16在相應(yīng)空窗期時(shí)刻執(zhí)行，降低空窗期前后位置的資源使用峰值.圖9(b)和(c)中為本文設(shè)計(jì)的遺傳算法求解該實(shí)例的結(jié)果，可以發(fā)現(xiàn)，當(dāng)引入局部分支定界優(yōu)化操作后能將資源量從63降至59，大大提升優(yōu)化效率，甚至更優(yōu)于文獻(xiàn)設(shè)計(jì)的算法，獲得接近于最優(yōu)解的目標(biāo)值.

表1 作業(yè)時(shí)序關(guān)系、工期及資源量Tab.1 Precedence relations,duration and resources of jobs

圖9 各算法調(diào)度結(jié)果Fig.9 Scheduling results of different algorithms

3.2 算例對比分析

為了驗(yàn)證本文所提算法的有效性，將該算法的運(yùn)行結(jié)果與CPLEX軟件所求精確解及文獻(xiàn)算法進(jìn)行了對比.本文所用測試算例是基于測試問題庫PSPLIB中的算例進(jìn)行改造的，對于基本算例中未提供的參數(shù)，采用在一定大小范圍內(nèi)通過Random函數(shù)隨機(jī)產(chǎn)生自然數(shù)的方式來確定，其中工期上限T取資源不受限下基于最早開始時(shí)間調(diào)度得到的作業(yè)最晚完成時(shí)間的 1.2 倍，資源空窗期通過在項(xiàng)目工期內(nèi)隨機(jī)產(chǎn)生長度為3的區(qū)間獲得.

在表2～4中，每組包含5個(gè)算例，CPLEX列中OC表示CPLEX在處理本組5個(gè)算例時(shí)得到的最優(yōu)解的平均值取整，tC表示CPLEX平均運(yùn)算時(shí)間；GA列中AG表示本文算法在處理本組5個(gè)算例時(shí)得到的最好解的平均值取整，tG表示本文算法平均運(yùn)算時(shí)間；對2種算法所得結(jié)果進(jìn)行比較.BB列中AB表示本文局部優(yōu)化算法中所設(shè)計(jì)的分支定界算法用以處理本組算例得到的最好解的平均值取整，tB表示算法平均運(yùn)算時(shí)間，同樣將其與CPLEX結(jié)果進(jìn)行比較.其中：

從表2～4中GAP1項(xiàng)可以發(fā)現(xiàn)，對作業(yè)數(shù)為10,12,16的算例，本文所設(shè)計(jì)遺傳算法求得的問題的解較CPLEX所得最優(yōu)解分別相差 0.34%,0.78%,1.48%，平均偏差小于1%，從而證明本文算法在求解小規(guī)模問題上的有效性.表格中的后半部分，將應(yīng)用于遺傳算法中局部優(yōu)化操作的分支定界算法用以求解相應(yīng)算例，從BB欄的tB項(xiàng)及GAP2項(xiàng)可以發(fā)現(xiàn)，此算法能在較短的時(shí)間內(nèi)獲得問題的最優(yōu)解，由此表明本文提出的4條支配規(guī)則能有效提高分支定界算法搜索效率.

表2 10個(gè)作業(yè)實(shí)驗(yàn)結(jié)果Tab.2 Experiment results of 10 jobs

表3 12個(gè)作業(yè)實(shí)驗(yàn)結(jié)果Tab.3 Experiment results of 12 jobs

表4 16個(gè)作業(yè)實(shí)驗(yàn)結(jié)果Tab.4 Experiment results of 16 jobs

對于作業(yè)數(shù)為30，60，90的中大型規(guī)模的算例，CPLEX在規(guī)定時(shí)間內(nèi)無法求得問題的最優(yōu)解，所得上下界間的差距也極大，因此本研究中以此類規(guī)模算例為例，將所設(shè)計(jì)遺傳算法與文獻(xiàn)[6]中提出的人工免疫算法AIS進(jìn)行了對比.表5～7中，每組同樣包含5個(gè)算例，其中GA列中VG項(xiàng)表示GA在處理本組算例時(shí)運(yùn)行5次后得到的最小值的平均值，tG項(xiàng)表示GA平均運(yùn)算時(shí)間；AIS列中VA項(xiàng)表示對比算法在處理本組算例時(shí)運(yùn)行5次后得到的最小值的平均值，tA項(xiàng)表示對比算法平均運(yùn)算時(shí)間；

通過表5～7的數(shù)值結(jié)果可以發(fā)現(xiàn)，本文所設(shè)計(jì)的遺傳算法較現(xiàn)有文獻(xiàn)的人工免疫算法，就作業(yè)數(shù)為30,60,90這3類算例而言，求解精度分別提升1.96%,2.55%,3.36%，局部分支優(yōu)化的操作能進(jìn)一步降低所得資源成本，從而實(shí)現(xiàn)全局優(yōu)化.

表5 30個(gè)作業(yè)實(shí)驗(yàn)結(jié)果Tab.5 Experiment results of 30 jobs

表6 60個(gè)作業(yè)實(shí)驗(yàn)結(jié)果Tab.6 Experiment results of 60 jobs

表7 90個(gè)作業(yè)實(shí)驗(yàn)結(jié)果Tab.7 Experiment results of 90 jobs

4 結(jié)語

資源投入問題是工程調(diào)度問題的一個(gè)重要分類，長期以來備受關(guān)注.針對飛機(jī)裝配中部分關(guān)鍵資源存在空窗期這一特性，本文設(shè)計(jì)了帶分支定界局部優(yōu)化操作的改進(jìn)型遺傳算法求解該問題，提出了基于作業(yè)位置的編碼方式，及在迭代中改進(jìn)作業(yè)開始時(shí)間的變異機(jī)制.通過數(shù)值實(shí)驗(yàn)，驗(yàn)證了本文所提出的算法在求解該問題時(shí)的有效性.小規(guī)模算例中，算法所得解與最優(yōu)解間的平均差值在1%以下；中大規(guī)模算例中，相較現(xiàn)有文獻(xiàn)的人工免疫算法，帶分支局部優(yōu)化的遺傳算法能進(jìn)一步提升問題的求解精度，降低資源的投入成本.后續(xù)對該問題的研究中可以考慮引入作業(yè)可拆分、作業(yè)多執(zhí)行模式等特性，通過降低空窗期對問題調(diào)度的影響，進(jìn)一步優(yōu)化調(diào)度結(jié)果.