The critical path method, step by step

The tech fest’s 14 activities take 76 working days if they are done one after another, yet the fest can be over in 38, because most of them run side by side. Which activities decide those 38 days, and how long may each of the others slip before the date moves? Two passes over the network answer both questions exactly.

You will run the forward and backward passes by hand and check them against a program, compute total and free float, find the critical path and watch it move when one activity grows, and test the path against GAO’s criteria for a valid one.

The forward pass gives every activity its earliest start and finish

The forward passforward pass: The walk through a schedule network from start to finish that gives each activity its early start and early finish; at a merge it takes the latest predecessor. walks the network from the start to the finish. Each activity starts as soon as its links allow, its early start (ES), and finishes its duration later, its early finish (EF). With a finish-to-start link, the successor’s ES is the predecessor’s EF. With several predecessors, an activity waits for the latest of them, which is the step that most hand calculations get wrong.

Days are counted from the start: ES 3 means the activity starts once 3 working days have passed. A, authorise plan and budget, has ES 0 and EF 3. C and E both wait for A, so both have ES 3. The two other link types follow their own ends: I starts 2 days after H starts (ES 11 + 2 = 13), and M’s finish link with I only asks that M finish after day 23. Step through the pass on nine of the fest’s activities; the second half of the figure is the backward pass of the next section:

At M four links meet. L allows a start at day 32, H at 15, J at 14 and the finish link with I at 21, so M starts at 32, the latest, and finishes at 34. The fest’s finish milestone comes after N’s 4 days, at 38. GAO’s schedule guide describes the same calculation as the software’s: the forward pass adds durations to early starts, and the backward pass subtracts them from late finishes.

The backward pass and float say how late each activity may run

The backward passbackward pass: The walk back from the finish that gives each activity its late finish and late start, the latest dates that keep the finish where it is. starts from the finish, day 38, and walks back. Each activity’s late finish (LF) is the latest it may finish without moving the finish, and its late start (LS) is LF minus its duration. With several successors, an activity takes the earliest limit any of them sets. The difference between the late and the early dates is its total floattotal float: How many days an activity can slip before the project's finish moves: its late start minus its early start., the days it can slip before the finish moves. The program below runs both passes over all 16 rows of the network:

"""Forward and backward passes over the tech fest network, with total and free float and the critical path.

Durations are working days. ES and EF are the early start and finish, LS and LF the late ones, all counted in days
from the start: an activity with ES 3 and EF 8 starts after 3 working days and is done after 8. Links: FS
(finish-to-start), SS (start-to-start) and FF (finish-to-finish), with a lag in days. Total float is LS - ES, the
slip an activity can take before the finish moves; free float is the slip it can take before any successor moves
(both as GAO's Schedule Assessment Guide, GAO-16-89G, defines them).
"""

FEST = {
    "S": ("Milestone: start", 0, []),
    "A": ("Authorise plan and budget", 3, [("S", "FS", 0)]),
    "B": ("Book the auditorium", 2, [("A", "FS", 0)]),
    "C": ("Prepare sponsor packages", 5, [("A", "FS", 0)]),
    "D": ("Sign sponsors", 10, [("C", "FS", 0)]),
    "E": ("Design the coding contest", 8, [("A", "FS", 0)]),
    "F": ("Build the robotics arena", 12, [("D", "FS", 0)]),
    "G": ("Line up speakers", 6, [("B", "FS", 0)]),
    "H": ("Build the registration form", 4, [("E", "FS", 0)]),
    "I": ("Run the publicity campaign", 10, [("H", "SS", 2)]),
    "J": ("Print posters", 3, [("G", "FS", 0)]),
    "K": ("Plan crowd control and first aid", 5, [("B", "FS", 0)]),
    "L": ("Set up sound, lights and stage", 2, [("F", "FS", 0), ("K", "FS", 0)]),
    "M": ("Hold the fest", 2, [("L", "FS", 0), ("H", "FS", 0), ("J", "FS", 0), ("I", "FF", 0)]),
    "N": ("Close the accounts and report", 4, [("M", "FS", 0)]),
    "Z": ("Milestone: finish", 0, [("N", "FS", 0)]),
}


