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

Xiaoming Wang, Guojian Zhou, Roel Leus and Stefan Creemers ()
Additional contact information
Stefan Creemers: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3359, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: 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.

Keywords: Project scheduling; Markovian networks; Dynamic programming; Parallel computing (search for similar items in EconPapers)
Pages: 16
Date: 2026-04-08
Note: In: European Journal of Operational Research, 2026
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3359

DOI: 10.1016/j.ejor.2026.04.012

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().