基于遗传算法的资源约束项目调度问题优化及应用研究

发布时间：2018-10-16 10:20

【摘要】：资源约束项目调度问题(RCPSP)是一类重要的调度问题,它主要研究项目在满足项目活动时序约束和资源约束的条件下,对项目中的活动的开始时间和完成时间进行合理安排,以达到某一管理目标的最优化。如:工期最短,成本最小,资源均衡等。该问题理论上属于NP-hard问题,模型丰富,许多组合优化问题是RCPSP的特殊情形。此外RCPSP也广泛存在于建筑行业,软件行业,制造业等行业中。因此研究RCPSP具有重要的理论意义和现实意义。本文主要研究内容如下:(1).针对经典RCPSP,本文将遗传算法和新颖的教学算法相结合,设计了一种新的用于求解经典资源约束项目调度问题的智能优化算法——教学遗传算法。此算法根据教学算法过程中的两阶段搜索方法设计了一种二次交叉操作,第一次交叉在教师个体与学生个体之间,第二次交叉在学生个体与学生个体之间以一定的交叉概率进行,这种交叉操作的设计使得教学遗传算法能有效的跳出局部最优,从而得到更好的调度方案。实验部分选用标准数据库PSPLIB中的经典资源约束项目调度问题集进行验证算法的有效性,结果表明优于现有文献中已有的一种算法。(2).在实际的项目调度中,项目各活动在执行时往往存在一种以上的执行模式,每种模式都代表一组资源需求量和相应持续时间的组合,不同的持续时间会有不同的资源需求,因此多执行模式资源约束项目调度问题作为经典RCPSP的扩展,更具有实际意义。针对MRCPSP本文提出了一种混合遗传算法。该算法在计算之前,需要对项目中数据进行预处理,然后基于拓扑排序产生初始种群,最后,为了改善遗传算法的局部搜索能力,设计了一种基于邻域搜索的变异操作。实验部分对标准数据库中的基准问题J18,J20进行了测试,验证了算法的有效性。(3).理论和算法最终都是要为实际服务的,要为现代项目中的项目管理问题提供实际解决方案。为验证本文所提出的混合遗传算法能否应用于具体实际,针对MRCPSP问题进行案例研究,结果表明该智能算法不仅丰富了多执行模式RCPSP的求解方法,而且拓宽了遗传算法的应用领域。
[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.
【学位授予单位】：湖南工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：F282;TP18

【相似文献】