【摘要】：資源受限項目調(diào)度問題是項目管理領域的一類長期受人關注的研究課題,此類問題是各類新的高性能優(yōu)化方法的實驗床。在此類問題的求解中,人們一般會直接利用活動的整體時間窗屬性,通過可行解空間的搜索來獲取最優(yōu)調(diào)度方案,而在搜索中卻忽略了活動的時間窗的可分解特性。通過活動時間窗的分解,可以有效縮小可行解空間,減少搜索過程中的計算量和時間花費,這對求解大規(guī)模的資源受限項目調(diào)度問題具有重大意義,因此本文對時間窗分解算法進行了創(chuàng)新性的嘗試。本研究結合活動時間窗分解的基本思想,首先設計并分析了合適的時間窗分解活動的選擇策略與可行解空間分解策略,將原問題可行解空間分解成多個子可行解空間,然后根據(jù)重定義方法更新子可行解空間的時間窗,隨后基于不同采樣策略設置每個子可行解空間的采樣規(guī)模,最后分別在不同的子可行解空間中進行調(diào)度方案的搜索。經(jīng)過實驗對不同策略的檢驗,本文選取了五種時間窗分解活動的選擇策略、三種可行解空間分解策略和兩種采樣策略進行詳細介紹,并對上述策略進行有效組合,通過基于標準案例庫PSPLIB的計算實驗,分別在J30、J60與J120三組測試集上做了實驗分析和對比,廣泛地驗證了本算法的有效性。實驗結果表明,RCPSP的時間窗分解算法在具體案例上能將可行解空間有效降低,并在不同可行解空間分解策略和采樣策略下,均相對于未分解的算法在求解時間效率上有顯著提高,充分表明了算法的合理性和有效性。此外,本算法具有良好的可拓展性,可嵌套多種啟發(fā)式算法進一步提高求解效率,這對于未來的研究方向也指出了可行的道路。
[Abstract]:Resource constrained project scheduling problem is a kind of research topic which has been paid close attention to for a long time in the field of project management. This kind of problem is the experimental bed of all kinds of new high performance optimization methods. In solving this kind of problem, people usually use the whole time window attribute of the activity directly to obtain the optimal scheduling scheme through the search of the feasible solution space, but ignore the decomposability of the active time window in the search. Through the decomposition of the active time window, the feasible solution space can be effectively reduced and the amount of computation and time spent in the search process can be reduced, which is of great significance to solve the large-scale resource-constrained project scheduling problem. Therefore, this paper makes an innovative attempt on the time window decomposition algorithm. In this study, combined with the basic idea of active time window decomposition, the suitable selection strategy and feasible solution space decomposition strategy of time window decomposition activity are designed and analyzed, and the feasible solution space of the original problem is decomposed into several sub-feasible solution spaces. Then the time window of the subfeasible solution space is updated according to the redefinition method, and then the sampling scale of each subfeasible solution space is set based on different sampling strategies. Finally, the scheduling scheme is searched in different subfeasible solution spaces. Through the experimental test of different strategies, this paper selects five selection strategies of time window decomposition activities, three feasible solution space decomposition strategies and two sampling strategies in detail, and effectively combines the above strategies. Through the calculation experiments based on the standard case base PSPLIB, the experimental analysis and comparison are carried out on J30, J60 and J120 test sets, and the effectiveness of the algorithm is widely verified. The experimental results show that the time window decomposition algorithm of RCPSP can effectively reduce the feasible solution space in specific cases, and under different feasible solution space decomposition strategies and sampling strategies, Compared with the undecomposed algorithm, the time efficiency of the algorithm is significantly improved, which fully shows the rationality and effectiveness of the algorithm. In addition, the algorithm has good extensibility and can be nesting a variety of heuristic algorithms to further improve the efficiency of the solution, which also points out a feasible way for the future research direction.
【學位授予單位】：華中科技大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP301.6

【參考文獻】

相關期刊論文 前4條

1 楊利宏;楊東;;基于遺傳算法的資源約束型項目調(diào)度優(yōu)化[J];管理科學;2008年04期

2 劉振元;王紅衛(wèi);;活動網(wǎng)絡中先序和后序活動的時間參數(shù)計算[J];華中科技大學學報(自然科學版);2007年04期

3 劉士新,王夢光,唐加福;一種求解資源受限工程調(diào)度問題的遺傳算法[J];系統(tǒng)工程學報;2002年01期

4 劉士新,王夢光,唐加福;資源受限工程調(diào)度問題的優(yōu)化方法綜述[J];控制與決策;2001年S1期

相關博士學位論文 前2條

1 張松;資源受限項目調(diào)度若干問題研究[D];中國科學技術大學;2014年

2 鄧林義;資源受限的項目調(diào)度問題及其應用研究[D];大連理工大學;2008年

相關碩士學位論文 前1條

1 余文敏;兩類資源受限項目調(diào)度問題的嵌套分割算法研究[D];華中科技大學;2013年

，

本文編號：2493536