Stochastic RCPSP

SRCPSP · Uncertain Durations · Proactive-Reactive

Construction · Schedule & Sequence · Tactical

Construction durations are chronically uncertain — weather, permits, subcontractor delivery, and learning-curve effects all distort the tidy deterministic schedule. The Stochastic Resource-Constrained Project Scheduling Problem (SRCPSP) models each activity duration as a random variable $ \tilde p_i $ and asks: what schedule minimises expected makespan, or maximises the probability of meeting the owner's deadline? Herroelen & Leus (2005) surveyed the landscape and distinguished proactive strategies (insert time buffers during baseline scheduling to absorb variance) from reactive ones (right-shift activities as durations are realised during execution). The page lets you run Monte Carlo simulations under both policies.

Where This Decision Fits

Schedule risk management — the highlighted step is what this page optimises

Baseline RCPSPDeterministic schedule

→

Duration UncertaintyVariance per activity

→

Stochastic RCPSPProactive / reactive

→

Resource LevelingUnder buffers

→

Execute & Re-planRepair as needed

The Problem

Makespan distribution under uncertain durations

Take the deterministic RCPSP of the previous page and replace fixed durations $ p_i $ with random variables $ \tilde p_i \sim F_i $. Construction practice typically uses a beta, triangular, or lognormal distribution with a point estimate $ \mu_i $ (the deterministic duration) and a standard deviation $ \sigma_i = \kappa_i \mu_i $, where $ \kappa_i $ is the coefficient of variation. For low-risk civil work $ \kappa \approx 0.1 $; for permit-heavy or weather-exposed activities it can exceed $ 0.4 $.

A common objective is to minimise the expected makespan given a policy $ \pi $ (the rule that decides when each activity starts given observed durations so far):

SRCPSP — expected-makespan objective $$ \min_{\pi \in \Pi} \;\; \mathbb{E}\!\left[\, s_{n+1}(\pi, \tilde{\mathbf{p}}) \,\right] $$ $$ \text{s.t.} \quad s_j(\pi, \mathbf{p}) \ge s_i(\pi, \mathbf{p}) + p_i \quad \forall (i,j) \in \mathcal{E}, \; \forall \mathbf{p} $$ $$ \sum_{i\,:\,s_i \le t < s_i + p_i}\; r_{ik} \;\le\; R_k \quad \forall k, \; \forall t, \; \forall \mathbf{p} $$

The policy space $ \Pi $ is the key modelling choice:

Deterministic (naive): schedule on mean durations $ \mu_i $; right-shift only when a predecessor actually finishes late.
Proactive buffered: schedule on mean durations plus a time buffer $ b_i $ per activity, sized so that cumulative variance on the critical path is absorbed. Van de Vonder et al. (2007) propose the Starting Time Criticality (STC) heuristic.
Reactive dispatch: at each decision epoch, re-run Serial SGS on the remaining activities with the realised durations so far. Higher computational cost per realisation, but usually the lowest expected makespan.

Chance-constrained alternative: $ \Pr(s_{n+1} \le T) \ge 1 - \alpha $ — the deadline must be met with probability $ 1 - \alpha $ (typical owner requirements: $ \alpha = 0.1 $ or $ 0.05 $). This becomes a $ (1-\alpha) $-quantile constraint on the makespan CDF.

See the deterministic RCPSP formulation

Try It Yourself

Monte Carlo over uncertain durations under three policies

Stochastic RCPSP Simulator

10 Activities · 1000 replications

Choose a Scenario

Uncertainty level (coefficient of variation $ \kappa $)

\u03ba = 0.20

0.1 = civil-works typical, 0.2 = average, 0.4+ = permit/weather exposed.

Owner deadline T (days)

45 d

Scheduling policy

Deterministic (mean)

Proactive (STC buffers)

Reactive (dispatching)

Makespan distribution

Completion probability vs. deadline (CDF)

Pick a scenario, set uncertainty + deadline, choose a policy, and click Run.

The Algorithms

Three canonical policies plus Monte Carlo evaluation

Naive Baseline

Deterministic (mean-based)

O(n\u00b2) per replication — Serial SGS on \u03bc

Schedule every activity at its mean duration. During simulated execution, push any successor that the realised finish of its predecessor would push — right-shifting the tail. Simple but chronically over-optimistic; the actual makespan is usually 15–30% longer than the deterministic CPM result when variance is material.

Proactive

Starting-Time Criticality (STC) Buffers

O(n\u00b2 + R · n) — Monte Carlo sizing, R reps

Van de Vonder, Demeulemeester & Herroelen (2007) score each activity's starting-time criticality — the probability that the activity's start is delayed beyond the deterministic baseline — using a short pre-simulation. Buffers are inserted in front of the highest-STC activities, sized to hit a target on-time completion probability. Robust to execution noise; worse expected makespan than reactive dispatching but predictable.

Reactive

Right-Shift Dispatching

O(n\u00b2 \u00b7 R) — re-schedule per realisation

