🧩 Constraint Solving POTD:Problem of the Day: Resource-Constrained Project Scheduling (RCPSP)

[github-actions[bot]]

Problem Statement

The Resource-Constrained Project Scheduling Problem asks: given a set of tasks with precedence dependencies and limited resources, find a schedule that minimizes makespan (total project duration) while respecting all constraints.

Consider a small example: You have 4 tasks (A, B, C, D) that must be completed on a construction project:

• Task A (duration 2 days) has no predecessors
• Task B (duration 3 days) requires A to complete first
• Task C (duration 2 days) requires A to complete first
• Task D (duration 1 day) requires both B and C to complete first

Resource constraint: Only 1 worker is available at any time.

Input:

• Tasks with durations: A=2, B=3, C=2, D=1
• Precedence graph: A → B, A → C; B,C → D
• Resource limits: 1 worker

Output:

• Optimal schedule: A (0-2) → B (2-5), C (2-4) → D (5-6)
• Makespan: 6 days

Why It Matters

Construction and engineering: General contractors must coordinate subcontractors (electricians, plumbers, carpenters) with limited availability. Delays in one trade cascade through the critical path, making optimal scheduling essential for profitability.

Software project management: Development sprints involve dependencies between modules, limited developer capacity, and integration phases. Poor scheduling causes bottlenecks and missed deadlines.

Manufacturing: Production lines must schedule jobs on bottleneck machines while respecting bill-of-materials dependencies and available labor. Even small improvements in makespan save millions in operational costs.

Modeling Approaches

Approach 1: Mixed-Integer Programming (MIP)

Paradigm: Linear programming with binary variables for task timing.

Decision variables:

• s_i = start time of task i (continuous)
• z_ij = binary variable (1 if task i finishes before task j starts)

Key constraints:

Minimize: max_i (s_i + d_i)  [makespan]

Subject to:
  s_j ≥ s_i + d_i  for each precedence i → j
  s_i ≥ 0 for all i
  Resource: Σ_{i: t ∈ [s_i, s_i+d_i]} r_i ≤ R_k  for each time t and resource k

Trade-offs:

• ✅ Exact solutions via branch-and-bound; well-understood solvers (CPLEX, Gurobi)
• ❌ Time indexing (bigM formulation) can create large, weak LP relaxations
• ❌ Non-convex due to disjunctive constraints

Approach 2: Constraint Programming (CP)

Paradigm: Declarative modeling with specialized propagation.

Decision variables:

• start[i] = start time of task i (integer domain)
• end[i] = end time of task i

Key constraints:

Minimize: max_i(end[i])

Subject to:
  end[i] = start[i] + duration[i]  for all i
  start[j] ≥ end[i]  for each precedence i → j
  cumulative(start[], duration[], resources[], capacity)

Trade-offs:

• ✅ Cumulative global constraint uses energy-based reasoning and edge-finding algorithms for strong propagation
• ✅ Easier to express complex temporal logic and disjunctions
• ✅ Handles discrete, non-linear constraints naturally
• ❌ May require careful search strategy tuning (restart, variable heuristics)

Example Model (MiniZinc)

int: n_tasks = 4;
array[1..n_tasks] of int: duration = [2, 3, 2, 1];
array[1..n_tasks] of int: resource_req = [1, 1, 1, 1];
int: max_capacity = 1;
int: max_horizon = 10;

% Precedence pairs (A → B, A → C, B → D, C → D)
array[1..4, 1..2] of 1..n_tasks: prec = 
  [|1,2 | 1,3 | 2,4 | 3,4|];

array[1..n_tasks] of var 0..max_horizon: start;
array[1..n_tasks] of var 0..max_horizon: end;

% Precedence constraints
constraint forall(i in 1..4)(
  start[prec[i,2]] >= end[prec[i,1]]
);

% Duration linking
constraint forall(i in 1..n_tasks)(
  end[i] = start[i] + duration[i]
);

% Cumulative resource constraint
constraint cumulative(start, duration, resource_req, max_capacity);

% Makespan
var int: makespan = max(end);

solve minimize makespan;

Key Techniques

1. Cumulative Global Constraint with Edge-Finding

The cumulative(starts, durations, resources, capacity) constraint is the workhorse of RCPSP solvers. Modern implementations use:

• Edge-finding: Detects that certain tasks must execute before/after a set, pruning unfeasible schedules
• Not-first/not-last reasoning: Eliminates impossible orderings
• Energetic reasoning: If the total resource demand in any time window exceeds capacity, infeasibility is detected

2. Critical Path Analysis & Precedence Relaxation

Before solving, compute:

• Earliest start times: Forward pass through the precedence graph (ignoring resources)
• Latest start times: Backward pass to identify the critical path
• Slack times: Tasks on the critical path have zero slack; others can shift within limits

This provides a good lower bound on makespan and guides search.

3. Restart Strategy & Variable Ordering

RCPSP can have a large search tree. Effective solvers use:

• Activity-based search: Prioritize tasks that are close to the critical path
• Conflict-driven restarts: Periodically restart the search after detecting symmetries or dead-ends
• Randomized ordering: Break ties in heuristics to explore different regions

Challenge Corner

Can you reduce the search space by pre-computing constraints on start times?

Think about this: given a deadline D on the entire project, how would you compute forbidden intervals—time periods during which a task cannot start—without solving the full RCPSP? What role does the cumulative constraint play in eliminating these intervals?

Extension: Suppose now some tasks can be preempted (paused and resumed later). How would this change your model? What additional constraints or decision variables would you need?

References

1. Brucker, P., Drexl, A., et al. (1999). "Resource-constrained project scheduling: Notation, classification, models, and methods." European Journal of Operational Research, 112(1), 3–41.

   • Comprehensive overview; standard taxonomy for RCPSP variants.

2. Laborie, P. & Godard, D. (2007). "Self-adjusting factory scheduling with double-part systems." Proceedings of the International Conference on Principles and Practice of Constraint Programming.

   • Modern CP approach using strong global constraints; IBM ILOG CP Optimizer perspective.

3. Schwindt, C. & Zimmermann, J. (2015). Handbook on Project Management and Scheduling (Vol. 1). Springer.

   • Practical guide to variants (with lags, multi-mode, preemption); algorithms and industrial applications.

4. Baptiste, P., Le Pape, C., & Nuijten, W. (2001). Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Kluwer.

   • Foundational text on CP techniques for scheduling; excellent on energy-based methods.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 6.72 AIC · ⌖ 5.48 AIC · ⊞ 6.1K · ◷

• expires on Oct 17, 2026, 3:35 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #67706.