Construction Project Scheduling

Resource-Constrained Project Scheduling · NP-Hard

Construction · Schedule & Sequence · Tactical

Schedule overruns cost the average commercial construction project 20–30% above baseline, with cascading penalties of €5K–€25K per day of delay. Every project kickoff, a construction scheduler must sequence 30–100 activities under crane, crew, and equipment constraints. The Resource-Constrained Project Scheduling Problem (RCPSP) — in Pritsker, Watters & Wolfe's (1969) canonical zero-one formulation — is strongly NP-hard (Blazewicz, Lenstra & Rinnooy Kan 1983); Hartmann & Briskorn (2010, 2022) catalogue more than 150 variants in continuous active development. This page presents the base single-mode problem; links to MRCPSP, SRCPSP, resource leveling, and linear scheduling appear below.

Where This Decision Fits

Construction operations chain — the highlighted step is what this page optimizes

Site SelectionLocation & zoning
→
Portfolio SelectionProject prioritization
→
Project SchedulingSequence activities
→
ProcurementMaterials & contracts
→
Site OperationsExecution & QC

The Problem

Schedule construction activities under precedence and renewable-resource limits

A construction project is a directed acyclic graph of activities indexed by \( i \in \mathcal{V} = \{0, 1, \ldots, n, n{+}1\} \), where activities 0 and n+1 are dummy source and sink nodes of zero duration, and 1, \ldots, n are the real construction activities (foundation pours, steel erection, cladding, MEP rough-ins, finishes, etc.). Each real activity \( i \) has a processing time \( p_i \in \mathbb{Z}_{\ge 0} \), precedence constraints encoded by arc set \( \mathcal{E} \subseteq \mathcal{V} \times \mathcal{V} \), and demands \( r_{ik} \) for \( K \) renewable resources (crane-hours, electrician crews, concrete crews, etc.) with per-period capacities \( R_k \).

The decision variables are the start times \( s_i \ge 0 \). At every point in time, the cumulative demand of all activities in progress must not exceed any resource capacity. The objective is to minimise the project makespan \( s_{n+1} \) — the total time from groundbreaking to handover. This is the canonical Pritsker, Watters & Wolfe (1969) zero-one formulation, later standardised under the \( PS \mid prec \mid C_{\max} \) notation of Brucker et al. (1999):

RCPSP — \( PS \mid prec \mid C_{\max} \) $$ \min \; s_{n+1} $$ $$ \text{s.t.} \quad s_j \ge s_i + p_i \quad \forall (i,j) \in \mathcal{E} $$ $$ \sum_{\,i \,:\, s_i \le t < s_i + p_i\,} r_{ik} \; \le \; R_k \quad \forall k \in \{1,\ldots,K\}, \; \forall t \ge 0 $$ $$ s_i \ge 0, \quad s_0 = 0 \quad \forall i \in \mathcal{V} $$

The first constraint enforces finish-to-start precedence; the second enforces per-period renewable-resource capacity at every time instant; the third bounds starts non-negatively with the source activity anchored at zero. Blazewicz, Lenstra & Rinnooy Kan (1983) proved RCPSP is strongly NP-hard by reduction from 3-partition, meaning no polynomial-time exact algorithm is known. Practical construction instances with 30–300 activities are solved with heuristic Schedule Generation Schemes (SGS) and metaheuristics — detailed below.

See full RCPSP theory and all algorithms

Try It Yourself

Schedule construction activities and compare algorithms

Construction Scheduler

15 Activities · 3 Resources
Choose a Scenario
Activities
Resource Capacities
Algorithm
Gantt Chart
Resource Usage Over Time

Ready. Click “Solve & Compare All Algorithms” to run.

Comparison
AlgorithmMakespanTime
Schedule Detail
Schedule details will appear here after solving.

The Algorithms

Schedule generation schemes and metaheuristics for RCPSP

Heuristic

Serial Schedule Generation Scheme (Serial SGS)

O(n² K) per schedule

Activities are scheduled one at a time in priority order. For each activity, find the earliest feasible start time that satisfies both precedence constraints (all predecessors finished) and resource constraints (no resource capacity is exceeded). Serial SGS generates active schedules — no activity can be started earlier without delaying another.

Heuristic

Parallel Schedule Generation Scheme (Parallel SGS)

O(n² K) per schedule

Instead of scheduling one activity at a time, Parallel SGS advances through time steps. At each time point, it identifies all eligible activities and schedules as many as possible without violating resource limits. This generates non-delay schedules — no resource is ever left idle when an eligible activity could use it.

Metaheuristic

Genetic Algorithm (Permutation Encoding)

Iterative · Population-based

A population of activity-list permutations evolves through selection, crossover (precedence-preserving), and mutation. Each chromosome is decoded via Serial SGS to produce a feasible schedule. Introduced for RCPSP by Hartmann (1998) and refined by Kolisch & Hartmann (2006).

Real-World Complexity

Why construction scheduling goes beyond the basic RCPSP model

