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

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

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

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

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