帶資源空窗期的資源投入型問(wèn)題的建模與優(yōu)化

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

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

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

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

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

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

1.1 問(wèn)題描述

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

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

1.2 空窗期

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

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

圖1 資源空窗期示意圖

度，易得lm=te,m-tb,m；δ(m-1,m)表示第m個(gè)非空窗期的長(zhǎng)度，易得δ(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)表示該問(wèn)題是優(yōu)化整個(gè)周期內(nèi)各資源使用的最大總成本.約束條件(2)表明時(shí)刻t資源p的使用量；式(3)表示任務(wù)在整個(gè)周期內(nèi)的執(zhí)行時(shí)間滿(mǎn)足該任務(wù)工期約束；任務(wù)之間應(yīng)該滿(mǎn)足約束(4)，即滿(mǎn)足一定的優(yōu)先關(guān)系；式(5)說(shuō)明需要關(guān)鍵資源的任務(wù)必須滿(mǎn)足空窗期約束；式(6)說(shuō)明任務(wù)一旦開(kāi)始，在完成之前不允許被中斷；式(7)說(shuō)明所有任務(wù)的最晚結(jié)束時(shí)間不應(yīng)大于項(xiàng)目給定工期.

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

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

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

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

(1) 工期規(guī)則

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

(2) EST規(guī)則

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

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

2.3.2任務(wù)j∈J開(kāi)始時(shí)間tST,j可排區(qū)間點(diǎn)集

(8)

(9)

(10)

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

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

(11)

2.3.3任務(wù)j∈J開(kāi)始時(shí)間tST,j可變區(qū)間點(diǎn)集

社會(huì)保障體系中的商業(yè)保險(xiǎn)：關(guān)系形成、目標(biāo)構(gòu)建與屬性定位 …………………………………………… 謝長(zhǎng)青 張藝珂（4/33）

(12)

任務(wù)j開(kāi)始時(shí)間tST,j的可變區(qū)間點(diǎn)集即為任務(wù)j開(kāi)始時(shí)間tST,j的決策區(qū)間.

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

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

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

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

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

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

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

3 遺傳算法設(shè)計(jì)

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

3.1 編碼

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

圖3 編碼示例

3.2 遺傳操作

3.2.1初始種群

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

3.2.2選擇

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

(13)

3.2.3交叉

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

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

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

圖4 交叉操作示例

3.2.4變異

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

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

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

圖5 變異操作示例

3.3 解碼

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

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

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

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

表1～5中：

(14)

(15)

(16)

表1 10項(xiàng)任務(wù)實(shí)驗(yàn)結(jié)果

表2 20項(xiàng)任務(wù)實(shí)驗(yàn)結(jié)果

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

表3 30項(xiàng)任務(wù)實(shí)驗(yàn)結(jié)果

表4 60項(xiàng)任務(wù)實(shí)驗(yàn)結(jié)果

表5 90項(xiàng)任務(wù)實(shí)驗(yàn)結(jié)果

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

5 總結(jié)與展望

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