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

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

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

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