def passes(net, finish_by=None):
    """Returns ES, EF, LS, LF, total float and free float. finish_by: {activity: latest finish day}, a constraint."""
    order = list(net)  # the dict is written in an order where every predecessor comes first
    dur = {a: net[a][1] for a in net}
    es, ef = {}, {}
    for a in order:
        start = 0
        for p, kind, lag in net[a][2]:
            if kind == "FS":
                start = max(start, ef[p] + lag)
            elif kind == "SS":
                start = max(start, es[p] + lag)
            elif kind == "FF":
                start = max(start, ef[p] + lag - dur[a])
        es[a], ef[a] = start, start + dur[a]
    end = max(ef.values())
    succs = {a: [(s, kind, lag) for s in net for p, kind, lag in net[s][2] if p == a] for a in net}
    ls, lf = {}, {}
    for a in reversed(order):
        finish = end
        for s, kind, lag in succs[a]:
            if kind == "FS":
                finish = min(finish, ls[s] - lag)
            elif kind == "SS":
                finish = min(finish, ls[s] - lag + dur[a])
            elif kind == "FF":
                finish = min(finish, lf[s] - lag)
        if finish_by and a in finish_by:
            finish = min(finish, finish_by[a])
        lf[a], ls[a] = finish, finish - dur[a]
    total = {a: ls[a] - es[a] for a in net}
    free = {}
    for a in net:
        slack = [end - ef[a]] if not succs[a] else []
        for s, kind, lag in succs[a]:
            if kind == "FS":
                slack.append(es[s] - lag - ef[a])
            elif kind == "SS":
                slack.append(es[s] - lag - es[a])
            elif kind == "FF":
                slack.append(ef[s] - lag - ef[a])
        free[a] = min(slack)
    return es, ef, ls, lf, total, free, end


def critical(net, total):
    low = min(total.values())
    return [a for a in net if total[a] == low]


def valid(net, path):
    """GAO best practice 6, the checks a program can make: one continuous chain of logic from start to finish,
    no lags or leads on it, no milestone carrying a duration."""
    problems = []
    on = set(path)
    for a in path[1:]:
        if not any(p in on for p, _, _ in net[a][2]):
            problems.append(f"{a} has no critical predecessor: the path is broken")
        for p, _, lag in net[a][2]:
            if p in on and lag:
                problems.append(f"the link {p} -> {a} carries a lag of {lag}")
    return problems or ["valid: continuous from start to finish, no lags or leads, driven by logic alone"]


es, ef, ls, lf, total, free, end = passes(FEST)
print(f"{'Id':<3}{'Activity':<34}{'Days':>4}{'ES':>4}{'EF':>4}{'LS':>4}{'LF':>4}{'Total':>7}{'Free':>6}")
for a, (name, days, _) in FEST.items():
    print(f"{a:<3}{name:<34}{days:>4}{es[a]:>4}{ef[a]:>4}{ls[a]:>4}{lf[a]:>4}{total[a]:>7}{free[a]:>6}")
path = critical(FEST, total)
print(f"Critical path: {' '.join(path)}, {end} working days")
print("Check:", "; ".join(valid(FEST, path)))
near = sorted((t, a) for a, t in total.items() if 0 < t <= 15)
print("Near-critical (total float 1 to 15 days):", ", ".join(f"{a} {t}" for t, a in near))

for days in (19, 20):
    slow = dict(FEST)
    slow["E"] = ("Design the coding contest", days, FEST["E"][2])
    *_, total2, _, end2 = passes(slow)
    print(f"If E takes {days} days instead of 8: finish after {end2} days, critical path {' '.join(critical(slow, total2))}")

es3, ef3, ls3, lf3, total3, free3, end3 = passes(FEST, finish_by={"M": 32})
late = [f"{a} {total3[a]}" for a in FEST if total3[a] < 0]
print(f"If the fest must be over by day 32: total float {', '.join(late)}")

