Abstract: This study considers the scheduling of resource-constrained project with stochastic activity duration to maximize expected net present value. We first define the problem, and develop the corresponding optimization model. Then we design a stochastic dynamic programming algorithm for this problem according to its characteristics. Through analyzing the project network structure and relationship between optimal values of different states, we refine the state generation procedure and state optimal value calculation process. This accelerates the dynamic programming. We use 540 simulated instances to validate our algorithm and analyze the impact of network features on the performance of the algorithm. The experimental results show that the order strength of the project has an important impact on the efficiency of the algorithm: when the order strength is low, there are more states thus needs more time to figure out the optimal expected net present value.

Key words: stochastic activity duration, maximize expected net present value, resource-constrained projects, dynamic programming

摘要： 本文研究了随机活动工期下如何调度资源约束项目使得项目的期望净现值最大。首先对问题进行了界定,建立了相应的优化模型,其次针对问题的特点设计了一种动态规划算法。在算法设计的过程中,本文通过对项目网络图结构及不同状态最优值之间关系的分析,优化了动态规划算法状态的生成过程及状态最优值的求解过程,从而加快了算法的求解。使用随机生成的540个不同规模、不同结构的仿真案例对算法的有效性进行了验证,并分析了项目网络特征对算法效率的影响。实验发现:项目的次序强度对算法所需时间有着较大的影响,随着项目次序强度的减小,生成的状态数量会增加,从而计算时间也会增加。本文的研究可以为不确定环境下的项目调度提供决策支持。

关键词: 随机活动工期, 最大期望净现值, 资源约束项目, 动态规划算法