Time-Cost Tradeoff
Multi-Mode RCPSP · Crashing · NP-Hard
Construction · Schedule & Sequence · TacticalWhen a project is running behind, contractors face a classic decision: which activities should be crashed — executed faster at higher cost — to meet the deadline with the minimum extra spend? Kelley (1961) formalised this as the time-cost tradeoff problem (TCTP): each activity has a piecewise-linear cost-versus-duration curve, and an LP traces the entire Pareto frontier. The discrete multi-mode RCPSP (MRCPSP) — where each activity has 2–3 named modes (normal, expedited, crashed) — is the modern discrete variant, strongly NP-hard and a first-class member of the Hartmann & Briskorn variant landscape.
Where This Decision Fits
Schedule recovery — the highlighted step is what this page optimises
The Problem
Minimum-cost schedule compression under a deadline
Each activity \( i \in \{1, \ldots, n\} \) can be executed in one of \( M_i \) modes. Mode \( m \) has duration \( p_{im} \) and fixed cost \( c_{im} \); shorter-duration modes cost more (crash cost > normal cost). The planner chooses binary variables \( x_{im} \in \{0,1\} \) with \( \sum_m x_{im} = 1 \) (exactly one mode per activity) and start times \( s_i \ge 0 \). Precedence and renewable-resource constraints carry over from base RCPSP; resource demands \( r_{imk} \) now depend on mode too (a crashed activity typically uses more crews per day).
The standard objective is minimise total cost subject to a project deadline \( T \):
Setting \( T \) to different values and re-solving traces the time-cost Pareto front: the set of non-dominated (duration, cost) pairs. Kelley (1961) showed that when cost curves are continuous and piecewise-linear convex in duration, the problem becomes a parametric LP solvable in closed form — the entire Pareto front emerges from a single sequence of pivots. The discrete MRCPSP is strongly NP-hard (Sprecher & Drexl 1998).
See the base RCPSP formulation (no crashing)Try It Yourself
Pick a mode per activity; trace the Pareto front by varying the deadline
Time-Cost Tradeoff Solver
10 Activities · 3 Modes eachTighter deadlines force more crash modes — watch the minimum cost rise.
Click a mode chip to pin it manually; click Solve to optimise all modes.
Each dot is the minimum cost for a given deadline. The current deadline is highlighted.
Pick a scenario, drag the deadline slider, and click Solve.
The Algorithms
LP for convex cost curves, branch-and-bound or GA for discrete multi-mode
Kelley 1961 Parametric LP
O(n m) pivots on the time-cost-compression LPWhen each activity has a piecewise-linear convex cost-duration curve (a continuum of modes between normal and full crash), the entire Pareto front emerges from a single parametric LP — the critical path is identified, the cheapest crash along it is taken, the critical path is re-computed, and the process repeats until no further cost-effective compression is possible. Pedagogically elegant; the foundation every construction PM was taught as “crashing the critical path.”
Enumeration with Priority Rules
O( product Mi · n ) — full mode-vector searchFor small instances (say, up to 10 activities with 3 modes each → 59,049 mode vectors), exhaustive enumeration of mode combinations is tractable. Each mode vector is scheduled with a standard RCPSP heuristic (Serial SGS with LFT priority) to get a feasible makespan-and-cost pair. The Pareto front is extracted from the dominated set. This is what the in-page solver uses to get a provably optimal cost for each target deadline.
Multi-mode Genetic Algorithm
Iterative · population on (mode-vector, activity-list) pairsHartmann (2001) introduced a two-part chromosome GA for MRCPSP: one half is the activity list (priority order), the other half is the mode vector. Standard precedence-preserving crossover and mode-swap mutation. Scales to the PSPLIB MMLIB benchmark suite (up to 30 activities, 3 modes) with <1% gap to optimum on average.
Real-World Complexity
Why construction crashing goes beyond textbook TCTP
Beyond Textbook TCTP
- Indirect costs — Overheads, site supervision, and owner penalties add a decreasing cost function in total duration that the classical TCTP objective doesn't capture directly. The combined cost curve is U-shaped.
- Non-convex cost curves — Discrete modes with step changes (single-shift → double-shift) violate the convexity assumption that makes Kelley's LP exact. In practice, the discrete MRCPSP is the right model.
- Stochastic durations — Crashed modes are riskier: higher variance in realised durations. Robust TCTP incorporates this.
- Quality penalties — Some crashing reduces quality (rushed concrete cure times, compressed inspections); the Time-Cost-Quality Tradeoff (TCQT) is a three-axis extension (Babu & Suresh 1996).
- Contractor incentives — Early-completion bonuses and late penalties per day create a staircase objective rather than a monotone one; the optimal schedule may deliberately sit at an inflection point of the bonus curve.
- Cascading crash effects — Crashing activity A may open up a new critical path through B; the LP handles this automatically, but discrete-mode heuristics must re-evaluate after every decision.
Related RCPSP Variants
TCTP is one of >150 variants catalogued by Hartmann & Briskorn (2022)
Key References
Cited above · DOIs & permanent URLs
Need to optimise your construction schedules?
From time-cost tradeoff to resource-constrained scheduling and cash-flow planning, mathematical modelling can transform construction recovery decisions. Let's discuss how Operations Research can work for you.