Id Activity                          Days  ES  EF  LS  LF  Total  Free
S  Milestone: start                     0   0   0   0   0      0     0
A  Authorise plan and budget            3   0   3   0   3      0     0
B  Book the auditorium                  2   3   5  21  23     18     0
C  Prepare sponsor packages             5   3   8   3   8      0     0
D  Sign sponsors                       10   8  18   8  18      0     0
E  Design the coding contest            8   3  11  14  22     11     0
F  Build the robotics arena            12  18  30  18  30      0     0
G  Line up speakers                     6   5  11  23  29     18     0
H  Build the registration form          4  11  15  22  26     11     0
I  Run the publicity campaign          10  13  23  24  34     11    11
J  Print posters                        3  11  14  29  32     18    18
K  Plan crowd control and first aid     5   5  10  25  30     20    20
L  Set up sound, lights and stage       2  30  32  30  32      0     0
M  Hold the fest                        2  32  34  32  34      0     0
N  Close the accounts and report        4  34  38  34  38      0     0
Z  Milestone: finish                    0  38  38  38  38      0     0
Critical path: S A C D F L M N Z, 38 working days
Check: valid: continuous from start to finish, no lags or leads, driven by logic alone
Near-critical (total float 1 to 15 days): E 11, H 11, I 11
If E takes 19 days instead of 8: finish after 38 days, critical path S A C D E F H I L M N Z
If E takes 20 days instead of 8: finish after 39 days, critical path S A E H I M N Z
If the fest must be over by day 32: total float S -2, A -2, C -2, D -2, F -2, L -2, M -2

Read the table one row at a time. K, crowd control and first aid, has ES 5 and LS 25: it may start up to 20 days late. B, the auditorium booking, has 18 days of total float but 0 days of free floatfree float: How many days an activity can slip before the early start of any of its successors moves; never more than its total float., the slip it can take before any successor moves. Any delay to B delays G and K at once, although the finish has room. That difference matters to the people who own G and K, and it is why GAO’s guide defines both.

The critical path is the chain with no float, and it moves

The activities with the lowest total float, here 0, form the critical pathcritical path: The continuous chain of activities with the lowest total float, which sets the earliest date the project can finish.: S, A, C, D, F, L, M, N and Z, 38 working days. GAO’s guide defines it as the longest continuous sequence of activities, the one that sets the earliest finish, so every day lost on it is a day lost at the end unless something is done about it. The guide adds that “critical” has this exact meaning: an important activity is not necessarily critical, and a dull one, such as setting up the stage, can be.

The path is not fixed. E, H and I share 11 days of total float, so they are a near-critical pathnear-critical path: A chain of activities with a little total float, which becomes the critical path if it slips by more than that float.. The program’s last lines show what a slip on it does:

A slip of exactly the chain’s float leaves the finish alone but makes two critical paths. One day more and the events chain sets the finish, while the sponsor chain, which everyone was watching, now has 1 day of float.

A valid critical path is driven by logic alone

A path can be the longest and still be wrong. GAO’s checklist for its sixth best practice asks that the critical path run continuously from the status date to the finish milestone, carry no lags or leads, include no level-of-effort or summary activities, and not be made critical by constraints on unimportant activities. The program’s check finds the fest’s path continuous, with no lag on any of its links.

Constraints are the usual trouble. Suppose the college insists that the fest be over by day 32. The last line of the output shows the effect of that constraint: S, A, C, D, F, L and M now have a total float of −2. Negative floatnegative float: Total float below zero, which appears when a required date is earlier than the network allows; its size is the number of days to recover. means the plan already misses the constraint by that many days. It is a warning, not an error: either the work changes, by a shorter path or more people on it, or the date does. With such constraints in a schedule, GAO’s guide asks for the longest path to be shown beside the lowest-float one, because the two can differ.

Practise: passes, float and the path

The questions bring new networks to work through as well as the fest. Do the passes on paper first, then choose or type your answer:

Interview questions

Warm-up (fresher to 2–5 years): total float and free float are both slack, so how do they differ?

Total float is how long an activity can slip before the project’s finish moves; free float is how long it can slip before any successor’s early start moves. Free float is never larger than total float. In the tech fest, booking the auditorium has 18 days of total float but 0 of free float: any delay reaches the next two activities at once, although the finish has room. Total float tells the project manager which delays threaten the end date; free float tells the owners of the next activities whether a delay reaches them.

Two harder questions follow, about a manager who wants every activity marked critical and about a schedule full of negative float. Decide what you would check first, then open each first step:

Key takeaways

• The forward pass gives each activity its early start and finish, taking the latest predecessor at every merge, and sets the earliest finish of the project.
• The backward pass gives the late dates from the finish back; total float is late start minus early start, and free float is the slip before any successor moves.
• The critical path is the continuous chain with the lowest float, and it moves when a near-critical chain slips by more than its float.
• A valid critical path is driven by logic, with no lags, leads or level-of-effort work on it, and negative float means a constraint date is already missed.