论文部分内容阅读
20世纪50年代,市场经济的发展开始进入了“快车道”,至此正式拉开了市场竞争的帷幕,现代项目的发展趋势也随之走向复杂化,对项目管理的要求早已不仅仅满足于单方面,低成本、短工期、高质量成了现代项目管理普遍追求的目标。而作为现代项目管理中的热点问题之一的资源受限项目调度问题(the resource-constrained project scheduling problem,RCPSP)更是受到 了国内外研究学者们的广泛关注和研究。它要求项目管理者在资源约束和活动时序约束的双重约束条件下,合理安排各个活动的开始时间和资源分配,来达成确定的优化目标。而目前国内对该经典问题的研究大都是建立在每个活动仅有一个固定执行模式的假设条件上,显然这并不符合实际,在现实中每个活动可能会有多种不同的执行模式。因此,本文讨论研究的是更具有实际意义和应用价值的多模式资源受限项目调度问题(the multi-mode resource-constrained project scheduling problem,MRCPSP)。多模式资源受限项目调度问题广泛存在于生产制造业、建筑业和软件行业中,是项目调度问题中的一类经典的NP-hard问题。相比于传统RCPSP问题,MRCPSP问题的特点非常突出,即活动存在多种可选择的执行模式,并且不同的模式包含了特定的执行时间,以及执行所需要不同类型和数量的资源。对该问题的研究不仅能为现代项目管理提供多面的方案,而且可以节约资源和资金,符合目前所倡导的资源节约型社会建设的要求。本文的主要内容基于改进遗传算法的MRCPSP问题的研究。首先介绍了资源受限项目调度问题、遗传算法和PSPLIB标准问题库的相关理论知识和国内外研究现状。接着根据MRCPSP问题的双重约束条件和活动有多种执行模式可供选择的特征,构建了总工期最优的数学模型。为了求解该模型,本文在传统遗传算法的基础上设计了全新的遗传算法——LPSGA(Level Project Scheduling Optimization based on Genetic Algorithm),其最大的特色是在编码操作中先对活动进行了分层操作以确定每个活动的层次级别,并且在算法进程中始终把级别小的活动放在前面,确保了活动的时序性,可以有效预防出现不可行解的情况,大大提高了算法的效率。同时为了迎合MRCPSP问题的特点,对算法的解码操作和包括交叉、变异在内的遗传操作进行了改进。在验证所提出的LPSGA算法的性能方面,本文首先利用PSPLIB标准问题库中的J18、J20测试集作为验证基准,将本文提出的LPSGA算法与另外四种传统启发式算法进行对比测试,结果表明该算法能有效且准确地求解MRCPSP问题。并且还将该算法应用到实际案例——日照钢铁大修项目中,证明了其具有实际应用价值。