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