10.6 Critical Path Scheduling for Activity-on-Node and with Leads, Lags, and Windows

Performing the critical path scheduling algorithm for activity-on-node representations is only a small variation from the activity-on-branch algorithm presented above. An example of the activity-on-node diagram for a seven activity network is shown in Figure 10-3. Some addition terminology is needed to account for the time delay at a node associated with the task activity. Accordingly, we define: ES(i) as the earliest start time for activity (and node) i, EF(i) is the earliest finish time for activity (and node) i, LS(i) is the latest start and LF(i) is the latest finish time for activity (and node) i. Table 10-7 shows the relevant calculations for the node numbering algorithm, the forward pass and the backward pass calculations.

TABLE 10-7  Critical Path Scheduling Algorithms (Activity-on-Node Representation)
Activity Numbering Algorithm
Step 1: Give the starting activity number 0.
Step 2: Give the next number to any unnumbered activity whose predecessor activities
     are each already numbered.
Repeat Step 2 until all activities are numbered.
Forward Pass
Step 1: Let E(0) = 0.
Step 2: For j = 1,2,3,...,n (where n is the last activity), let
     ES(j) = maximum {EF(i)}
where the maximum is computed over all activities (i) that have j as their successor.
Step 3: EF(j) = ES(j) + Dj
Backward Pass
Step 1: Let L(n) equal the required completion time of the project.
     Note: L(n) must equal or exceed E(n).
Step 2: For i = n-1, n-2, ..., 0, let
     LF(i) = minimum {LS(j)}
where the minimum is computed over all activities (j) that have i as their predecessor.
Step 3: LS(i) = LF(i) - Di

For manual application of the critical path algorithm shown in Table 10-7, it is helpful to draw a square of four entries, representing the ES(i), EF(i), LS(i) and LF (i) as shown in Figure 10-14. During the forward pass, the boxes for ES(i) and EF(i) are filled in. As an exercise for the reader, the seven activity network in Figure 10-3 can be scheduled. Results should be identical to those obtained for the activity-on-branch calculations.

Figure 10-14  ES, EF, LS and LF Display for Hand Calculation of Critical Path for Activity-on-Node Representation

Building on the critical path scheduling calculations described in the previous sections, some additional capabilities are useful. Desirable extensions include the definition of allowable windows for activities and the introduction of more complicated precedence relationships among activities. For example, a planner may wish to have an activity of removing formwork from a new building component follow the concrete pour by some pre-defined lag period to allow setting. This delay would represent a required gap between the completion of a preceding activity and the start of a successor. The scheduling calculations to accommodate these complications will be described in this section. Again, the standard critical path scheduling assumptions of fixed activity durations and unlimited resource availability will be made here, although these assumptions will be relaxed in later sections.

A capability of many scheduling programs is to incorporate types of activity interactions in addition to the straightforward predecessor finish to successor start constraint used in Section 10.3. Incorporation of additional categories of interactions is often called precedence diagramming. For example, it may be the case that installing concrete forms in a foundation trench might begin a few hours after the start of the trench excavation. This would be an example of a start-to-start constraint with a lead: the start of the trench-excavation activity would lead the start of the concrete-form-placement activity by a few hours. Eight separate categories of precedence constraints can be defined, representing greater than (leads) or less than (lags) time constraints for each of four different inter-activity relationships. These relationships are summarized in Table 10-8. Typical precedence relationships would be:

While the eight precedence relationships in Table 10-8 are all possible, the most common precedence relationship is the straightforward direct precedence between the finish of a preceding activity and the start of the successor activity with no required gap (so FS = 0).

TABLE 10-8  Eight Possible Activity Precedence Relationships
Relationship Explanation
Finish-to-start Lead Latest Finish of Predecessor Earliest Start of Successor + FS
Finish-to-start Lag Latest Finish of Predecessor Earliest Start of Successor + FS
Start-to-start Lead Earliest Start of Predecessor Earliest Start of Successor + SS
Start-to-start Lag Earliest Start of Predecessor Earliest Start of Successor + SS
Finish-to-finish Lead Latest Finish of Predecessor Earliest Finish of Successor + FF
Finish-to-finish Lag Latest Finish of Predecessor Earliest Finish of Successor + FF
Start-to-finish Lead Earliest Start of Predecessor Earliest Finish of Successor + SF
Start-to-finish Lag Earliest Start of Predecessor Earliest Finish of Successor + SF

