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

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

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

【部分圖文】：

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

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

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

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



本文編號：3460582