研究多次搶占式資源受限的項(xiàng)目調(diào)度問(wèn)題,假設(shè)任意時(shí)間點(diǎn)可作為資源搶占節(jié)點(diǎn)且搶占次數(shù)不受限制,建立滿足多次資源搶占的線性整數(shù)規(guī)劃模型并提出改進(jìn)遺傳算法對(duì)其進(jìn)行求解。為克服遺傳算法（GA）局部搜索能力缺陷,在算法中引入禁忌搜索（TS）進(jìn)一步優(yōu)化子代。針對(duì)性地設(shè)計(jì)了允許多次搶占的基于工作優(yōu)先級(jí)編碼策略以及串行調(diào)度方案生成機(jī)制。通過(guò)測(cè)試算例集實(shí)驗(yàn)調(diào)試算法參數(shù),并以標(biāo)準(zhǔn)算例集（Project Scheduling ProblemLibrary,PSPLIB）對(duì)算法進(jìn)行可行性檢驗(yàn)。實(shí)驗(yàn)結(jié)果表明,資源受限項(xiàng)目調(diào)度問(wèn)題中引入多次搶占機(jī)制能有效縮減項(xiàng)目工期,設(shè)計(jì)的算法對(duì)問(wèn)題求解效果良好。 

【文章來(lái)源】：計(jì)算機(jī)工程與應(yīng)用. 2019,55(06)北大核心CSCD

【文章頁(yè)數(shù)】：6 頁(yè)

【部分圖文】：

工序關(guān)系與約束信息圖

少于必要時(shí)間；約束函數(shù)（8）表示決策變量。假設(shè)一個(gè)包含11個(gè)工作的項(xiàng)目，工作0和工作10分別是表示開(kāi)始和結(jié)束的虛擬任務(wù)，其余工作均為需要時(shí)間和可再生資源的實(shí)際工作。工作之間的網(wǎng)絡(luò)關(guān)系與約束信息如圖1所示。以工作8為例，工作8的開(kāi)始以工作5和6同時(shí)完成為前提，工作8的開(kāi)始時(shí)間為前序任務(wù)的最晚的結(jié)束時(shí)間，且完成工作8需要至少3個(gè)單位時(shí)間，各單位時(shí)間內(nèi)供應(yīng)的可更新資源不少于2個(gè)單位數(shù)量。上述小規(guī)模RCPSP，由于其網(wǎng)絡(luò)復(fù)雜度較低，通過(guò)精確算法求得工作一次性調(diào)度下的最優(yōu)方案。項(xiàng)目單位時(shí)間資源使用量如圖2所示。從圖2中可以看出，項(xiàng)目整體持續(xù)時(shí)間為15天，其中7天未實(shí)現(xiàn)資源利用最大化，精確算法雖可以求得RCPSP的最優(yōu)調(diào)度方案，但是上述方案仍然有大量資源出現(xiàn)閑置，難以實(shí)現(xiàn)資源連續(xù)高效使用。由于完成項(xiàng)目所需的資源總量確定，項(xiàng)目工期會(huì)隨單位時(shí)間資源利用率的降低而延長(zhǎng)，若能提高單位時(shí)間資源利用率，就能縮短整個(gè)項(xiàng)目的完成時(shí)間。PRCPSP以單位時(shí)間節(jié)點(diǎn)作為工作搶占點(diǎn)，在滿足資源約束和前后關(guān)系約束的前提下，允許其他滿足進(jìn)行條件的工作搶占當(dāng)前進(jìn)行工作的資源并優(yōu)先進(jìn)行。當(dāng)采取搶占式調(diào)度方案時(shí)，能有效地避免上述資源閑置所帶來(lái)的工期順延[18]。3算法設(shè)計(jì)遺傳算法是模擬生物進(jìn)化過(guò)程搜索最優(yōu)解的方法，算法將其求解的問(wèn)題以“染色體”的形式表現(xiàn)，采用“適者生存”的原則對(duì)種群內(nèi)染色體進(jìn)行選擇、交叉、變異操作，以獲得高適應(yīng)度子代個(gè)體。遺傳算法因其本身具有強(qiáng)大的自適應(yīng)性、可擴(kuò)展性及群體進(jìn)化能力被廣泛應(yīng)用。禁忌搜索算法屬于鄰域搜索算法，具有自適應(yīng)的存儲(chǔ)記憶功能。算法從一個(gè)初始可行解開(kāi)始，搜索過(guò)程中通過(guò)禁忌表避免迂回搜索，同時(shí)可通過(guò)藐視準(zhǔn)則特赦被禁忌的最優(yōu)解，從而實(shí)現(xiàn)對(duì)?