The computations with these lead and lag constraints are somewhat more complicated variations on the basic calculations defined in Table 10-1 for critical path scheduling. For example, a start-to-start lead would modify the calculation of the earliest start time to consider whether or not the necessary lead constraint was met:


where SSij represents a start-to-start lead between activity (i,j) and any of the activities starting at event j.

The possibility of interrupting or splitting activities into two work segments can be particularly important to insure feasible schedules in the case of numerous lead or lag constraints. With activity splitting, an activity is divided into two sub-activities with a possible gap or idle time between work on the two subactivities. The computations for scheduling treat each sub-activity separately after a split is made. Splitting is performed to reflect available scheduling flexibility or to allow the development of a feasible schedule. For example, splitting may permit scheduling the early finish of a successor activity at a date later than the earliest start of the successor plus its duration. In effect, the successor activity is split into two segments with the later segment scheduled to finish after a particular time. Most commonly, this occurs when a constraint involving the finish time of two activities determines the required finish time of the successor. When this situation occurs, it is advantageous to split the successor activity into two so the first part of the successor activity can start earlier but still finish in accordance with the applicable finish-to-finish constraint.

Finally, the definition of activity windows can be extremely useful. An activity window defines a permissible period in which a particularly activity may be scheduled. To impose a window constraint, a planner could specify an earliest possible start time for an activity (WES) or a latest possible completion time (WLF). Latest possible starts (WLS) and earliest possible finishes (WEF) might also be imposed. In the extreme, a required start time might be insured by setting the earliest and latest window start times equal (WES = WLS). These window constraints would be in addition to the time constraints imposed by precedence relationships among the various project activities. Window constraints are particularly useful in enforcing milestone completion requirements on project activities. For example, a milestone activity may be defined with no duration but a latest possible completion time. Any activities preceding this milestone activity cannot be scheduled for completion after the milestone date. Window constraints are actually a special case of the other precedence constraints summarized above: windows are constraints in which the precedecessor activity is the project start. Thus, an earliest possible start time window (WES) is a start-to-start lead.

One related issue is the selection of an appropriate network representation. Generally, the activity-on-branch representation will lead to a more compact diagram and is also consistent with other engineering network representations of structures or circuits. For example, the nine activities shown in Figure 10-4 result in an activity-on-branch network with six nodes and nine branches. In contrast, the comparable activity-on-node network shown in Figure 9-6 has eleven nodes (with the addition of a node for project start and completion) and fifteen branches. The activity-on-node diagram is more complicated and more difficult to draw, particularly since branches must be drawn crossing one another. Despite this larger size, an important practical reason to select activity-on-node diagrams is that numerous types of precedence relationships are easier to represent in these diagrams. For example, different symbols might be used on each of the branches in Figure 9-6 to represent direct precedences, start-to-start precedences, start-to-finish precedences, etc. Alternatively, the beginning and end points of the precedence links can indicate the type of lead or lag precedence relationship. Another advantage of activity-on-node representations is that the introduction of dummy links as in Figure 10-1 is not required. Either representation can be used for the critical path scheduling computations described earlier. In the absence of lead and lag precedence relationships, it is more common to select the compact activity-on-branch diagram, although a unified model for this purpose is described in Chapter 11. Of course, one reason to pick activity-on-branch or activity-on-node representations is that particular computer scheduling programs available at a site are based on one representation or the other. Since both representations are in common use, project managers should be familiar with either network representation.

Many commercially available computer scheduling programs include the necessary computational procedures to incorporate windows and many of the various precedence relationships described above. Indeed, the term "precedence diagramming" and the calculations associated with these lags seems to have first appeared in the user's manual for a computer scheduling program.

If the construction plan suggests that such complicated lags are important, then these scheduling algorithms should be adopted. In the next section, the various computations associated with critical path scheduling with several types of leads, lags and windows are presented.