Efficient Rollout Algorithms for Resource-Constrained Project Scheduling with a Flexible Project Structure and Uncertain Activity Durations

Chunlai Yu, Xiaoming Wang () and Qingxin Chen
Additional contact information
Chunlai Yu: State Key Laboratory of Precision Electronic Manufacturing Technology and Equipment, Guangdong University of Technology, Guangzhou 510006, China
Xiaoming Wang: State Key Laboratory of Precision Electronic Manufacturing Technology and Equipment, Guangdong University of Technology, Guangzhou 510006, China
Qingxin Chen: State Key Laboratory of Precision Electronic Manufacturing Technology and Equipment, Guangdong University of Technology, Guangzhou 510006, China

Mathematics, 2025, vol. 13, issue 9, 1-25

Abstract: This study addresses the resource-constrained project scheduling problem with flexible structures and uncertain activity durations. The problem is formulated as a Markov decision process, with the optimal policy determined through stochastic dynamic programming. To mitigate the curse of dimensionality in large-scale problems, several approximate methods are proposed to derive suboptimal policies. In addition to traditional methods based on priority rules and metaheuristic algorithms, we focus on the application of rollout algorithms. To improve the computational efficiency of the rollout algorithms, only the best-performing priority rules are employed for action evaluation, and the common random numbers technique is also incorporated. Experimental results demonstrate that rollout algorithms significantly outperform priority rules and metaheuristics. The common random numbers technique not only enhances computational efficiency but also improves the accuracy of action selection. The post-rollout algorithm reduces computation time by 44.37% compared to the one-step rollout, with only a 0.02% performance gap. In addition, rollout algorithms perform more stably than other methods under different problem characteristics.

Keywords: RCPSP; flexible project structure; uncertain duration; rollout algorithm; suboptimal policy (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/9/1395/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/9/1395/ (text/html)

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:gam:jmathe:v:13:y:2025:i:9:p:1395-:d:1641757

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().