本文選題：資源受限條件下的項目調(diào)度問題　切入點：P系統(tǒng)　出處：《山東師范大學》2017年碩士論文　論文類型：學位論文

【摘要】：膜計算(Membrane computing,又稱P系統(tǒng),P system)是一類新型自然計算模型,通過對生物細胞、細胞組織以及細胞器官的結構和功能進行模擬,將生物細胞生化反應以及物質(zhì)交流的過程抽象得到進化規(guī)則,進而實現(xiàn)計算過程。該類自然計算模型具有極大并行性、分布式、圖靈等價性等優(yōu)點,已廣泛應用于智能機器人、生物學、數(shù)據(jù)挖掘、密碼學、經(jīng)濟學等應用領域,是極具前景的研究領域,將在新時期的大數(shù)據(jù)時代發(fā)揮更大的作用。從理論上,由于部分簡單的膜計算模型已經(jīng)被證明具有圖靈等價性的特點,且膜計算模型具有極大并行性的特點,因此,膜計算在理論計算機領域有可能超越圖靈機的地位,并取而代之。因此,膜計算成為各學科學者研究的熱點。項目制作為當代社會最重要的一種經(jīng)濟活動組織形式,項目管理已經(jīng)成為企業(yè)管理人員的必修課,而項目調(diào)度問題作為項目管理中項目時間管理的重要組成部分,同樣受到學者的關注。隨著信息技術的飛速發(fā)展,項目活動分解結構(WBS)日益精細,考慮到的約束條件日益增加,項目管理與其他研究領域一樣進入了大數(shù)據(jù)時代,而資源受限條件下的項目調(diào)度問題(RCPSP)屬于NP-hard問題,隨著項目活動數(shù)量的增加,問題難以在適當?shù)臅r間內(nèi)得到答案,因此,將新型算法應用于資源受限條件下的項目調(diào)度問題(RCPSP)成為該問題研究的熱點。對于NP-hard問題,計算消耗大,因此,尋找新的計算模型,提高運算效率,成為學界研究的熱點�；谀び嬎愕臉O大并行性的特點,本論文嘗試將資源受限條件下的項目調(diào)度問題(RCPSP)與膜計算結合,利用膜計算理論提高計算效率,更高效地求解資源受限條件下的項目調(diào)度問題(RCPSP)。本論文的主要工作包括:一是提出一種新型協(xié)同類細胞膜計算計算模型,展示該膜計算計算模型運行過程,并證明該膜計算計算模型的計算能力;二是將新型協(xié)同膜計算模型與基于優(yōu)先規(guī)則的串行項目進度方案生成機制(SSGS)結合,提出優(yōu)化資源受限條件下的項目調(diào)度問題(RCPSP)的協(xié)同類細胞P系統(tǒng),設計出相應的膜結構、膜規(guī)則、膜對象等,并用案例驗證了P系統(tǒng)的可行性;三是將新型協(xié)同膜計算模型與遺傳算法相結合,提出一種新型基于協(xié)同類細胞P系統(tǒng)的優(yōu)化資源受限條件下的項目調(diào)度問題(RCPSP)的協(xié)同膜算法,并使用PSPLIB數(shù)據(jù)庫的案例集驗證該算法的有效性;四是將新型協(xié)同膜計算模型與遺傳算法相結合,提出一種新型基于協(xié)同類細胞P系統(tǒng)的求解多執(zhí)行模式資源受限條件下的項目調(diào)度問題(MRCPSP)的協(xié)同膜算法,并使用PSPLIB數(shù)據(jù)庫的案例集驗證該算法的有效性。
[Abstract]:Membrane computing (also known as P system) is a new type of natural computing model that simulates the structure and function of biological cells, tissues and organs. This kind of natural computing model has been widely used in intelligent robots because it has the advantages of maximum parallelism, distribution and Turing equivalence. Biology, data mining, cryptography, economics and other application fields, are very promising research areas, will play a greater role in the new era of big data. Because some simple membrane computing models have been proved to have the characteristics of Turing equivalence, and the membrane computing model has the characteristics of great parallelism, it is possible that membrane computing can surpass the position of Turing machine in the field of theoretical computer. Therefore, membrane computing has become a hot topic for scholars in various disciplines. Project making is one of the most important forms of economic activity organization in contemporary society, and project management has become a compulsory course for enterprise managers. As an important part of project time management, project scheduling problem is also concerned by scholars. With the rapid development of information technology, the decomposition structure of project activities is becoming more and more sophisticated, and the constraint conditions are increasing day by day. Project management, like other research fields, has entered the era of big data, and the problem of project scheduling under limited resources belongs to the NP-hard problem. With the increase of the number of project activities, it is difficult to get an answer in an appropriate time. The application of the new algorithm to the project scheduling problem under the condition of limited resources has become a hot topic in this paper. For the NP-hard problem, the computation consumption is large, so we find a new computing model to improve the computational efficiency. Based on the characteristics of maximum parallelism of membrane computing, this paper attempts to combine the project scheduling problem (RCPSPP) with membrane computing in order to improve the computational efficiency by using the membrane computing theory. The main work of this thesis includes: first, a new kind of collaborative cell membrane computing model is proposed to show the running process of the membrane computing model. The computational capability of the membrane computing model is proved. Secondly, the new collaborative membrane computing model is combined with the serial project schedule generation mechanism based on priority rules (SSGSs). A cooperative cell P system is proposed to optimize the project scheduling problem (RCPSP) under the condition of limited resources. The corresponding membrane structure, membrane rules, membrane objects and so on are designed. The feasibility of the P system is verified by a case study. The third is to combine the new collaborative membrane computing model with genetic algorithm, and propose a new collaborative membrane algorithm based on collaborative cell-like P system, which is an optimized project scheduling problem with limited resources. The case set of PSPLIB database is used to verify the validity of the algorithm. Fourth, the new collaborative membrane computing model is combined with genetic algorithm. A new collaborative membrane algorithm based on cooperative cell P system is proposed to solve the project scheduling problem with multi-execution mode resource constraints. The validity of the algorithm is verified by using the case set of PSPLIB database.
【學位授予單位】：山東師范大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：F272

【參考文獻】

相關期刊論文 前1條

1 潘林強;宋_";;細胞計算進展與展望[J];中國科學院院刊;2014年01期

相關博士學位論文 前6條

1 薛潔;兩類生物計算問題及其在數(shù)據(jù)挖掘中的應用研究[D];山東師范大學;2015年

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

3 劉闖;基于類細胞膜計算的優(yōu)化方法及其應用研究[D];大連理工大學;2014年

4 金敏力;基于關鍵鏈的項目優(yōu)化調(diào)度問題研究[D];哈爾濱工業(yè)大學;2013年

5 牛云云;求解計算困難問題的膜計算模型與算法研究[D];華中科技大學;2012年

6 黃亮;膜計算優(yōu)化方法研究[D];浙江大學;2007年

，

本文編號：1596704