RCPSP Solver

Pseudocode

Once resources are finite the problem stops being a network sweep and becomes a search. The standard practical method is a serial schedule generation scheme driven by a priority rule.

SerialSGS(activities, priority):
    scheduled = {}
    for k = 1 to number of activities:
        eligible = unscheduled activities whose
                   predecessors are all scheduled
        a = the eligible activity ranked highest
            by the priority rule

        t = earliest time >= max finish of a's predecessors
            such that for every period in [t, t+dur[a]):
                usage + need[a] <= capacity, for each resource

        schedule a at t; update resource usage

// Priority rules: latest start time, minimum slack,
// most total successors, greatest resource demand

The serial scheme always produces a feasible schedule, never an optimal one. Different priority rules give different makespans, so practical solvers run many rules, or randomise the priority and sample thousands of schedules, keeping the best. Exact methods exist via branch and bound or constraint programming but only for small instances, since RCPSP is NP-hard.

Worked example, step by step

Take the same four-activity project used for CPM and add a single resource that only one activity can use at a time.

Example graph: Activities A (3 days), B (2 days), C (4 days), D (2 days), with A and B preceding C, and C preceding D. Every activity needs 1 unit of a resource whose total capacity is 1.

1. Recall the unconstrained answer. CPM scheduled A and B in parallel starting at time 0 and finished the project in 9 days, with B carrying one day of slack.
2. The parallel start is now illegal. A and B each need the whole resource, so they cannot overlap. The schedule must serialise them, and this is the moment the problem stops being solvable by a network sweep.
3. Try A first. A runs 0 to 3, then B runs 3 to 5. C cannot start until both are done, so it runs 5 to 9, and D runs 9 to 11.
4. Try B first. B runs 0 to 2, then A runs 2 to 5. C again waits for both, running 5 to 9, and D runs 9 to 11.
5. Both orders tie. Either sequencing gives a makespan of 11. Here the total work on A and B is what binds, so the order between them does not matter. On larger instances it usually does, which is exactly why priority rules are worth choosing carefully.

The resource constraint pushes the project from 9 days to 11. Two things are worth taking from this. B had one day of slack under CPM and now has none, because slack computed without resource constraints is not real slack. And the critical path concept itself weakens: the binding constraint here is resource contention between A and B, which is not a path through the network at all.

Complexity, and where it comes from

Time: NP-hard; O(V^2) per schedule generation · Space: O(V + R·T)

RCPSP is NP-hard, and strongly so: it generalises job-shop scheduling and contains bin packing as a special case, so no polynomial algorithm is expected. A single pass of the serial schedule generation scheme is cheap, at O(V squared) in the worst case, since for each of V activities it may scan forward through time looking for a feasible start. Memory is the resource profile over the planning horizon, O(R times T) for R resources and T time periods, plus O(V) for the schedule. Practical solvers exploit the cheapness of one pass by generating thousands of schedules under randomised priority rules, or by embedding the scheme inside a genetic algorithm or tabu search. Exact branch-and-bound handles roughly 30 to 60 activities depending on how tight the resources are.

When to use RCPSP (Resource-Constrained Project Scheduling), and when not to

Which method fits depends on whether resources actually bind and how large the instance is.

Common pitfalls

• Trusting CPM float once resources are constrained. Slack computed without resource limits is optimistic and often plain wrong. In the example, B looked as though it had a day of float, and under the real constraint it has none. Resource-constrained float has to be computed against the actual schedule.
• Assuming a single critical path still exists. With resource contention, the binding constraint can be two activities competing for a machine rather than any path through the dependency network. The critical chain concept exists precisely because the classical critical path stops being the whole story.
• Using one priority rule and stopping. Different rules produce materially different makespans on the same instance and no rule dominates. Running several and keeping the best costs almost nothing given how cheap a single pass is.
• Forgetting renewable versus non-renewable resources. A renewable resource, such as a machine or a person, replenishes each period. A non-renewable one, such as a budget, is consumed for the whole project. Modelling a budget as renewable silently allows spending it again every day.
• Ignoring that the schedule may be infeasible at any time. If one activity demands more of a resource than the total capacity, no schedule exists at all. Check per-activity demand against capacity before searching, or the solver will loop looking for a start time that can never arrive.

Frequently asked questions

What is the resource-constrained project scheduling problem?

RCPSP asks for the shortest schedule for a set of activities with precedence constraints, where each activity consumes limited resources that cannot be exceeded at any point in time. It generalises the critical path method by adding capacity limits, which turns a linear-time network calculation into an NP-hard optimisation problem.

How does RCPSP differ from the critical path method?

CPM assumes unlimited resources, so any set of activities whose dependencies are satisfied can run simultaneously. RCPSP enforces capacity, so activities compete and must sometimes be serialised. In the worked example the same network takes 9 days under CPM and 11 days once a single shared resource is introduced.

Why is RCPSP NP-hard?

It generalises several known hard problems, including job-shop scheduling and bin packing, the latter appearing when activities must be packed into limited capacity over time. No polynomial algorithm is known, and exact methods are practical only up to roughly 60 activities depending on how tightly resources bind.

What is a schedule generation scheme?

It is the standard heuristic construction method. The serial version repeatedly picks the highest-priority activity whose predecessors are all scheduled, then places it at the earliest time where enough resource capacity is free for its whole duration. It always yields a feasible schedule, and the priority rule determines how good that schedule is.

Does resource-constrained scheduling change the critical path?

Yes, in two ways. Float computed by CPM is no longer reliable, since an activity with slack on paper may be pinned by resource contention. And the binding constraint may not be a path at all, but two independent activities competing for the same resource, which is why practitioners use the critical chain rather than the critical path when resources are tight.