Construction & Infrastructure
Scheduling · Procurement · Site Selection
From the invention of CPM and PERT in the late 1950s for DuPont plant maintenance and the Polaris missile programme, to modern NP-hard Resource-Constrained Project Scheduling Problems (RCPSP) governing billion-dollar infrastructure projects — operations research has shaped how we plan, procure, and build the physical world.
The Resource-Constrained Project Scheduling Problem (RCPSP) assigns start times to activities that have precedence constraints (activity B cannot begin until activity A finishes) and share renewable resources (cranes, crews, concrete pumps) with limited per-period availability. RCPSP is NP-hard in the strong sense (Blazewicz et al., 1983), meaning no polynomial-time algorithm is known. Modern construction projects with hundreds of activities rely on heuristic priority rules, meta-heuristics, or CP/MIP solvers to minimise the project makespan — the total duration from groundbreaking to completion.
Problem type: Combinatorial scheduling with precedence and resource constraints. Assign a start time to each activity to minimise the project makespan, subject to finish-to-start precedence arcs and per-period resource capacity limits.
s.t. S_j ≥ S_i + d_i ∀ (i,j) ∈ E // precedence
Σ{i: S_i≤t<S_i+d_i} r_ik ≤ R_k ∀ k,t // resource cap
S_i ≥ 0 ∀ i // non-negative starts
RCPSP Solver
- Kelley, J.E. & Walker, M.R. (1959). Critical-Path Planning and Scheduling. Proceedings of the Eastern Joint Computer Conference, 160-173. Published
- 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. Published
- 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. Published
Construction projects consume dozens of material types — concrete, steel rebar, lumber, aggregates, piping — each with time-varying demand driven by the project schedule. Ordering too early ties up capital and storage space; ordering too late halts work crews. The dynamic lot-sizing problem determines when and how much to order each material to minimise the sum of fixed ordering costs, unit purchase costs, and per-period holding costs. Wagner & Whitin (1958) proved that an optimal policy exists where orders arrive exactly when inventory reaches zero, enabling efficient O(T²) dynamic programming. The Silver-Meal heuristic (1973) provides near-optimal results in O(T) time per item, making it practical for multi-material procurement planning.
Problem type: Dynamic lot-sizing / economic order quantity variant. For each material, determine order quantities across T periods to minimise the total of fixed ordering costs plus variable holding costs, subject to satisfying all period demands with no backorders.
s.t. I_t = It-1 + Q_t - d_t ∀ t // inventory balance
Q_t ≤ M · δ_t ∀ t // order indicator
I_t ≥ 0, δ_t ∈ {0,1} // no backorders
Lot-Sizing Solver
- Wagner, H.M. & Whitin, T.M. (1958). Dynamic Version of the Economic Lot Size Model. Management Science, 5(1), 89-96. Published
- Silver, E.A. & Meal, H.C. (1973). A Heuristic for Selecting Lot Size Quantities for the Case of a Deterministic Time-Varying Demand Rate and Discrete Opportunities for Replenishment. Production and Inventory Management, 14(2), 64-74. Published
- Bitran, G.R. & Yanasse, H.H. (1982). Computational Complexity of the Capacitated Lot Size Problem. Management Science, 28(10), 1174-1186. Published
All Construction Applications
Browse the complete collection