資源受限項(xiàng)目調(diào)度問題的混合遺傳算法研究.pdf

1、資源受限項(xiàng)目調(diào)度問題(RCPSP)是一類重要的調(diào)度問題,它要求在滿足項(xiàng)目時(shí)序約束和資源約束的條件下,安排所有工作的開工期和完工期,以達(dá)到某一最優(yōu)的目標(biāo)。該問題理論上屬于NP-hard問題,許多組合優(yōu)化問題是RCPSP的特殊情形。因此研究RCPSP具有重要的理論和現(xiàn)實(shí)意義。本文主要研究求解資源受限項(xiàng)目調(diào)度問題的改進(jìn)遺傳算法。首先,結(jié)合文化算法的雙層結(jié)構(gòu)和多智能體進(jìn)化算法的演化優(yōu)勢(shì)以及遺傳算法的靈活編碼方式,提出一種求解資源受限項(xiàng)目調(diào)度問題

2、的混合遺傳算法—多智能體文化遺傳算法。算法設(shè)置了上層信仰空間和下層群體空間,各空間內(nèi)智能體通過與其鄰域進(jìn)行競(jìng)爭(zhēng)、合作操作及自學(xué)習(xí)操作來增加自身的能量,空間之間的交互是定期通過接受操作和影響操作采用同步傳輸方式來完成,同時(shí)為測(cè)試算法的通用性,選擇了多個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行了仿真。結(jié)果表明：多智能體文化遺傳算法(MACGA)不僅能夠有效地跳出局部最優(yōu),而且具有較高的的收斂速度。其次,將各算法應(yīng)用到經(jīng)典資源受限項(xiàng)目調(diào)度問題中,算法采用十進(jìn)制編碼方

3、式,結(jié)合工作的存儲(chǔ)鄰接矩陣隨機(jī)生成調(diào)度序列,有效地解決了工作調(diào)度違例現(xiàn)象。運(yùn)用優(yōu)先搶占模式的資源分配方式,來安排工作資源,從而避免了資源分配中的沖突問題。本文以準(zhǔn)數(shù)據(jù)庫PSPLIB中的經(jīng)典資源受限項(xiàng)目調(diào)度問題為例進(jìn)行仿真,驗(yàn)證各算法的穩(wěn)定性和有效性。最后,考慮到實(shí)際項(xiàng)目中各工作執(zhí)行時(shí)往往有多種執(zhí)行模式可供選擇,因此將各算法應(yīng)用到多模式資源受限項(xiàng)目調(diào)度問題中。由于一種模式代表一組資源需求量及相應(yīng)執(zhí)行時(shí)間的組合,不同的執(zhí)行時(shí)間對(duì)應(yīng)不同的資源