?Pc，算法基本流程如下：BEGINParameter:Popsizeo,MaxGen,PcSet:InitPop;gen=1Compute:Fitness(gen)WHILEgen≤MaxGen;Pair:Group=Popsizeo/2Crossover:twopointMutate:tubasearchCompute:Fitness(newgen)Merge:gen=gen+newgen;Popsize=2×PopsizeoUpdate:gen=gen+1Select:Popsize=PopsizeoENDWHILEEND4算例分析結(jié)合本文模型及所提算法對(duì)所舉算例進(jìn)行分析。假設(shè)其工作允許搶占，但是限制其最大搶占次數(shù)為1時(shí)，其他條件不做變化，得到相應(yīng)調(diào)度方案2，項(xiàng)目單位時(shí)間資源使用量如圖3所示。調(diào)度方案2總持續(xù)天數(shù)為15，項(xiàng)目實(shí)現(xiàn)資源最大利用時(shí)間為12。相比方案1其前期資源得到了連續(xù)高效使用，實(shí)現(xiàn)了利用率最大化，但1_PRCPSP的項(xiàng)目完成時(shí)間沒(méi)有得到縮減。針對(duì)此案例采用多次搶占策略做進(jìn)一步優(yōu)化，得到相應(yīng)調(diào)度方案3，項(xiàng)目單位時(shí)間資源使用量如圖4所示。調(diào)度方案3總持續(xù)天數(shù)為14，項(xiàng)目實(shí)現(xiàn)資源最大利用時(shí)間為11。方案3在實(shí)現(xiàn)資源使用的穩(wěn)定性優(yōu)化的同時(shí)，縮短了項(xiàng)目的總體完成時(shí)間。為進(jìn)一步檢證文中所提搶占模型及其算法可行性，采用Kolisch構(gòu)建的標(biāo)準(zhǔn)算例庫(kù)PSPLIB中單模式RCP-SP算例進(jìn)行算法性能測(cè)試。算例中的每個(gè)工作最多有3個(gè)緊后任務(wù)，共涉及調(diào)度4種可更新資源，并限制每種資源的可用上限。算例庫(kù)中算例有4種規(guī)模，以其工作數(shù)量劃分分別為J30、J60、J90、J120，其中算例庫(kù)已公布J30算例在非搶占情況下的精確算法最優(yōu)解。本文采用J30算例作為算法的實(shí)驗(yàn)數(shù)據(jù)對(duì)算法進(jìn)行可行性驗(yàn)證。遺傳算法求解受算法參數(shù)影響，為保證算法求解效果，擬對(duì)交叉概率Pc和變異概率Pm進(jìn)行參數(shù)調(diào)試。首先對(duì)J30中部分算例進(jìn)行實(shí)驗(yàn)，確定算法參數(shù)。統(tǒng)計(jì)J30中各算例的持續(xù)時(shí)間，依據(jù)分層抽樣原則，將

【參考文獻(xiàn)】：
期刊論文
[1]求解任務(wù)可拆分多項(xiàng)目協(xié)同調(diào)度問(wèn)題的啟發(fā)式算法[J]. 王磊,聶蘭順,戰(zhàn)德臣,王弼陡,羅剛銀.  控制與決策. 2017(06)
[2]基于項(xiàng)目網(wǎng)絡(luò)拆分決策的多項(xiàng)目協(xié)同調(diào)度問(wèn)題建模[J]. 陸志強(qiáng),楊超.  上海交通大學(xué)學(xué)報(bào). 2017(02)
[3]任務(wù)可拆分的多模式多項(xiàng)目調(diào)度模型與算法[J]. 王偉鑫,王旭,葛顯龍.  計(jì)算機(jī)集成制造系統(tǒng). 2014(06)
[4]搶占式資源受限項(xiàng)目調(diào)度問(wèn)題的遺傳算法[J]. 壽涌毅,彭曉峰,李菲,賴昌濤.  浙江大學(xué)學(xué)報(bào)(工學(xué)版). 2014(08)



本文編號(hào)：3460582