基于工位的資源受限項(xiàng)目調(diào)度問題的模型研究與調(diào)度算法實(shí)現(xiàn).pdf

1、資源受限項(xiàng)目調(diào)度問題(Resource-constrained Project Scheduling Problem，RCPSP)包含一組在調(diào)度過程中必須滿足優(yōu)先關(guān)系和資源約束的任務(wù)，常見調(diào)度目標(biāo)是最小化最大完工時間(Makespan)。在生產(chǎn)系統(tǒng)或服務(wù)組織中，存在這么一類問題，相對于RCPSP，額外擁有一定數(shù)量不同類型的工位，任務(wù)需要在特定的工位上執(zhí)行，每個資源只能服務(wù)有限的工位，工件或可移動的資源在工位之間移動需要一定的時間，調(diào)度目

2、標(biāo)也是最小化最大完工時間。在以前RCPSP研究中，缺少對工件和資源位置的考慮，因此上述問題不能直接使用RCPSP模型進(jìn)行求解。本文將對基于工位約束的資源受限項(xiàng)目調(diào)度問題(Site-based and Resource-constrainedProject Scheduling Problem，SRCPSP)做以下詳細(xì)描述與分析。
　　首先，本文在介紹RCPSP及其各種擴(kuò)展約束后，分析了工位的基本約束，并對工位與資源、工位與工件和工

3、位與任務(wù)之間的約束進(jìn)行了詳細(xì)的分析與公式化描述。結(jié)合任務(wù)優(yōu)先關(guān)系與工位的約束，證明了任務(wù)的同工位特性，定義了同工位任務(wù)。基于同工位任務(wù)提出了任務(wù)子網(wǎng)(Sub-net，SN)和聯(lián)合子網(wǎng)(CombinedSub-nets，CSN)的概念，并設(shè)計(jì)了SN和CSN的求解流程，將工位約束與RCPSP模型結(jié)合，給出了SRCPSP的模型。
　　其次，為了在可接受時間內(nèi)獲得SRCPSP的可行解，本文提出兩個基于優(yōu)先規(guī)則的啟發(fā)式調(diào)度算法，分別是基于任

4、務(wù)子網(wǎng)的搜索算法(Sub-net Based Searchalgorithm，SNBS)和基于聯(lián)合子網(wǎng)的搜索算法(Combined Sub-nets Based Searchalgorithm，CSNBS)。此外，為更好的解釋上述算法，文中給出了SNBS算法和CSNBS算法的流程圖。
　　最后，本文使用項(xiàng)目調(diào)度仿真平臺獲得了可用于驗(yàn)證算法正確新的兩組測試實(shí)例。實(shí)驗(yàn)結(jié)果表明SNBS在時間效率上優(yōu)于CSNBS，但CSNBS較SNBS獲