Beyond Basic RCPSP

  • Multi-mode execution — Activities can be performed in different modes trading time for cost (MRCPSP)
  • Generalized precedence relations — Min/max time lags between activities (RCPSP/max)
  • Multi-skill resources — Workers have different qualifications; a plumber cannot substitute for an electrician
  • Stochastic durations — Weather delays, permit hold-ups, and material delivery variance
  • Non-renewable resources — Budget and materials are consumed, not renewed each period
  • Multiple objectives — Minimizing makespan, cost, resource leveling, and risk simultaneously
  • Activity preemption — Some activities can be interrupted; others (e.g., concrete pour) cannot

Extensions & Related Variants

The RCPSP genealogy — each branch is a page on this site

Hartmann & Briskorn (2010, 2022) organise the RCPSP variant landscape along three orthogonal axes: activity model (single-mode \( \to \) multi-mode, preemptive, setup times), temporal constraints (finish-start precedence \( \to \) generalised min/max time lags), and resource model (renewable \( \to \) doubly-constrained, partially renewable, cumulative). The sub-applications on this site explore the most construction-relevant branches:

  • MRCPSP — multi-mode / time-cost tradeoff. Activities executable in several modes trading duration for cost (crashing). → Open Time-Cost Tradeoff
  • SRCPSP — stochastic durations. \( p_i \) is a random variable; proactive-reactive buffering per Herroelen & Leus (2005). → Open Stochastic RCPSP
  • Resource leveling. Same precedence + resource constraints, different objective: minimise resource peak or variance rather than makespan. → Open Resource Leveling
  • Linear / LOB scheduling. Activities repeated at successive locations (floors, stations, km-posts); keep crews continuously working. → Open Linear Scheduling
  • RCPSP/max — generalised precedence. Min and max time lags between activities instead of plain finish-to-start (Bartusch et al. 1988). Not yet modelled here; see base RCPSP plus extensions.
  • RCMPSP — multi-project. Several RCPSPs sharing a resource pool, dominant at the portfolio level. Open research frontier; not yet built.

Cross-domain siblings with the same base mathematical structure: agriculture's harvest processing line (flow shop) and farm equipment scheduling (parallel machine); healthcare's OR theatre scheduling (resource-constrained with elective vs. emergency priorities).

Key References

Cited above · DOIs & permanent URLs

Pritsker, A. A. B., Watters, L. J., & Wolfe, P. M. (1969).
“Multiproject scheduling with limited resources: a zero-one programming approach.”
Management Science, 16(1), 93–108. (Canonical RCPSP formulation.) doi:10.1287/mnsc.16.1.93
Blazewicz, J., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1983).
“Scheduling subject to resource constraints: classification and complexity.”
Discrete Applied Mathematics, 5(1), 11–24. (RCPSP strongly-NP-hardness proof.) doi:10.1016/0166-218X(83)90012-4
Kelley, J. E., & Walker, M. R. (1959).
“Critical-path planning and scheduling.”
Proceedings of the Eastern Joint Computer Conference, 160–173. (CPM origin at DuPont — precursor to RCPSP without resource constraints.)
Brucker, P., Drexl, A., Möhring, R., Neumann, K., & Pesch, E. (1999).
“Resource-constrained project scheduling: notation, classification, models and methods.”
European Journal of Operational Research, 112(1), 3–41. (\( \alpha \mid \beta \mid \gamma \) notation standardisation.) doi:10.1016/S0377-2217(98)00204-5
Demeulemeester, E., & Herroelen, W. (1992).
“A branch-and-bound procedure for the multiple resource-constrained project scheduling problem.”
Management Science, 38(12), 1803–1818. doi:10.1287/mnsc.38.12.1803
Hartmann, S. (1998).
“A competitive genetic algorithm for resource-constrained project scheduling.”
Naval Research Logistics, 45(7), 733–750. (The activity-list GA implemented on this page.) doi:10.1002/(SICI)1520-6750(199810)45:7<733::AID-NAV5>3.0.CO;2-C
Kolisch, R., & Sprecher, A. (1997).
“PSPLIB — a project scheduling problem library.”
European Journal of Operational Research, 96(1), 205–216. (The j30/j60/j90/j120 benchmark sets.) doi:10.1016/S0377-2217(96)00170-1
Kolisch, R., & Hartmann, S. (2006).
“Experimental investigation of heuristics for resource-constrained project scheduling: an update.”
European Journal of Operational Research, 174(1), 23–37. doi:10.1016/j.ejor.2005.01.065
Hartmann, S., & Briskorn, D. (2010).
“A survey of variants and extensions of the resource-constrained project scheduling problem.”
European Journal of Operational Research, 207(1), 1–14. doi:10.1016/j.ejor.2009.11.005
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. (Most recent canonical RCPSP survey, with >150 variants catalogued.) doi:10.1016/j.ejor.2021.05.004

Need to optimize your construction schedules?

From resource-constrained scheduling to multi-project portfolio optimization, mathematical modeling can transform your construction planning. Let’s discuss how Operations Research can work for you.

Connect on LinkedIn
Disclaimer
Data shown is illustrative. Activity names, durations, precedence relations, and resource capacities are representative scenarios for educational purposes and do not reflect any specific construction project.
Back