搶占式資源受限項目調(diào)度問題的多Agent優(yōu)化方法.pdf

1、本文的研究對象是資源受限項目調(diào)度問題的一個擴展問題,“允許最多一次搶占的搶占式資源受限項目調(diào)度問題”,即1 PRCPSP。實際項目中的某些活動會因為資源沒及時到位、或者需要優(yōu)先滿足其他活動的需要而被迫暫時終止;但出于控制進度偏差的需要,這種暫時終止不會被允許過多地存在。這是搶占式資源受限項目調(diào)度問題(PRCPSP)產(chǎn)生的背景。1 PRCPSP是PRCPSP的特例,其中的每項活動至多只允許被搶占一次。
　　 與RCPSP一樣,1

2、PRCPSP是一個典型的NP-難問題,利用智能優(yōu)化方法求解該問題是重要的研究方向。我們在前人已有研究的基礎(chǔ)上,從多Agent優(yōu)化方法的角度探尋該問題的求解方式。具體而言,研究方法包括粒子群優(yōu)化方法(PSO)、蟻群優(yōu)化方法(ACO)和多Agent優(yōu)化方法(MAO)三種,其中PSO和ACO屬于群智能優(yōu)化方法,也都是MAO的一種。
　　 PSO首先被用于問題求解,相應(yīng)的算法為1PRCPSP PSO。我們設(shè)計了基于活動列表的編碼、基于優(yōu)

3、先權(quán)值的編碼、基于活動列表和搶占點的編碼,以及基于優(yōu)先權(quán)值和搶占點的編碼四種編碼方式,采用串行進度生成機制(SSGS)和允許一次搶占的串行進度生成機制(1 SSGS)來解碼,結(jié)合峰交叉算子(PX)的思想設(shè)計了相應(yīng)的粒子更新機制。在PSPLIB中的RCPSP數(shù)據(jù)集上的計算實驗顯示,1PRCPSP PSO不僅具有很好的收斂性,而且能求得具有競爭性的結(jié)果。
　　 其次,我們將ACO應(yīng)用于1_PRCPSP的求解中,設(shè)計了1PRCPSP

4、ACO。該算法同樣借鑒了峰交叉算子的思想,設(shè)計了峰路徑信息素增強機制,針對當前代最好的解的峰,施加一個額外的信息素增強操作。算法采用1_SSGS將螞蟻走過的路徑轉(zhuǎn)化為問題的可行調(diào)度。同樣的,我們使用PSPLIB中的RCPSP數(shù)據(jù)集對算法的收斂性和求解效果作了評估。
　　 最后,我們設(shè)計了一種1PRCPSP MAS體系及相應(yīng)的優(yōu)化方法1PRCPSP_MAO。1PRCPSP_MAS體系包含兩類Agent:負責項目資源請求與活動執(zhí)行的

5、活動Agent,以及負責資源分配和項目調(diào)度的調(diào)度Agent。活動Agent與調(diào)度Agent之間通過協(xié)商機制完成資源分配和項目調(diào)度;通過一種迭代改進機制來實現(xiàn)問題解的優(yōu)化。與前兩類不同的是,1PRCPSP MAO同時具有仿真和優(yōu)化兩種特征。Agent之間的協(xié)商機制,旨在模擬實際項目運作中經(jīng)常發(fā)生的負責人或部門之間通過溝通解決沖突或改變項目計劃的情形;而迭代改進機制則使得算法具有優(yōu)化問題解的功能。
　　 本文的成果具有理論和實踐意義