Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 38 ยท Scheduling and Queueing

Critical Path Method

Plan projects with the critical path method: build activity networks, run forward and backward passes, find slack and the critical path, use PERT estimates, and crash activities with LP.

A project (building a house, launching a product, migrating a database) consists of activities with durations and precedence relations: the walls cannot go up before the foundation is done. How long will the project take? Which activities can slip without delaying it, and which cannot? The critical path method (CPM) answers both questions with simple arithmetic on a network.

CPM is a longest-path computation in an acyclic network, a close relative of shortest paths, and the "crashing" extension is a pure linear program.

The activity network

Each activity has a duration d_i and a set of predecessors that must finish before it starts. This forms a directed acyclic graph (DAG). Two dummy nodes help: START (before all activities with no predecessors) and END (after all activities with no successors).

flowchart LR
    S((Start)) --> A["A: 3"]
    S --> B["B: 2"]
    A --> C["C: 4"]
    A --> D["D: 6"]
    B --> D
    C --> E["E: 3"]
    D --> F["F: 5"]
    E --> G["G: 2"]
    F --> G
    G --> T((End))

Activity-on-node diagram; the number after each letter is the duration in days.

Forward and backward passes

Forward pass (earliest times). Going through activities in topological order:

TEXT
ES_j = max over predecessors i of EF_i      (0 if none)
EF_j = ES_j + d_j

The project duration is the largest EF.

Backward pass (latest times). Starting from the project duration T:

TEXT
LF_i = min over successors j of LS_j        (T if none)
LS_i = LF_i - d_i

Slack (float) of an activity is LS - ES. Zero slack means the activity is critical: delaying it delays the whole project. A path of critical activities from start to end is a critical path, and it is the longest path in the network.

Python CPM forward and backward passes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The critical activities form the path A, D, F, G with total length 3 + 6 + 5 + 2 = 16. Activities B, C and E have slack, so they can start late or run slow within limits without hurting the finish date.

Types of float

  • Total float LS - ES: how long an activity can slip before the project is delayed (shared with others on its path).
  • Free float: how long it can slip without delaying the earliest start of any successor.

Total float is shared. If B and another activity on the same non-critical path each use all of their individual total float, they together exceed the path's available slack, so always check the path rather than each activity alone.

PERT: uncertain durations

Real durations are uncertain. PERT (Program Evaluation and Review Technique) asks for three estimates per activity: optimistic a, most likely m and pessimistic b. A beta-distribution approximation gives:

TEXT
expected duration  te = (a + 4m + b) / 6
variance           var = ((b - a) / 6)^2

Run CPM with the expected durations. For the critical path the expected project length is the sum of te, and the variance is the sum of the variances (assuming independence), so you can estimate the chance of finishing by a deadline with a normal approximation.

Python PERT: probability of meeting a deadline

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The expected duration (17.3 days) is longer than the 16 days of the fixed-duration plan because the pessimistic estimates are skewed to the high side, and there is only about a 22% chance of finishing in 16 days. PERT also slightly underestimates the real duration when several near-critical paths compete, because the longest of several random paths is longer on average than any one of them. Use a simulation for risky projects.

Time-cost tradeoff: crashing as an LP

Many activities can be crashed: finished faster by paying for more labor or overtime. Suppose activity i has normal duration d_i, can be shortened by up to m_i days, and each day of crashing costs k_i. We want to meet a deadline T at least extra cost. This is a linear program:

TEXT
minimize    sum k_i y_i
subject to  s_j >= s_i + d_i - y_i      for each precedence i -> j
            s_end <= T, 0 <= y_i <= m_i, s >= 0

Variables: s_i start times and y_i crash days. The constraints say each activity starts after its predecessors finish, using the shortened duration.

Python Crashing the project from 16 to 13 days with linprog

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Normal duration is 16 days. To cut it to 13, the LP crashes A by one day (300) and F by two days (400), the cheapest way to remove three days from the critical path A, D, F, G, for an extra cost of 700. In bigger networks it may also crash parallel paths so that they do not become critical. The cost-versus-deadline curve is convex and piecewise linear, and you can trace it by solving for several values of T.

Fractional crash days are allowed in the LP. If crashing must be whole days, mark y as integer in a MILP, as in Integer Programming Basics.

Beyond the basics

  • Lags and overlaps: start-to-start relations with a delay generalize the constraints s_j >= s_i + lag.
  • Resource constraints: when activities share workers or equipment, the problem becomes the NP-hard resource-constrained project scheduling problem (RCPSP), usually handled with MILP or heuristics (Scheduling with MILP).
  • Monitoring: during a project, recompute CPM with actual progress; watch the critical path, because it can change.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How is the earliest start of an activity computed?

    An activity cannot start until all predecessors have finished, so it waits for the latest of them.
  2. 2. An activity has ES = 4 and LS = 7. What is its slack, and is it critical?

    Slack is LS - ES = 3 > 0, so the activity is not critical.
  3. 3. What does the PERT expected duration (a + 4m + b) / 6 use?

    It weights the most likely estimate four times and the two extremes once each.
  4. 4. In the crashing LP, what does the variable y_i represent?

    y_i is the (continuous) number of crash days, bounded by the maximum allowed and priced per day.

Summary

  • CPM models a project as an activity network; the forward pass gives earliest times, the backward pass latest times.
  • Slack is LS - ES; zero-slack activities form the critical path, the longest path through the network.
  • PERT uses three-point estimates to get expected durations and variances and a probability of meeting a deadline.
  • Time-cost tradeoffs (crashing) form a linear program in start times and crash days.
  • Resource limits turn CPM into harder scheduling problems that need integer programming.

Next: Scheduling with MILP