CPM - Critical Path Method

This algorithm follows a solution strategy very similar to the dynamic programming algorithm, however there is a variation which occurs due to the fact that a project network need not be structured as a sequence of stages. It also has a starting node and works by computing 'flag values' for the nodes, however for CPM problems, the flag values represent the longest time to each node, and the nodes in the network may be processed in any sequence so long as all preceding nodes have flags at each step. The arcs are always directed, for 'activity on arc' or AoA diagrams since the passage of time is implied by each activity, and for 'activity on node' or AoN diagrams since a precedence relation states that one activity must be complete before another begins. But the possibility of concurrent activities means that there will usually be many paths through the network, and the longest of these is called the critical path since it determines the minimal project duration.

 Although textbooks have traditionally described the CPM in terms of AoA diagrams, the programming logic is much simpler and more natural using the AoN diagrams. So we use the AoN convention here to conform with current software practice. We require the insertion of a BOP beginning of project node to start the project (unless there is already one activity which must precede all others) and also the insertion of a EOP end of project node to end the project (unless there is already one activity which must follow all others).

 For the AoN diagrams, we will actually be computing four 'flag' values for each node. Two of them, the ES early start times and the EF early finish times, are computed in a forward pass which procedes from the BOP to the EOP, i.e. in the forward time direction. The other two of them, the LF late finish times and the LS late start times, are computed in a second backward pass which procedes from the EOP back to the BOP, i.e. in the backwards time direction. If we denote by d(k) the duration of activity k, then it is easy to see that EF(k) = ES(k) + d(k) and LS(k) = LF(k) - d(k). Hence there are really only two independent times at each node to compute from the forward and backward passes, the other two being obtained by simple addition and subtraction of d(k). It is customary to place the ES and EF times in the upper left and upper right corners of each node on the forward pass, and then place the LF and LS times in the lower right and lower left corners respectively on the backward pass.

The activity slack for each node is then easily given as LS(k)-ES(k) or, equivalently, as LF(k)-EF(k). This is the amount of time an activity may be delayed beyond its early start time without causing a delay in the time of the EOP.

Now here is the algorithm description, which has four parts: the initialization step, the forward pass, the backward pass, and the computation of slacks.

 Initialization

Step 0: Place a BOP at the beginning of the project if there is no activity which must precede all others (i.e. when several activities may begin in parallel). Place an EOP node at the end of the project if there is no activity which must follow all others (i.e. when several activities may end in parallel). Place an ES flag value of zero on the designated origin node, and let EF(1) = d(1) for the first node (where the duration of both BOP and EOP nodes is taken to be zero).

Forward Pass

Step 1: Pick any node k such that all of its predecesors have EF time flags. If none remain, i.e. the last or EOP node has just been flagged, go to the Backward Pass.

Step 2: Let the ES(k) time for the selected node be the maximum of the EF times at the preceeding nodes, and set the EF(k) time for node k equal to ES(k) + d(k). Return to step 1.  Mathematically, we can write formulas for the early start and finish times as follows:

 Backward Pass

Initialization: Set the LF time at the last or EOP node equal to the EF time, so that no delays at the final project time are allowed. Then set the LS there equal to the ES, as well. Hence the node slack at the last node is zero, by definition.

 Step 3. Choose any node such that all following nodes have LS time flags. If none remain, i.e. the beginning or BOP node has just been flagged, go to the computation of slacks.

 Step 4. Set the LF(j) time for the selected node to the minimum of the LS times at the succeeding nodes, and set the LS(j) time for node j equal to LF(j) - d(j). Return to step 3.  Mathematically, we can write formulas for the late start and finish times as follows:

 Activity Slacks

 Let activity slack S(k) = LS(k) - ES(k) for each node. Activities with zero slack are called critical activities, and are always found on one or more critical paths. This (or these) critical path(s) determine minimum project duration since all of them must be completed as part of the project, and all noncritical activities can be completed concurrently with the critical activities.