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

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

2、PRCPSP是一個(gè)典型的NP-難問題,利用智能優(yōu)化方法求解該問題是重要的研究方向。我們?cè)谇叭艘延醒芯康幕A(chǔ)上,從多Agent優(yōu)化方法的角度探尋該問題的求解方式。具體而言,研究方法包括粒子群優(yōu)化方法(PSO)、蟻群優(yōu)化方法(ACO)和多Agent優(yōu)化方法(MAO)三種,其中PSO和ACO屬于群智能優(yōu)化方法,也都是MAO的一種。
　　 PSO首先被用于問題求解,相應(yīng)的算法為1PRCPSP PSO。我們?cè)O(shè)計(jì)了基于活動(dòng)列表的編碼、基于優(yōu)

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

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

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