【摘要】：資源約束項(xiàng)目調(diào)度問題(RCPSP)是一類重要的調(diào)度問題,它主要研究項(xiàng)目在滿足項(xiàng)目活動(dòng)時(shí)序約束和資源約束的條件下,對(duì)項(xiàng)目中的活動(dòng)的開始時(shí)間和完成時(shí)間進(jìn)行合理安排,以達(dá)到某一管理目標(biāo)的最優(yōu)化。如:工期最短,成本最小,資源均衡等。該問題理論上屬于NP-hard問題,模型豐富,許多組合優(yōu)化問題是RCPSP的特殊情形。此外RCPSP也廣泛存在于建筑行業(yè),軟件行業(yè),制造業(yè)等行業(yè)中。因此研究RCPSP具有重要的理論意義和現(xiàn)實(shí)意義。本文主要研究?jī)?nèi)容如下:(1).針對(duì)經(jīng)典RCPSP,本文將遺傳算法和新穎的教學(xué)算法相結(jié)合,設(shè)計(jì)了一種新的用于求解經(jīng)典資源約束項(xiàng)目調(diào)度問題的智能優(yōu)化算法——教學(xué)遺傳算法。此算法根據(jù)教學(xué)算法過程中的兩階段搜索方法設(shè)計(jì)了一種二次交叉操作,第一次交叉在教師個(gè)體與學(xué)生個(gè)體之間,第二次交叉在學(xué)生個(gè)體與學(xué)生個(gè)體之間以一定的交叉概率進(jìn)行,這種交叉操作的設(shè)計(jì)使得教學(xué)遺傳算法能有效的跳出局部最優(yōu),從而得到更好的調(diào)度方案。實(shí)驗(yàn)部分選用標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)PSPLIB中的經(jīng)典資源約束項(xiàng)目調(diào)度問題集進(jìn)行驗(yàn)證算法的有效性,結(jié)果表明優(yōu)于現(xiàn)有文獻(xiàn)中已有的一種算法。(2).在實(shí)際的項(xiàng)目調(diào)度中,項(xiàng)目各活動(dòng)在執(zhí)行時(shí)往往存在一種以上的執(zhí)行模式,每種模式都代表一組資源需求量和相應(yīng)持續(xù)時(shí)間的組合,不同的持續(xù)時(shí)間會(huì)有不同的資源需求,因此多執(zhí)行模式資源約束項(xiàng)目調(diào)度問題作為經(jīng)典RCPSP的擴(kuò)展,更具有實(shí)際意義。針對(duì)MRCPSP本文提出了一種混合遺傳算法。該算法在計(jì)算之前,需要對(duì)項(xiàng)目中數(shù)據(jù)進(jìn)行預(yù)處理,然后基于拓?fù)渑判虍a(chǎn)生初始種群,最后,為了改善遺傳算法的局部搜索能力,設(shè)計(jì)了一種基于鄰域搜索的變異操作。實(shí)驗(yàn)部分對(duì)標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)中的基準(zhǔn)問題J18,J20進(jìn)行了測(cè)試,驗(yàn)證了算法的有效性。(3).理論和算法最終都是要為實(shí)際服務(wù)的,要為現(xiàn)代項(xiàng)目中的項(xiàng)目管理問題提供實(shí)際解決方案。為驗(yàn)證本文所提出的混合遺傳算法能否應(yīng)用于具體實(shí)際,針對(duì)MRCPSP問題進(jìn)行案例研究,結(jié)果表明該智能算法不僅豐富了多執(zhí)行模式RCPSP的求解方法,而且拓寬了遺傳算法的應(yīng)用領(lǐng)域。
[Abstract]:Resource constrained project scheduling problem (RCPSP) is a kind of important scheduling problem. It mainly studies how to arrange the start time and completion time of project activities reasonably under the condition of satisfying project activity timing constraints and resource constraints. To optimize the achievement of a management goal. Such as: the shortest time limit, minimum cost, resource balance, etc. This problem belongs to the NP-hard problem theoretically and has abundant models. Many combinatorial optimization problems are special cases of RCPSP. In addition, RCPSP also widely exists in the construction industry, software industry, manufacturing industry and other industries. Therefore, the study of RCPSP has important theoretical and practical significance. The main contents of this paper are as follows: (1). Aiming at classical RCPSP, this paper combines genetic algorithm with new teaching algorithm, and designs a new intelligent optimization algorithm for solving classical resource constrained project scheduling problem, which is called instructional genetic algorithm (TGA). According to the two-stage search method in the process of teaching algorithm, this algorithm designs a kind of second crossover operation, the first crossover is between the individual of teacher and the individual of student. The second crossover is carried out with a certain cross probability between students and students. The design of the crossover operation enables the instructional genetic algorithm to jump out of the local optimum effectively and obtain a better scheduling scheme. In the experimental part, the classical resource constrained project scheduling problem set in standard database PSPLIB is selected to verify the validity of the algorithm. The results show that it is better than one of the existing algorithms in the existing literature. (2) In actual project scheduling, there is often more than one execution mode for each project activity. Each model represents a combination of resource requirements and corresponding durations, and different durations will have different resource requirements. Therefore, as an extension of classical RCPSP, multi-execution mode resource-constrained project scheduling problem has more practical significance. This paper presents a hybrid genetic algorithm for MRCPSP. In order to improve the local search ability of genetic algorithm, a mutation operation based on neighborhood search is designed to improve the local search ability of genetic algorithm. In the experimental part, the benchmark problem J18 / J20 in the standard database is tested, and the validity of the algorithm is verified. (3). Both the theory and the algorithm should serve the practice and provide practical solutions for the project management problems in modern projects. In order to verify whether the hybrid genetic algorithm proposed in this paper can be applied to practical applications, a case study on the MRCPSP problem is carried out. The results show that the intelligent algorithm not only enriches the solution method of multi-execution mode RCPSP, but also improves the performance of the algorithm. Moreover, it widens the application field of genetic algorithm.
【學(xué)位授予單位】：湖南工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：F282;TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 宋紅星;曹文彬;;基于雙種群蟻群算法的多目標(biāo)資源受限項(xiàng)目調(diào)度問題研究[J];信息系統(tǒng)工程;2010年04期

