基于遺傳算法的多資源約束項(xiàng)目調(diào)度問題研究.pdf

1、項(xiàng)目調(diào)度是對(duì)項(xiàng)目活動(dòng)的時(shí)間進(jìn)度管理，是項(xiàng)目管理的重要內(nèi)容且具有重要的現(xiàn)實(shí)意義。多資源約束項(xiàng)目調(diào)度問題 RCPSP（Resource-Constrained Project Scheduling Problems）是項(xiàng)目調(diào)度中最基礎(chǔ)的一類問題，它是在滿足項(xiàng)目活動(dòng)優(yōu)先約束關(guān)系和資源約束關(guān)系的條件下，合理安排項(xiàng)目活動(dòng)的開始時(shí)間和結(jié)束時(shí)間，達(dá)到項(xiàng)目工期最短的目標(biāo)。多資源約束項(xiàng)目調(diào)度問題屬于 NP-hard（Non-deterministic p

2、olynomial-time hard）問題，在工程中對(duì)于此類優(yōu)化問題一般只須高效地求出次優(yōu)解而不是最優(yōu)解。
　　綜述了項(xiàng)目調(diào)度發(fā)展歷程及其模型和求解方法，對(duì)項(xiàng)目調(diào)度各種模型特點(diǎn)進(jìn)行了分析和比較，選擇多資源約束項(xiàng)目調(diào)度模型作為對(duì)象進(jìn)行研究。遺傳算法 GA（Genetic Algorithm）在求解多資源約束項(xiàng)目調(diào)度問題上具有良好的效果，結(jié)合多資源約束項(xiàng)目調(diào)度模型特點(diǎn)設(shè)計(jì)新的遺傳算法進(jìn)行求解，如：設(shè)計(jì)兩點(diǎn)交叉算子使之不產(chǎn)生重碼，將精

3、英保留策略與局部搜索算法嵌入遺傳算法提高遺傳算法搜索性能。基于國際標(biāo)準(zhǔn)問題庫PSPLIB（Project Scheduling Problem Library）中的標(biāo)準(zhǔn)算例進(jìn)行算法測(cè)試，比較了不同算法的性能，結(jié)果表明了改進(jìn)的遺傳算法求解效果的優(yōu)越性。同時(shí)引入某公司項(xiàng)目調(diào)度實(shí)例，將理論模型與實(shí)際項(xiàng)目調(diào)度過程相結(jié)合，為項(xiàng)目調(diào)度優(yōu)化提供指導(dǎo)。
　　進(jìn)一步研究了不確定執(zhí)行時(shí)間的多資源約束項(xiàng)目調(diào)度問題，引入模糊理論表示不確定的活動(dòng)時(shí)間，將六