本文關(guān)鍵詞：搶占式資源受限項目調(diào)度問題的多Agent優(yōu)化方法

  更多相關(guān)文章： 項目調(diào)度 搶占 多Agent優(yōu)化 粒子群優(yōu)化 蟻群優(yōu)化 峰交叉算子

【摘要】：本文的研究對象是資源受限項目調(diào)度問題的一個擴展問題,“允許最多一次搶占的搶占式資源受限項目調(diào)度問題”,即1_PRCPSP。實際項目中的某些活動會因為資源沒及時到位、或者需要優(yōu)先滿足其他活動的需要而被迫暫時終止；但出于控制進度偏差的需要,這種暫時終止不會被允許過多地存在。這是搶占式資源受限項目調(diào)度問題(PRCPSP)生的背景。1_PRCPSP是PRCPSP的特例,其中的每項活動至多只允許被搶占一次。 與RCPSP一樣,1_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)先權(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_ACO。該算法同樣借鑒了峰交叉算子的思想,設(shè)計了峰路徑信息素增強機制,針對當(dāng)前代最好的解的峰,施加一個額外的信息素增強操作。算法采用1_SSGS將螞蟻走過的路徑轉(zhuǎn)化為問題的可行調(diào)度。同樣的,我們使用PSPLIB中的RCPSP數(shù)據(jù)集對算法的收斂性和求解效果作了評估。 最后,我們設(shè)計了一種1PRCPSP_MAS體系及相應(yīng)的優(yōu)化方法1PRCPSP_MAO。1PRCPSP_MAS體系包含兩類Agent:負責(zé)項目資源請求與活動執(zhí)行的活動Agent,以及負責(zé)資源分配和項目調(diào)度的調(diào)度Agent�；顒覣gent與調(diào)度Agent之間通過協(xié)商機制完成資源分配和項目調(diào)度；通過一種迭代改進機制來實現(xiàn)問題解的優(yōu)化。與前兩類不同的是,1 PRCPSP MAO同時具有仿真和優(yōu)化兩種特征。Agent之間的協(xié)商機制,旨在模擬實際項目運作中經(jīng)常發(fā)生的負責(zé)人或部門之間通過溝通解決沖突或改變項目計劃的情形；而迭代改進機制則使得算法具有優(yōu)化問題解的功能。 本文的成果具有理論和實踐意義,豐富了搶占式資源受限項目調(diào)度問題的研究方式,拓展了粒子群優(yōu)化方法、蟻群優(yōu)化方法和多Agent優(yōu)化方法的應(yīng)用領(lǐng)域；所設(shè)計的多Agent系統(tǒng)可以用于項目進度管理決策中,為項目計劃制定階段的項目整體評估提供了一種基于MAS的仿真優(yōu)化方法。
【關(guān)鍵詞】：項目調(diào)度 搶占 多Agent優(yōu)化 粒子群優(yōu)化 蟻群優(yōu)化 峰交叉算子
【學(xué)位授予單位】：浙江大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：F062.4;F224
【目錄】：

• 致謝4-6
• 摘要6-8
• Abstract8-10
• 目錄10-13
• 圖目錄13-15
• 表目錄15-16
• 1 緒論16-28
• 1.1 研究背景和意義17-23
• 1.2 研究問題的提出23-24
• 1.3 研究框架與論文組織24-26
• 1.4 本章小結(jié)26-28
• 2 搶占式資源受限項目調(diào)度問題28-52
• 2.1 文獻綜述28-34
• 2.1.1 RCPSP28-32
• 2.1.2 PRCPSP32-34
• 2.2 模型描述34-39
• 2.3 算法概述39-50
• 2.3.1 重要概念39-41
• 2.3.2 串行進度生成機制41-46
• 2.3.3 雙向調(diào)整技術(shù)46-47
• 2.3.4 允許一次搶占的串行進度生成機制47-48
• 2.3.5 峰交叉算子48-50
• 2.4 本章小結(jié)50-52
• 3 多AGENT優(yōu)化方法52-80
• 3.1 群智能優(yōu)化方法52-53
• 3.2 粒子群優(yōu)化方法53-59
• 3.2.1 產(chǎn)生與發(fā)展53-55
• 3.2.2 算法流程55-57
• 3.2.3 在項目調(diào)度問題上的應(yīng)用57-59
• 3.3 蟻群優(yōu)化方法59-67
• 3.3.1 產(chǎn)生與發(fā)展59-64
• 3.3.2 算法流程64
• 3.3.3 在調(diào)度問題上的應(yīng)用64-67
• 3.4 多AGENT優(yōu)化方法67-78
• 3.4.1 產(chǎn)生與發(fā)展67-71
• 3.4.2 體系結(jié)構(gòu)71-77
• 3.4.3 開發(fā)工具77-78
• 3.5 本章小結(jié)78-80
• 4 搶占式資源受限項目調(diào)度問題的粒子群優(yōu)化方法80-96
• 4.1 算法描述80-87
• 4.1.1 粒子編碼80-83
• 4.1.2 粒子解碼83-84
• 4.1.3 適應(yīng)值函數(shù)84
• 4.1.4 粒子更新機制84-86
• 4.1.5 總體流程86-87
• 4.2 計算實驗87-94
• 4.2.1 實驗環(huán)境87
• 4.2.2 參數(shù)設(shè)置87-88
• 4.2.3 實驗結(jié)果88-94
• 4.3 本章小結(jié)94-96
• 5 搶占式資源受限項目調(diào)度問題的蟻群優(yōu)化方法96-106
• 5.1 算法描述96-99
• 5.1.1 路徑構(gòu)建方案96-97
• 5.1.2 信息素信息更新機制97
• 5.1.3 啟發(fā)式信息97-98
• 5.1.4 適應(yīng)值函數(shù)98
• 5.1.5 總體流程98-99
• 5.2 計算實驗99-104
• 5.2.1 實驗環(huán)境99
• 5.2.2 參數(shù)設(shè)置99-100
• 5.2.3 實驗結(jié)果100-104
• 5.3 本章小結(jié)104-106
• 6 搶占式資源受限項目調(diào)度問題的多AGENT優(yōu)化方法106-126
• 6.1 系統(tǒng)描述106-112
• 6.1.1 系統(tǒng)縱覽106-108
• 6.1.2 協(xié)商模型108-109
• 6.1.3 調(diào)度Agent109-111
• 6.1.4 活動Agent111-112
• 6.2 計算實例112-123
• 6.3 計算實驗123-125
• 6.3.1 實驗環(huán)境123-124
• 6.3.2 實驗結(jié)果124-125
• 6.4 本章小結(jié)125-126
• 7 進一步討論126-132
• 7.1 三種MAO的比較126-130
• 7.1.1 四種Agent特征對比126-127
• 7.1.2 三種MAO效果對比127-130
• 7.2 管理實踐意義130-131
• 7.3 本章小結(jié)131-132
• 8 總結(jié)與展望132-134
• 參考文獻134-144
• 附錄1 名詞中英文對照144-150
• 附錄2 PSPLIB中的RCPSP問題實例150-154
• 作者簡歷及在學(xué)期間所取得主要科研成果154

【共引文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 伍京華;蔣國瑞;黃梯云;;一種基于Agent的辯論談判中的反駁模型[J];北京工業(yè)大學(xué)學(xué)報;2007年09期

2 胡德明;;優(yōu)化巖土工程勘察的探討[J];才智;2008年13期

3 孫丹丹;苗建松;王朝翔;丁煒;;Ad Hoc網(wǎng)絡(luò)中基于蟻群優(yōu)化的路由選擇算法[J];吉林大學(xué)學(xué)報(信息科學(xué)版);2007年06期

4 劉瓊,楊紅杰,汪永琳;Agent與基于Agent系統(tǒng)[J];常德師范學(xué)院學(xué)報(自然科學(xué)版);2000年01期

5 付曉;于振華;劉宇;;一種無線傳感器網(wǎng)絡(luò)形式化模型及應(yīng)用研究[J];傳感技術(shù)學(xué)報;2008年09期

6 楊栩;尤學(xué)一;季民;潘留明;王秀朵;趙樂軍;;城市綠地土壤入滲模型及參數(shù)確定[J];城市環(huán)境與城市生態(tài);2011年06期

7 亢孟軍;王貝;杜清運;王明軍;;上下文敏感的空間信息服務(wù)智能推送研究[J];測繪科學(xué);2011年03期

8 葛繼科;邱玉輝;閻艷;;基于BDI Agent的網(wǎng)格服務(wù)模型研究[J];重慶師范大學(xué)學(xué)報(自然科學(xué)版);2008年04期

9 曹鳳雪;;多Agent系統(tǒng)中組織適應(yīng)的形式化方法[J];江蘇技術(shù)師范學(xué)院學(xué)報;2011年06期

10 李信滿,趙宏;高速網(wǎng)絡(luò)環(huán)境下的網(wǎng)絡(luò)入侵檢測系統(tǒng)[J];東北大學(xué)學(xué)報;2002年07期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 薛宏濤;沈林成;;基于協(xié)進化方法的多智能體系統(tǒng)及其符號演繹理論模型[A];第二十六屆中國控制會議論文集[C];2007年

2 嚴彬;熊偉清;程美英;葉青;;基于擁塞控制的多種群二元蟻群算法[A];第二十七屆中國控制會議論文集[C];2008年

3 ;Particle Swarm Optimization of Periodic Deep Brain Stimulation Waveforms[A];中國自動化學(xué)會控制理論專業(yè)委員會A卷[C];2011年

4 張元敏;殷志鋒;周雅;;蟻群算法在多用戶檢測中的應(yīng)用及其改進[A];第十三屆全國信號處理學(xué)術(shù)年會（CCSP-2007）論文集[C];2007年

5 楊俊杰;陳俊宏;;利用智能型代理人進行野外環(huán)境輻射監(jiān)測之研究[A];第11屆海峽兩岸信息管理發(fā)展策略研討會論文集[C];2005年

6 ;An estimation of distribution algorithm for resource-constrained project scheduling problem[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

7 ;Hybrid particle swarm optimization-simplex algorithm for inverse problem[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

8 ;Research on the Decision-making of Multi-issue/Attribute Negotiation Based on Agent Technology and the Genetic Algorithm[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

9 ;A Modified Glowworm Swarm Optimization for Multimodal Functions[A];Proceedings of the 2011 Chinese Control and Decision Conference（CCDC）[C];2011年

10 蔡遠利;于振華;王瑞峰;;多Agent系統(tǒng)形式化建模方法學(xué)[A];'2006系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會論文集[C];2006年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 汪澎;駕駛?cè)司X狀態(tài)檢測技術(shù)研究[D];江蘇大學(xué);2010年

2 應(yīng)瑛;不確定資源約束下項目調(diào)度問題研究[D];浙江大學(xué);2010年

3 許偉;基于進化算法的復(fù)雜化工過程智能建模方法及其應(yīng)用[D];華東理工大學(xué);2011年

4 傅朝陽;面向?qū)崟r任務(wù)求解的自治服務(wù)協(xié)同模型、形式語義及其驗證[D];浙江大學(xué);2010年

5 李永卓;我國電力市場化進程中供應(yīng)鏈管理研究[D];中國地質(zhì)大學(xué)（北京）;2011年

6 王靜;化肥供應(yīng)鏈及其適應(yīng)性研究[D];北京交通大學(xué);2011年

7 賀利堅;多Agent系統(tǒng)中信任和信譽模型的研究[D];北京交通大學(xué);2011年

8 田文迪;隨機DTRTP環(huán)境下項目調(diào)度策略的比較研究[D];華中科技大學(xué);2011年

9 彭飛;實值演化算法投資組合研究[D];中國科學(xué)技術(shù)大學(xué);2011年

10 李玉劍;復(fù)雜系統(tǒng)中集體行為和臨界現(xiàn)象的動力學(xué)研究[D];中國科學(xué)技術(shù)大學(xué);2011年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 郭凱;基于BDI的agent協(xié)商目標(biāo)研究[D];鄭州大學(xué);2009年

2 蔣紅進;蟻群算法在光突發(fā)交換網(wǎng)絡(luò)路由中的研究[D];哈爾濱工程大學(xué);2010年

3 周柏欣;無線Ad Hoc專用通信網(wǎng)絡(luò)路由協(xié)議研究[D];哈爾濱工程大學(xué);2010年

4 梁林娜;復(fù)雜多主體戰(zhàn)略管控系統(tǒng)建模及應(yīng)用研究[D];中國海洋大學(xué);2010年

5 周緒倩;基于電子商務(wù)的Web數(shù)據(jù)挖掘系統(tǒng)架構(gòu)研究[D];河北工程大學(xué);2010年

6 呂海鵬;改進蟻群算法在YKK系列中型高壓電機優(yōu)化設(shè)計中的應(yīng)用[D];哈爾濱理工大學(xué);2010年

7 宋紅星;多模式資源約束項目工期—成本優(yōu)化問題研究[D];江南大學(xué);2010年

8 溫麗丹;Agent在HIS中的應(yīng)用研究[D];長春工業(yè)大學(xué);2010年

9 賈曉冬;Multi-Agent在建筑工程預(yù)算系統(tǒng)中的應(yīng)用研究[D];長春工業(yè)大學(xué);2010年

10 梁毅;粒子群算法搜索模式研究與應(yīng)用[D];華東理工大學(xué);2011年

，

本文編號：935903