Example 10-2: Critical path scheduling calculations

Consider the network shown in Figure 10-4 in which the project start is given number 0. Then,
the only event that has each predecessor numbered is the successor to activity A, so it receives
number 1. After this, the only event that has each predecessor numbered is the successor to the
two activities B and C, so it receives number 2. The other event numbers resulting from the
algorithm are also shown in the figure. For this simple project network, each stage in the
numbering process found only one possible event to number at any time. With more than one
feasible event to number, the choice of which to number next is arbitrary. For example, if activity
C did not exist in the project for Figure 10-4, the successor event for activity A or for activity B
could have been numbered 1.

Figure 10-4 A Nine-Activity Project Network

Once the node numbers are established, a good aid for manual scheduling is to draw a small
rectangle near each node with two possible entries. The left hand side would contain the earliest
time the event could occur, whereas the right hand side would contain the latest time the event
could occur without delaying the entire project. Figure 10-5 illustrates a typical box.

TABLE 10-2 Precedence Relations and Durations for a Nine Activity Project Example
Activity Description Predecessors Duration
A Site clearing --- 4
B Removal of trees --- 3
C General excavation A 8
D Grading general area A 7
E Excavation for trenches B, C 9
 F Placing formwork and reinforcement for concrete B, C 12
G Installing sewer lines D, E 2
H Installing other utilities D, E 5
I Pouring concrete F, G 6

For the network in Figure 10-4 with activity durations in Table 10-2, the earliest event time
calculations proceed as follows:

Step 1 E(0) = 0
Step 2
j=1 E(1) = Max{E(0) + D01} = Max{ 0 + 4 } = 4
j=2 E(2) = Max{E(0) + D02; E(1) + D12} = Max{0 + 3; 4 + 8} = 12
j=3 E(3) = Max{E(1) + D13; E(2) + D23} = Max{4 + 7; 12 + 9} = 21
j=4 E(4) = Max{E(2) + D24; E(3) + D34} = Max{12 + 12; 21 + 2} = 24
j=5 E(5) = Max{E(3) + D35; E(4) + D45} = Max{21 + 5; 24 + 6} = 30

Thus, the minimum time required to complete the project is 30 since E(5) = 30. In this case, each
event had at most two predecessors.

For the "backward pass," the latest event time calculations are:

Step 1 L(5) = E(5) = 30

Step 2
j=4 L(4) = Min {L(5) - D45} = Min {30 - 6} = 24
j=3 L(3) = Min {L(5) - D35; L(4) - D34} = Min {30 -5; 24 - 2} = 22
j=2 L(2) = Min {L(4) - D24; L(3) - D23} = Min {24 - 12; 22 - 9} = 12
j=1 L(1) = Min {L(3) - D13; L(2) - D12} = Min {22 - 7; 12 - 8} = 4
j=0 L(0) = Min {L(2) - D02; L(1) - D01} = Min {12 - 3; 4 - 4} = 0

In this example, E(0) = L(0), E(1) = L(1), E(2) = L(2), E(4) = L(4),and E(5) = L(5). As a result, all nodes
but node 3 are in the critical path. Activities on the critical path include A (0,1), C (1,2), F (2,4) and
I (4,5) as shown in Table 10-3.

TABLE 10-3 Identification of Activities on the Critical Path for a Nine-Activity Project
Duration Earliest start time Latest finish time Latest start time
Activity Dij E(i)=ES(i,j) L(j)=LF(i,j) LS(i,j)
 A (0,1) 4 0* 4* 0
B (0,2) 3 0 12 9
C (1,2) 8 4* 12* 4
D (1,3) 7 4 22 15
E (2,3) 9 12 22 13
F (2,4) 12 12* 24* 12
G (3,4) 2 21 24 22
H (3,5) 5 21 30 25
I (4,5) 6 24 30* 24

*Activity on a critical path since E(i) + DiJ = L(j).

Example 10-3: Critical path for a fabrication project

As another example of critical path scheduling, consider the seven activities associated with the
fabrication of a steel component shown in Table 10-4. Figure 10-7 shows the network diagram
associated with these seven activities. Note that an additional dummy activity X has been added
to insure that the correct precedence relationships are maintained for activity E. A simple rule to
observe is that if an activity has more than one immediate predecessor and another activity has
at least one but not all of these predecessor activity as a predecessor, a dummy activity will be
required to maintain precedence relationships. Thus, in the figure, activity E has activities B and
C as predecessors, while activity D has only activity C as a predecessor. Hence, a dummy activity
is required. Node numbers have also been added to this figure using the procedure outlined in
Table 10-1. Note that the node numbers on nodes 1 and 2 could have been exchanged in this
numbering process since after numbering node 0, either node 1 or node 2 could be numbered
next.

TABLE 10-4 Precedences and Durations for a Seven Activity Project

Activity Description Predecessors Duration

A Preliminary design --- 6

B Evaluation of design A 1
C Contract negotiation --- 8
D Preparation of fabrication plant C 5
E Final design B, C 9
F Fabrication of Product D, E 12
G Shipment of Product to owner F 3
Figure 10-7 Illustration of a Seven Activity Project Network

The results of the earliest and latest event time algorithms (appearing in Table 10-1) are shown
in Table 10-5. The minimum completion time for the project is 32 days. In this small project, all
of the event nodes except node 1 are on the critical path. Table 10-6 shows the earliest and latest
start times for the various activities including the different categories of float. Activities C,E,F,G
and the dummy activity X are seen to lie on the critical path.

