🧩 Constraint Solving POTD:Resource-Constrained Project Scheduling (RCPSP)

[github-actions[bot]]

Constraint Solving — Problem of the Day · 2026-03-23 · Category: Scheduling

---

Problem Statement

You are managing a construction project with n activities (tasks). Each activity has a fixed duration and requires a certain amount of each renewable resource (e.g., workers, cranes, machines) while it runs. Resources are shared and have a limited daily capacity. Activities also have precedence constraints — some tasks cannot begin until others have finished.

Goal: Schedule all activities (assign a start time to each) so that:

1. All precedence constraints are satisfied.
2. At no point in time does cumulative resource usage exceed any resource's capacity.
3. The makespan (the finish time of the last activity) is minimized.

Concrete Instance (5 activities, 2 resources)

Resources: R1 = 3 units, R2 = 2 units.

Activity	Duration	R1 req	R2 req	Must follow
A	3	2	0	—
B	2	1	1	—
C	4	2	1	A
D	2	1	2	B
E	3	1	0	C, D

Input: durations d_i, resource requirements r_ik, capacities R_k, precedence pairs (i,j).
Output: Start times s_i ≥ 0 for each activity, minimizing max_i(s_i + d_i).

---

Why It Matters

• Construction & engineering projects: Allocating crews, equipment, and materials across overlapping tasks while respecting dependencies is literally RCPSP — it underlies every modern project management tool (MS Project, Primavera).
• Semiconductor manufacturing: Scheduling wafer fabrication steps with constrained machine capacity is a large-scale RCPSP instance where a few percent improvement in makespan translates to millions of dollars.
• Software release planning: Assigning developer capacity across features with technical dependencies maps directly onto this model.

---

Modeling Approaches

Approach 1 — Constraint Programming with cumulative

The most natural CP formulation uses a time-point model with the cumulative global constraint.

Decision variables:

s_i ∈ [0..UB]   for each activity i   (start time)
```
where `UB` is an upper bound on the makespan (e.g., sum of all durations).

**Constraints:**
```
// Precedence
s_j ≥ s_i + d_i          for each (i,j) ∈ precedence arcs

// Resource capacity — one cumulative per resource k
cumulative([s_i], [d_i], [r_ik], R_k)   for each resource k

// Makespan objective variable
makespan = max_i(s_i + d_i)
```

The `cumulative(starts, durations, heights, capacity)` global constraint enforces that, at every time point `t`, the total height of all tasks active at `t` does not exceed `capacity`. Solvers implement this with **Edge-Finding**, **Not-First/Not-Last**, and **Energetic Reasoning** propagators, giving very strong pruning.

**Trade-offs:** Highly expressive; propagation is very strong. Scales well in practice due to global constraint propagators. Less competitive on pure lower-bound quality versus LP relaxations.

---

#### Approach 2 — Mixed-Integer Programming (MIP), Time-Indexed Formulation

A classical MIP formulation introduces binary decision variables indexed by activity and time.

**Decision variables:**
```
x_it ∈ {0,1}   = 1 if activity i starts at time t
```

**Constraints:**
```
// Each activity starts exactly once
∑_t  x_it = 1                                       ∀i

// Precedence
∑_t  t · x_jt  ≥  ∑_t  t · x_it  +  d_i           ∀(i,j) ∈ prec

// Resource capacity at each time point τ
∑_i  r_ik · ∑_{t=τ-d_i+1}^{τ}  x_it  ≤  R_k       ∀k, τ

// Makespan
makespan ≥ ∑_t (t + d_i) · x_it                    ∀i

Trade-offs: Yields a strong LP relaxation that provides good lower bounds; compatible with commercial solvers (Gurobi, CPLEX). However, the number of variables grows as O(n · UB), making it expensive for large horizons.

---

Approach 3 — Hybrid CP/MIP with Preemptive Relaxation

A popular practical approach uses the LP relaxation of the time-indexed MIP to compute a lower bound on makespan, then feeds this bound to a CP solver as a pruning tool. The CP solver handles the combinatorial structure (symmetry, precedences); the LP handles resource capacity cuts.

Trade-offs: Best of both worlds in many benchmarks, but more complex to implement.

---

Example Model — OR-Tools CP-SAT (Python pseudo-code)

from ortools.sat.python import cp_model

model = cp_model.CpModel()
horizon = sum(durations)  # crude upper bound

# Decision variables
tasks = []
for i in range(n):
    start = model.NewIntVar(0, horizon, f"start_{i}")
    end   = model.NewIntVar(0, horizon, f"end_{i}")
    interval = model.NewIntervalVar(start, durations[i], end, f"interval_{i}")
    tasks.append((start, end, interval))

# Precedence constraints
for (i, j) in precedence_arcs:
    model.Add(tasks[j][0] >= tasks[i][1])

# Resource constraints (one Cumulative per resource)
for k in range(num_resources):
    model.AddCumulative(
        intervals  = [tasks[i][2] for i in range(n)],
        demands    = [requirements[i][k] for i in range(n)],
        capacity   = capacities[k]
    )

# Objective
makespan = model.NewIntVar(0, horizon, "makespan")
model.AddMaxEquality(makespan, [tasks[i][1] for i in range(n)])
model.Minimize(makespan)

solver = cp_model.CpSolver()
solver.Solve(model)

---

Key Techniques

1. Energetic Reasoning (ER)

For a time window [a, b], the minimum energy that resource k must supply equals ∑_i min(r_ik · overlap(i, [a,b])). If this exceeds R_k · (b−a), the problem is infeasible. ER derives this contradiction early and is one of the most powerful propagators for RCPSP.

2. Precedence-Based Lower Bounds

The critical path length (longest path in the precedence graph, by total duration) gives a lower bound on makespan even without resource constraints. Combining this with a preemptive schedule lower bound (solve a relaxed version where activities may be split) gives tight bounds cheaply.

3. Variable and Value Ordering Heuristics

• Activity Selection: Choose the activity with the earliest latest start time (most urgent) or the one on the critical path.
• Time Assignment: Assign the earliest feasible start (schedule-as-early-as-possible, ASAP), which tends to leave slack for later decisions.
• Restart strategies with clause learning (as in modern CP-SAT solvers) are very effective for RCPSP.

4. Symmetry Breaking via Dominant Schedules

The concept of left-shifted (active) schedules reduces the search space significantly: a schedule is active if no activity can be moved earlier without violating a constraint. Restricting search to active schedules eliminates a large fraction of equivalent solutions.

---

Challenge Corner

🧩 Think about this:

The standard RCPSP assumes renewable resources (capacity resets each time period). But what if some resources are non-renewable (e.g., a fixed budget consumed cumulatively)? How would you extend the model to handle both renewable and non-renewable resources simultaneously?

Bonus: the PSPLIB benchmark library contains hundreds of RCPSP instances. Can you find a model that solves the 30-activity instances (j30) to proven optimality reliably within 60 seconds?

---

References

1. 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. — The foundational survey.

2. Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-Based Scheduling. Kluwer Academic Publishers. — In-depth coverage of CP scheduling techniques including energetic reasoning.

3. 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. — Comprehensive taxonomy of RCPSP variants.

4. PSPLIB — Public benchmark library for RCPSP: (www.omdb.wi.tum.de/redacted) — Standard test instances (j30, j60, j90, j120) used in all competitive research.

AI generated by Constraint Solving — Problem of the Day · history

• expires on Mar 30, 2026, 2:18 PM UTC