论文部分内容阅读
资源受限的项目调度问题(Resource-Constrained Project Scheduling Problem,RCPSP)广泛地存在于各行各业,不仅是项目管理实践的核心内容,也是运筹学的一个重要分支。合理的调度计划能够节约资源、缩短工期、获得较大的经济效益。在理论研究上,资源受限项目调度问题模型丰富,大部分属于NP-hard问题,求解困难,因此研究RCPSP具有重要的现实意义和理论价值。本论文围绕这个问题,分为两大部分：一个是受到水利工程建设项目的启发,提出了一种新的具有硬性时间约束的资源受限项目调度扩展模型,称之为具有禁止时间窗口的资源受限项目调度问题(Resource-Constrained Project Scheduling Problem with Forbidden Time Windows,RCPSP-FTW);二是在资源受限项目调度中引入数据包络分析技术,解决调度方案的选择问题。本论文的主要工作和创新点如下：1、建立了具有禁止时间窗口的资源受限项目调度问题的模型,详细说明了其特点。调整了经典的调度方案生成机制和基于多优先规则的启发式算法,使之适合于求解具有禁止时间窗口的资源受限项目调度问题。同时基于PSPLIB实例库数据,构建了具有禁止时间窗口约束的仿真实例,并使用它验证了基于多优先规则启发式算法的有效性。2、设计了两种求解具有禁止时间窗口的资源受限项目调度问题的元启发式算法。一种是遗传算法,根据问题特点提出了禁止时间窗口的交叉算子,并使用双对齐技术和精英保留机制改善解的质量。另一种是改进的类电磁算法,使用随机键和拓扑排序相结合的编码方式,改进了粒子电荷、合力以及粒子移动的方式并使用变邻域搜索作为局部搜索方法。仿真实验分别用一个简化的水利工程项目和大量仿真数据验证了两个算法的求解效果。实验表明这两种算法能够大大提高解的质量。根据实验结果也说明了禁止时间窗口和受到禁止时间窗口影响的活动分布是导致具有禁止时间窗口的资源受限项目调度问题工期波动的主要原因。3、使用了数据包络分析技术解决管理者面对众多候选的资源受限项目调度方案陷入选择困境的难题。项目调度问题本身具有三个相互矛盾的目标,分别是工期、成本和质量。实际中管理者对这三个目标的偏好并不统一,导致调度方案难以抉择。因此在资源受限项目调度中引入数据包络分析技术。利用一个多模式资源受限项目调度问题作为例子,说明两者如何结合。这为资源受限项目调度应用的扩展和实际的项目决策提供了一个新的思路。