TABLE 10-5 Event Times for a Seven Activity Project

Node Earliest Time E(i) Latest Time L(j)

0 0 0
1 6 7
2 8 8
3 8 8
4 17 17
5 29 29
6 32 32

TABLE 10-6 Earliest Start, Latest Start and Activity Floats for a Seven Activity Project

Latest start time Free float

Activity Earliest start time ES(i,j) LS(i,j) Independent float Total float
 A (0,1) 0 1 0 0 1
B (1,3) 6 7 1 0 1
C (0,2) 0 0 0 0 0
D (2,4) 8 12 4 4 4
E (3,4) 8 8 0 0 0
F (4,5) 17 17 0 0 0
G (5,6) 29 29 0 0 0
X (2,3) 8 8 0 0 0

Example 11-4: Time/Cost Trade-offs

The construction of a permanent transitway on an expressway median illustrates the possibilities

for time/cost trade-offs in construction work. [8] One section of 10 miles of transitway was built
in 1985 and 1986 to replace an existing contra-flow lane system (in which one lane in the
expressway was reversed each day to provide additional capacity in the peak flow direction).
Three engineers' estimates for work time were prepared:

 975 calendar day, based on 750 working days at 5 days/week and 8 hours/day of work
plus 30 days for bad weather, weekends and holidays.
 702 calendar days, based on 540 working days at 6 days/week and 10 hours/day of work.
 360 calendar days, based on 7 days/week and 24 hours/day of work.

The savings from early completion due to operating savings in the contra-flow lane and contract
administration costs were estimated to be $5,000 per day.

In accepting bids for this construction work, the owner required both a dollar amount and a
completion date. The bidder's completion date was required to fall between 360 and 540 days.
In evaluating contract bids, a $5,000 credit was allowed for each day less than 540 days that a
bidder specified for completion. In the end, the successful bidder completed the project in 270
days, receiving a bonus of 5,000*(540-270) = $450,000 in the $8,200,000 contract. However, the
contractor experienced fifteen to thirty percent higher costs to maintain the continuous work
schedule.

Example 11-5: Time cost trade-offs and project crashing

As an example of time/cost trade-offs and project crashing, suppose that we needed to reduce
the project completion time for a seven activity product delivery project first analyzed in Section
10.3 as shown in Table 10-4 and Figure 10-7. Table 11-4 gives information pertaining to possible
reductions in time which might be accomplished for the various activities. Using the minimum
cost durations (as shown in column 2 of Table 11-4), the critical path includes activities C,E,F,G
plus a dummy activity X. The project duration is 32 days in this case, and the project cost is
$70,000.
 TABLE 11-4 Activity Durations and Costs for a Seven Activity Project

Change in
Activity Minimum Cost Normal Duration Crash Cost Crash Duration Cost per Day

A 8 6 14 4 3
B 4 1 4 1 ---
C 8 8 24 4 4
D 10 5 24 3 7
E 10 9 18 5 2
F 20 12 36 6 2.7
G 10 3 18 2 8

Examining the unit change in cost, Rij shown in column 6 of Table 11-4, the lowest rate of change
occurs for activity E. Accordingly, a good heuristic strategy might be to begin by crashing this
activity. The result is that the duration of activity E goes from 9 days to 5 days and the total
project cost increases by $8,000. After making this change, the project duration drops to 28 days
and two critical paths exist: (1) activities C, X, E, F and G, and (2) activities C, D, F, and G.

Examining the unit changes in cost again, activity F has the lowest value of Rijj. Crashing this
activity results in an additional time savings of 6 days in the project duration, an increase in
project cost of $16,000, but no change in the critical paths. The activity on the critical path with
the next lowest unit change in cost is activity C. Crashing this activity to its minimum completion
time would reduce its duration by 4 days at a cost increase of $16,000. However, this reduction
does not result in a reduction in the duration of the project by 4 days. After activity C is reduced
to 7 days, then the alternate sequence of activities A and B lie on the critical path and further
reductions in the duration of activity C alone do not result in project time savings. Accordingly,
our heuristic corrections might be limited to reducing activity C by only 1 day, thereby increasing
costs by $4,000 and reducing the project duration by 1 day.

At this point, our choices for reducing the project duration are fairly limited. We can either reduce
the duration of activity G or, alternatively, reduce activity C and either activity A or activity B by
an identical amount. Inspection of Table 11-4 and Figure 10-4 suggest that reducing activity A
and activity C is the best alternative. Accordingly, we can shorten activity A to its crash duration
(from 6 days to 4 days) and shorten the duration of activity C (from 7 days to 5 days) at an
additional cost of $6,000 + $8,000 = $14,000. The result is a reduction in the project duration of
2 days.

Our last option for reducing the project duration is to crash activity G from 3 days to 2 days at an
increase in cost of $8,000. No further reductions are possible in this time since each activity along
a critical path (comprised of activities A, B, E, F and G) are at minimum durations. At this point,
the project duration is 18 days and the project cost is $120,000., representing a fifty percent
reduction in project duration and a seventy percent increase in cost. Note that not all the
activities have been crashed. Activity C has been reduced in duration to 5 days (rather than its 4
day crash duration), while activity D has not been changed at all. If all activities had been crashed,
the total project cost would have been $138,000, representing a useless expenditure of $18,000.
The change in project cost with different project durations is shown graphically in Figure 11-5.

Figure 11-5 Project Cost Versus Time for a Seven Activity Project