基于P系统的项目调度优化问题研究

发布时间：2018-03-11 05:08

本文选题：资源受限条件下的项目调度问题　切入点：P系统　出处：《山东师范大学》2017年硕士论文　论文类型：学位论文

【摘要】：膜计算(Membrane computing,又称P系统,P system)是一类新型自然计算模型,通过对生物细胞、细胞组织以及细胞器官的结构和功能进行模拟,将生物细胞生化反应以及物质交流的过程抽象得到进化规则,进而实现计算过程。该类自然计算模型具有极大并行性、分布式、图灵等价性等优点,已广泛应用于智能机器人、生物学、数据挖掘、密码学、经济学等应用领域,是极具前景的研究领域,将在新时期的大数据时代发挥更大的作用。从理论上,由于部分简单的膜计算模型已经被证明具有图灵等价性的特点,且膜计算模型具有极大并行性的特点,因此,膜计算在理论计算机领域有可能超越图灵机的地位,并取而代之。因此,膜计算成为各学科学者研究的热点。项目制作为当代社会最重要的一种经济活动组织形式,项目管理已经成为企业管理人员的必修课,而项目调度问题作为项目管理中项目时间管理的重要组成部分,同样受到学者的关注。随着信息技术的飞速发展,项目活动分解结构(WBS)日益精细,考虑到的约束条件日益增加,项目管理与其他研究领域一样进入了大数据时代,而资源受限条件下的项目调度问题(RCPSP)属于NP-hard问题,随着项目活动数量的增加,问题难以在适当的时间内得到答案,因此,将新型算法应用于资源受限条件下的项目调度问题(RCPSP)成为该问题研究的热点。对于NP-hard问题,计算消耗大,因此,寻找新的计算模型,提高运算效率,成为学界研究的热点。基于膜计算的极大并行性的特点,本论文尝试将资源受限条件下的项目调度问题(RCPSP)与膜计算结合,利用膜计算理论提高计算效率,更高效地求解资源受限条件下的项目调度问题(RCPSP)。本论文的主要工作包括:一是提出一种新型协同类细胞膜计算计算模型,展示该膜计算计算模型运行过程,并证明该膜计算计算模型的计算能力;二是将新型协同膜计算模型与基于优先规则的串行项目进度方案生成机制(SSGS)结合,提出优化资源受限条件下的项目调度问题(RCPSP)的协同类细胞P系统,设计出相应的膜结构、膜规则、膜对象等,并用案例验证了P系统的可行性;三是将新型协同膜计算模型与遗传算法相结合,提出一种新型基于协同类细胞P系统的优化资源受限条件下的项目调度问题(RCPSP)的协同膜算法,并使用PSPLIB数据库的案例集验证该算法的有效性;四是将新型协同膜计算模型与遗传算法相结合,提出一种新型基于协同类细胞P系统的求解多执行模式资源受限条件下的项目调度问题(MRCPSP)的协同膜算法,并使用PSPLIB数据库的案例集验证该算法的有效性。
[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

【参考文献】