论文部分内容阅读
计划评审技术(Program Evaluation and Review Technique，PERT)是在一个给定的项目中对潜在任务进行分析的一种方法。其建立的目的是为了简化大而复杂的项目的计划，合理分配任务的时间。
由于PERT在项目执行过程中资源限制通常被忽略。因此，在资源受限的情况下根据PERT编制的项目调度计划经常无法顺利实施，这时，便产生了资源受限的项目调度问(Resource Constrained Project Scheduling Problem，RCPSP)。
RCPSP是计划调度中的重要问题，要求在项目时序约束和资源约束的条件约束下，安排所有项目的开始时间和结束时间，以达到某种目标的最优化，或者使多种目标均衡化。在理论上来说，该问题属于NP-hard问题，模型非常丰富，并且有许多的组合优化问题属于RCPSP的特殊情况。此外，RCPSP广泛存在于建筑工程，软件开发，飞机和轮船制造等生产中。因此，研究RCPSP具有十分重要的理论和现实意义。
在工程项目计划管理的实施过程中，项目进度计划和优化资源配置是两个核心问题。自PERT诞生以来，时间/资源均衡双目标优化问题已研究了多年，而且已证明此类问题是个非常困难的组合问题。现在许多学者提出了一些解决方案，包括线性规划、整数规划、动态规划和遗传算法以及其他的启发式方法。这些方法可以划分为两大类：一类是精确法，另一类是近似方法，后者较前者减少了计算量。但是，由于项目调度问题本身的复杂性，对于经典的RCPSP，这些方法大多是针对一个项目进行调度优化，而针对资源受限多项目双目标调度问题的研究则非常少，特别是对数十个项目同时进行调度优化。
本文针对PSO算法在资源受限多项目调度中的应用展开研究，主要研究如下：
(1)对资源受限多项目调度问题和PSO算法进行了分析研究。详细介绍了资源受限项目调度问题的分类和求解算法，描述了资源受限多项目调度问题。对基本的PSO算法进行了详细的介绍，并将其与其它进化算法行了比较说明。
(2)由于PSO算法收敛过早，易陷入局部最优，并且当算法采用典型的线性递减惯性权重时，在算法执行初期，具有较强的全局搜索能力，如果最优点不能被找到，随着惯性权重的减小，局部搜索能力将加强，易陷入局部极值。因此，结合模拟退火算法全局收敛性好，执行时间较长，步长较小的线性递减惯性权重变化幅度较小，不易陷入局部最优的特点，本文提出了一种适合于资源受限多项目调度的PSO算法。
(3)将改进的PSO算法用于求解资源受限多项目调度问题和资源受限多项目调度的时间/资源均衡双目标优化问题。最后，通过大数据量的仿真试验验证该算法的有效性，并和其它算法进行比较。实验结果显示，将改进的PSO算法用于求解资源受限多项目调度问题时，求解所得的最好目标函数值为48.68，而使用其它算法求解所得的最好目标函数值为59.44。当改进的PSO算法用于求解资源受限多项目调度的时间/资源均衡双目标优化问题时，对100个项目进行求解，算法平均执行时间为131.474秒，而相同条件下，未改进的PSO算法的平均执行时间为144.946秒。这说明，本文提出的改进的PSO算法在处理大规模数据时的优化效果比其他算法要好，由此可以证明本算法模型的正确性与可行性。