2 程序;吳澄;;一種復(fù)雜項(xiàng)目調(diào)度問題的混合智能算法[J];計(jì)算機(jī)集成制造系統(tǒng);2006年04期

3 徐進(jìn);費(fèi)少梅;張樹有;施岳定;;自適應(yīng)粒子群求解資源動(dòng)態(tài)分配項(xiàng)目調(diào)度問題[J];計(jì)算機(jī)集成制造系統(tǒng);2011年08期

4 雒興剛;汪定偉;唐加福;;任務(wù)可拆分項(xiàng)目調(diào)度問題[J];東北大學(xué)學(xué)報(bào);2006年09期

5 宗硯;劉瓊;張超勇;朱海平;;考慮資源傳遞時(shí)間的多項(xiàng)目調(diào)度問題[J];計(jì)算機(jī)集成制造系統(tǒng);2011年09期

6 孫曉雅;林焰;;任務(wù)可定點(diǎn)拆分的資源受限項(xiàng)目調(diào)度問題研究[J];微電子學(xué)與計(jì)算機(jī);2012年07期

7 張維存;康凱;;蟻群-粒子群算法求解多模式資源受限項(xiàng)目調(diào)度問題[J];計(jì)算機(jī)工程與應(yīng)用;2007年34期

8 劉敏;代成琴;王宇航;;資源受限的項(xiàng)目調(diào)度問題的求解算法[J];自動(dòng)化技術(shù)與應(yīng)用;2008年06期

