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

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