Construction Project Scheduling
Resource-Constrained Project Scheduling · NP-Hard
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. This is RCPSP — strongly NP-hard — where precedence constraints and shared renewable resources make finding the shortest feasible schedule a combinatorial challenge.
Where This Decision Fits
Construction operations chain — the highlighted step is what this page optimizes
The Problem
Schedule construction activities under resource limits
A construction project consists of 15 activities — Foundation Excavation, Steel Erection, HVAC Rough-In, Electrical Wiring, Plumbing, Concrete Pour, Roofing, Exterior Cladding, Interior Framing, Drywall, Flooring, Painting, Elevator Install, Fire Safety, and Final Inspection — each with a known duration, a set of precedence links, and demands on 3 renewable resources: crane-hours, electricians, and concrete crews.
At any point in time, concurrent activities must not exceed the available capacity of any resource. The goal is to minimize the project makespan — the total time from groundbreaking to final inspection — while respecting all precedence and resource constraints.
subject to
sj ≥ si + pi // ∀ (i,j) ∈ E — precedence
Σ{j: sj≤t<sj+pj} rjk ≤ Rk // ∀ k, ∀ t — resource capacity
sj ≥ 0 // non-negative start times
Where pj is the duration of activity j, rjk is the demand of activity j for resource k, Rk is the capacity of resource k, and E is the set of precedence pairs.
See full RCPSP theory and all algorithmsTry It Yourself
Schedule construction activities and compare algorithms
Construction Scheduler
15 Activities · 3 ResourcesReady. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Makespan | Time |
|---|
The Algorithms
Schedule generation schemes and metaheuristics for RCPSP
Serial Schedule Generation Scheme (Serial SGS)
O(n² K) per scheduleActivities 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.
Parallel Schedule Generation Scheme (Parallel SGS)
O(n² K) per scheduleInstead 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.
Genetic Algorithm (Permutation Encoding)
Iterative · Population-basedA 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
Key References
Foundational works in resource-constrained project scheduling
- (1992). “A branch-and-bound procedure for the multiple resource-constrained project scheduling problem.” Management Science, 38(12), 1803–1818.
- (1998). “A competitive genetic algorithm for resource-constrained project scheduling.” Naval Research Logistics, 45(7), 733–750.
- (2006). “Experimental investigation of heuristics for resource-constrained project scheduling: An update.” European Journal of Operational Research, 174(1), 23–37.
- (1997). “PSPLIB — A project scheduling problem library.” European Journal of Operational Research, 96(1), 205–216.
- (2002). “Ant colony optimization for resource-constrained project scheduling.” IEEE Transactions on Evolutionary Computation, 6(4), 333–346.
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.