9 盧睿;李林瑛;;一種求解反應(yīng)式項(xiàng)目調(diào)度問題的啟發(fā)式方法[J];系統(tǒng)仿真學(xué)報(bào);2011年02期

10 孫曉雅;林焰;;人工蜂群算法求解任務(wù)可拆分項(xiàng)目調(diào)度問題[J];微電子學(xué)與計(jì)算機(jī);2011年11期

相關(guān)會(huì)議論文 前3條

1 丁雪楓;尤建新;;多模式資源受限項(xiàng)目調(diào)度問題的混合優(yōu)化算法研究[A];第十四屆中國(guó)管理科學(xué)學(xué)術(shù)年會(huì)論文集(上冊(cè))[C];2012年

2 劉艷秋;張穎;汪定偉;王福利;;基于GA的RCPSP可靠性優(yōu)化方法研究[A];2001年中國(guó)智能自動(dòng)化會(huì)議論文集（下冊(cè)）[C];2001年

3 周楷;何正文;;周期性支付的多模式Max-npv項(xiàng)目調(diào)度問題研究[A];中國(guó)企業(yè)運(yùn)籌學(xué)學(xué)術(shù)交流大會(huì)論文集[C];2008年

相關(guān)博士學(xué)位論文 前8條

1 王宏;求解資源受限項(xiàng)目調(diào)度問題算法的研究[D];天津大學(xué);2005年

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

3 陳衛(wèi)明;動(dòng)態(tài)環(huán)境下產(chǎn)品開發(fā)項(xiàng)目調(diào)度問題及其求解研究[D];華中科技大學(xué);2011年

4 吳兵;柔性資源受限的多模式項(xiàng)目調(diào)度問題研究[D];武漢理工大學(xué);2008年

5 彭武良;面向產(chǎn)品開發(fā)的項(xiàng)目調(diào)度問題及項(xiàng)目管理系統(tǒng)研究[D];東北大學(xué);2008年

6 李詩(shī)嫻;基于凈現(xiàn)值的資源受限型項(xiàng)目調(diào)度問題研究[D];天津大學(xué);2012年

7 賈艷;資源受限項(xiàng)目調(diào)度問題的仿真優(yōu)化方法及其應(yīng)用研究[D];華中科技大學(xué);2012年

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

相關(guān)碩士學(xué)位論文 前10條

1 李遠(yuǎn)見;幾種改進(jìn)的智能算法及其應(yīng)用[D];安徽師范大學(xué);2015年

2 段向陽(yáng);基于遺傳算法的資源約束項(xiàng)目調(diào)度問題優(yōu)化及應(yīng)用研究[D];湖南工業(yè)大學(xué);2015年

3 張冠群;基于蟻群算法的多模式資源受限項(xiàng)目調(diào)度問題研究[D];湖南大學(xué);2009年

4 傅奧;多目標(biāo)資源受限項(xiàng)目調(diào)度問題蟻群算法研究[D];浙江大學(xué);2008年

5 蒲娟;多目標(biāo)模糊資源受限項(xiàng)目調(diào)度問題研究[D];鄭州大學(xué);2012年

6 薄銀利;基于模塊化外包的項(xiàng)目調(diào)度問題研究[D];蘭州大學(xué);2011年

7 劉志霞;資源受限項(xiàng)目調(diào)度問題及其任務(wù)擾動(dòng)的干擾管理研究[D];沈陽(yáng)工業(yè)大學(xué);2011年

8 陳俊波;考慮施工設(shè)備租賃的項(xiàng)目調(diào)度問題研究[D];華中科技大學(xué);2009年

9 劉雅婷;人力資源受限項(xiàng)目調(diào)度問題研究[D];華中科技大學(xué);2007年

10 王偉;任務(wù)工期不確定的資源受限項(xiàng)目調(diào)度優(yōu)化[D];浙江大學(xué);2010年

，

本文編號(hào)：2274050