Construction Project Planning
Resource-Constrained Project Scheduling
A construction manager must schedule activities — foundation, framing, plumbing, electrical, roofing — subject to precedence constraints and limited crews. This is the Resource-Constrained Project Scheduling Problem (RCPSP), one of the most important models in project management and Operations Research.
The Problem
Scheduling construction activities under real-world constraints
Consider a residential construction project. Each activity — pouring the foundation, framing the walls, installing plumbing and electrical, raising the roof, and finishing work — has a duration (in days) and requires specific resources (workers, cranes). Activities must obey precedence constraints: you cannot frame walls before laying the foundation, and the roof cannot go up before the framing is complete.
Resources are renewable: a team of 5 workers is available each day, and up to 2 cranes can be deployed simultaneously. Activities that do not share a precedence relationship can run in parallel — but only if the combined resource demand does not exceed capacity. The objective is to minimize the project duration (makespan), completing all activities as early as possible.
The RCPSP is strongly NP-hard, even with just two resource types. For a project with n activities and K renewable resource types, the number of feasible schedules grows combinatorially with the interactions between precedence and resource constraints. Exact methods are practical only for small instances; real projects rely on heuristic Schedule Generation Schemes (SGS) that build feasible schedules one activity at a time.
subject to
Sj ≥ Si + di // precedence: j cannot start before i finishes
Σi active at t rik ≤ Rk ∀ t, k // resource capacity per period
Si ≥ 0 // non-negative start times
Where Si is the start time of activity i, di is its duration, rik is its demand for resource k, and Rk is the capacity of resource k.
Try It Yourself
Edit activities, precedences, and resource capacities, then schedule the project
Construction Project Scheduler
6 Activities · 9 Precedences · Workers 5 · Cranes 2| # | Name | Duration (days) | Workers | Cranes |
|---|
| # | Predecessor | → | Successor |
|---|
| Algorithm | Project Duration (days) | Critical Path | Avg Resource Util. | Time |
|---|
The Algorithms
Schedule Generation Schemes for resource-constrained project scheduling
The RCPSP heuristics used here are Schedule Generation Schemes (SGS). An SGS builds a complete, feasible schedule by iteratively selecting an unscheduled activity and assigning it a start time that satisfies both precedence and resource constraints. The key difference between the Serial and Parallel schemes lies in how they choose what to schedule next.
Serial SGS — LFT
Heuristic · Active SchedulesActivities are prioritized by Latest Finish Time (ascending): activities that must finish earliest get scheduled first. The LFT is computed via a backward pass from the sink node.
- Compute LFT via backward pass: LF[sink] = critical path length; LF[i] = min over successors j of (LF[j] − dur[j])
- Sort eligible activities by LFT ascending
- For each activity in priority order: find the earliest time t where all predecessors are finished AND resource capacity allows it
- Schedule the activity at time t, update resource usage
Serial SGS — EST
Heuristic · Active SchedulesActivities are prioritized by Earliest Start Time (ascending): activities that can begin soonest get scheduled first. The EST is computed via a forward pass from the source node.
- Compute EST via forward pass: ES[source] = 0; ES[j] = max over predecessors i of (ES[i] + dur[i])
- Sort eligible activities by EST ascending
- For each activity in priority order: find the earliest feasible start time respecting precedence AND resource constraints
- Schedule the activity, update resource usage
Parallel SGS
Heuristic · Non-Delay SchedulesInstead of iterating over activities, the Parallel SGS iterates over time points. At each decision point, it schedules as many eligible activities as resources allow, then advances time to the next activity completion event.
- Start at t = 0. Find all eligible activities (predecessors complete, not yet scheduled)
- Among eligible, schedule those whose resource demand fits within remaining capacity (by LFT priority)
- Advance t to the next completion time of any running activity
- Repeat until all activities are scheduled
Why It's More Complex
Real-world construction scheduling goes far beyond the basic model
Real-World Complications
- Weather delays — Rain, snow, and extreme heat can halt outdoor activities, introducing stochastic durations and calendar-dependent scheduling
- Subcontractor availability — Specialized crews (electricians, plumbers) are shared across projects and available only on certain days
- Material delivery schedules — Activities cannot start until materials arrive, adding time-window constraints beyond simple precedence
- Permit dependencies — Inspections and regulatory approvals create external milestones that the scheduler cannot control
- Multi-project portfolios — Construction firms run many projects simultaneously, competing for the same pool of workers and equipment
- Cost-time tradeoffs (crashing) — Activities can be accelerated by adding resources, but at increasing cost. The time-cost tradeoff problem adds a budget dimension
- Stochastic durations — Activity times are uncertain, leading to robust and stochastic RCPSP variants with probabilistic completion guarantees
Key References
Foundational papers on resource-constrained project scheduling
- (2006). "Experimental investigation of heuristics for resource-constrained project scheduling." European Journal of Operational Research, 127(2), 394–407.
- (2010). "A survey of variants and extensions of the resource-constrained project scheduling problem." European Journal of Operational Research, 207(1), 1–14.
Need to optimize project scheduling?
From construction planning to software development pipelines, resource-constrained scheduling drives project efficiency. Let's discuss how mathematical optimization can accelerate your projects.