A parallel computing approach for scheduling Markovian project networks to maximize the expected net present value

This paper proposes a multithreaded parallel stochastic dynamic programming (SDP) approach for solving resource-unconstrained project scheduling problems with exponentially distributed activity durations, aiming to maximize the expected net present value (eNPV). These problems are typically modeled as Markov decision processes, in which optimal policies can be derived through SDP. However, traditional SDP methods are computationally intractable for large-scale instances due to the exponential growth of state and action spaces. To overcome this limitation, we develop a producer–consumer parallelization scheme that separates state enumeration from eNPV evaluation. The producer thread enumerates feasible states, while multiple consumer threads concurrently compute their optimal NPVs. Several optimized implementation strategies are proposed to improve cache efficiency, reduce synchronization overhead, and balance workload among threads. We further provide a theoretical analysis of the asymptotic properties of the parallel SDP, establishing the conditions under which the load-balancing efficiency and computational proportion of state enumeration converge. Comprehensive computational experiments confirm the validity of the theoretical analysis and demonstrate the scalability and robustness of the proposed approach. The parallel SDP achieves a maximum speedup factor of over 16 on a 24-cores processor for benchmark instances, and enables the exact solution of more complex instances that were previously intractable using serial SDP. The proposed framework is general and can easily be extended to other Markovian optimization problems that are characterized by high-dimensional state spaces.