求解資源受限項(xiàng)目調(diào)度問(wèn)題算法的研究.pdf

1、資源受限項(xiàng)目調(diào)度問(wèn)題(RCPSP)是一類重要的調(diào)度問(wèn)題,它要求在滿足項(xiàng)目時(shí)序約束和資源約束的條件下,安排所有任務(wù)的開(kāi)工期和完工期,以達(dá)到某一最優(yōu)的目標(biāo),如,工期最短,成本最小,資源均衡等.理論上該問(wèn)題屬于NP-hard問(wèn)題,模型豐富,許多組合優(yōu)化問(wèn)題是RCPSP的特殊情形,例如作業(yè)車間(job shop)調(diào)度,流水車間(flow shop)調(diào)度等.此外RCPSP廣泛存在于建筑工程,軟件開(kāi)發(fā),飛機(jī)和輪船制造等單件或小批量生產(chǎn)方式的企業(yè)中.

2、因此研究RCPSP具有重要的理論和現(xiàn)實(shí)意義.本文主要研究?jī)?nèi)容如下: 1.遺傳算法(GA)已經(jīng)應(yīng)用于經(jīng)典RCPSP中并取得了顯著的效果.在此基礎(chǔ)上,本文設(shè)計(jì)了一種新的編碼方法用于遺傳算法求解經(jīng)典RCPSP.此編碼方法為帶有解碼規(guī)則和解碼方向的任務(wù)鏈表,亦即在任務(wù)鏈表后面加上兩個(gè)基因,一個(gè)是表示解碼規(guī)則的基因,另一個(gè)是表示解碼方向的基因,由這兩個(gè)基因同時(shí)控制任務(wù)鏈表的解碼規(guī)則和解碼方向.選用標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)PSPLIB中的156個(gè)例子進(jìn)行

3、驗(yàn)證該算法的有效性,結(jié)果表明本算法優(yōu)于用任務(wù)鏈表和帶有解碼規(guī)則的任務(wù)鏈表兩種編碼的遺傳算法. 2.在實(shí)際的項(xiàng)目調(diào)度中,不確定因素往往會(huì)導(dǎo)致項(xiàng)目調(diào)度無(wú)法按預(yù)定方案正常執(zhí)行.為了更好地反映實(shí)際情況,本文研究了以排序健壯性最大為優(yōu)化目標(biāo)具有模糊工期和模糊交貨期的資源受限項(xiàng)目調(diào)度問(wèn)題,采用六點(diǎn)模糊數(shù)表示模糊工期和模糊交貨期,引入了兩種模糊數(shù)的弱比較方法,即積分值法和重心距離法.針對(duì)這一優(yōu)化問(wèn)題本文設(shè)計(jì)了一種基于任務(wù)鏈表編碼形式的遺傳算法

4、.數(shù)值實(shí)驗(yàn)結(jié)果表明,該算法優(yōu)于文獻(xiàn)中的相關(guān)算法,同時(shí)也表明基于兩種模糊數(shù)的弱比較方法對(duì)算法的性能影響較弱. 3.采用基于非支配性排序的多目標(biāo)遺傳算法(NSGA-Ⅱ),設(shè)計(jì)了一種求解多模式、多種類資源約束的多目標(biāo)資源受限項(xiàng)目調(diào)度問(wèn)題的遺傳算法,該算法采用了任務(wù)鏈表和模式向量的編碼方案,適應(yīng)值是個(gè)體的非支配等級(jí)和其局部擁擠距離,采用一種新的比較算子,比較兩個(gè)個(gè)體的適應(yīng)值的大小,特殊的精英選擇策略.將所設(shè)計(jì)的算法用于求解以項(xiàng)目總工期和