At every decision epoch (activity finish event), re-run Serial SGS with realised durations so far and a priority rule (LFT, MTS, GRPW). Ballestín (2007) showed reactive policies dominate proactive ones in expected makespan when $ \kappa \ge 0.2 $; at lower uncertainty the proactive schedule is competitive and gives owners a stable delivery date.

Real-World Complexity

Why construction uncertainty goes beyond basic SRCPSP

Beyond Independent Durations

Correlated durations — Weather affects all concurrent outdoor activities; supply-chain disruptions hit related material-dependent activities together. Independent sampling is a convenient lie.
Bayesian updating — As the project progresses, observations refine the duration distribution of future activities (same trade, same subcontractor, same crew).
Resource uncertainty — Crew availability also fluctuates (absenteeism, competing projects). Robust extensions add stochastic $ R_k $ on top of stochastic $ p_i $.
Partial preemption — Activities can sometimes be paused (formwork cures, inspections pending) without restart cost; the scheduler can exploit this for cheap robustness.
Learning curves — Repetitive activities (floor framings, highway paving stations) get faster with experience, so durations are sequence-dependent — not independent draws.
Rare-but-catastrophic events — Strikes, floods, design-change orders. Heavy-tailed distributions (Pareto) dominate expected-makespan calculations; percentile objectives (P₉₅, P₉₉) are a saner metric than the mean.

Related RCPSP Variants

SRCPSP is the uncertainty arm of the Hartmann-Briskorn taxonomy

RCPSP — deterministic base. The zero-variance limit of this page. Start here before layering uncertainty. → Open Project Scheduling

Time-Cost Tradeoff (MRCPSP). Crashing in expectation — mode selection that accounts for both duration and risk. Often paired with stochastic models. → Open Time-Cost Tradeoff

Resource Leveling. Once buffers are inserted, the resource histogram reshapes; levelling post-processes the buffered schedule. → Open Resource Leveling

Linear / LOB Scheduling. Repetitive construction adds sequence-dependent learning effects; stochastic LOB is an open research frontier. → Open Linear Scheduling

Cash-Flow Optimisation. Under uncertain durations, cash draw schedules need to carry their own buffers — a second-order stochastic problem. → Open Cash Flow

Robust / DRO RCPSP. Distributionally robust variants minimise worst-case expected makespan over a family of distributions. Active research; not yet modelled here.

Key References

Cited above · DOIs & permanent URLs

Herroelen, W., & Leus, R. (2005).

“Project scheduling under uncertainty: survey and research potentials.”

European Journal of Operational Research, 165(2), 289–306. (The canonical SRCPSP survey.) doi:10.1016/j.ejor.2004.04.002

Ballestín, F. (2007).

“When it is worthwhile to work with the stochastic RCPSP?”

Journal of Scheduling, 10(3), 153–166. (Empirically compares deterministic vs. stochastic policies as a function of variance.) doi:10.1007/s10951-007-0012-1

Van de Vonder, S., Demeulemeester, E., & Herroelen, W. (2007).

“A classification of predictive-reactive project scheduling procedures.”

Journal of Scheduling, 10(3), 195–207. (The Starting Time Criticality buffer-sizing heuristic.) doi:10.1007/s10951-007-0011-2

Möhring, R. H. (1984).

“Minimizing costs of resource requirements in project networks subject to a fixed completion time.”

Operations Research, 32(1), 89–120. (Early stochastic extensions of PERT/RCPSP.) doi:10.1287/opre.32.1.89

Igelmund, G., & Radermacher, F. J. (1983).

“Preselective strategies for the optimization of stochastic project networks under resource constraints.”

Networks, 13(1), 1–28. (Foundational work on policy-based SRCPSP.) doi:10.1002/net.3230130102

Stork, F. (2001).

Stochastic Resource-Constrained Project Scheduling.

PhD thesis, TU Berlin. (Canonical dissertation defining robustness measures for SRCPSP.) doi:10.14279/depositonce-326

Artigues, C., Leus, R., & Talla Nobibon, F. (2013).

“Robust optimization for resource-constrained project scheduling with uncertain activity durations.”

Flexible Services and Manufacturing Journal, 25(1-2), 175–205. (Robust-optimization formulations under interval uncertainty.) doi:10.1007/s10696-012-9147-2

Demeulemeester, E., & Herroelen, W. (2011).

Robust Project Scheduling.

Foundations and Trends in Technology, Information and Operations Management, 3(3–4), 201–376. (Book-length treatment of robust / stochastic RCPSP.) doi:10.1561/0200000021

Hartmann, S., & Briskorn, D. (2022).

“An updated survey of variants and extensions of the resource-constrained project scheduling problem.”

European Journal of Operational Research, 297(1), 1–14. (Stochastic and robust sections.) doi:10.1016/j.ejor.2021.05.004

Need to schedule under uncertainty?

From stochastic project scheduling to time-cost tradeoff and robust cash-flow planning, mathematical modelling translates construction variance into predictable delivery. Let's discuss how Operations Research can work for you.

Connect on LinkedIn

Disclaimer

Activity durations, variances, and Monte Carlo replications are illustrative values for pedagogical comparison of policies. Real construction uncertainty quantification requires project-specific historical data, expert elicitation, and correlation modelling.