OPERATIONS RESEARCH

Chapter 7
Network Analysis

Prof. Bibhas C. Giri

Department of Mathematics
Jadavpur University
Kolkata, India
Email: [email protected]
MODULE - 2: Total Float and Free Float
of Activity, CPM Model: Time-cost
Optimization

2.1 Total Float and Free Float of An Activity

Total float - The total float refers to the amount of the free time associated with an
activity which can be used before, during or after the performance of this activity. To-
tal float is the positive difference between the earliest finish time and the latest finish
time, or the positive difference between the earliest start time and the latest start time
of an activity depending upon which way it is defined.

Free float - Free float is that portion of the total float within which an activity can
be manipulated without affecting the float of subsequent activities. The free float
indicates the value by which an activity can be delayed without causing any delay in
its immediate successor activities.

Example 2.1: A project has the following time-cost information:

Activity Time Activity Time

1-2 4 5-6 4
1-3 1 5-7 8
2-4 1 6-8 1
3-4 1 7-8 2
3-5 6 8-10 5
4-9 5 9-10 7

2
• Construct a network diagram and find the critical path and total project dura-
tion.

• Find total float and free float for each activity.

Solution: The networking diagram is shown in Fig. 2.1.

Fig. 2.1: Network diagram of Example 2.1

Calculations for the total and free floats are shown in the following table:

Activity Duration Earliest Latest Float

Start Finish Start Finish Total Free
tij Ei Ej = Ei + tij Li Lj Lj − Ej
1-2 4 0 4 5 9 5 0
1-3 1 0 1 0 1 0 0
2-4 1 4 5 9 10 5 0
3-4 1 1 2 9 10 8 3
3-5 6 1 7 1 7 0 0
4-9 5 5 10 10 15 5 0
5-6 4 7 11 12 16 5 0
5-7 8 7 15 7 15 0 0
6-8 1 11 12 16 17 5 5
7-8 2 15 17 15 17 0 0
8-10 5 17 22 17 22 0 0
9-10 7 10 17 15 22 5 5
2.2 CPM Model

The critical path method was developed for an industrial setting. It is most commonly
used in construction of projects where materials and activities are fairly standard.
Instead of focusing measuring the uncertainty of time estimate, it focuses primarily
on minimizing project costs.
CPM employs the basic networking fundamentals - the critical path or paths and
slack paths. Two time estimates, with associated costs are made for each activity: a
normal time to reflect typical conditions and a crash time to reflect stepped up condi-
tions. The basic contention is that time can be saved by applying added resources at
an increased cost. Times and costs for each activity are analyzed in terms of time-cost
trade off.

2.2.1 Time-cost relationship

The time-cost relationship for activities may take a variety of forms. As a simplify-
ing assumption, the typically non-linear time cost curve is approximated by a linear
equation (Figure 2.2). The linear approximation infers a cost increase in cost per unit
reduction in time. In situations where actual cost curve depends materially from lin-
earity, a piecewise linear approximation can be used (Figure 2.2). The exact time-cost

Fig. 2.2:

trade off for reducing the duration of an activity can be obtained from the linear time-
cost equation. It is the absolute value of the slope. More specifically, with a crash cost
(Cc ), a normal cost (CN ), a crash time (Tc ) and a normal time (TN ), the incremental cost
(Ic ) of crashing an activity is given by

∆C Cc − CN
Ic = =
∆T TN − Tc
In effect, the incremental cost represents the cost increase per unit of time decrease.
The following table contains the information for a representative project. The more
descriptive network counter part is presented in Fig. 2.3. The time estimates are in-
serted above, and the cost estimates below the activity arrows.

Activity Time (weeks) Cost (Rs.) Time ∆T Cost ∆C Incremental

Normal Crash Normal Crash reduction increase cost Ic
(weeks) (Rs.) (Rs.)
1-2 6 3 4000 5000 3 1000 333.3
1-3 6 2 4000 6000 4 2000 500
2-4 7 5 4000 6000 2 2000 1000
3-4 5 2 4000 6000 3 2000 666.6
2-5 5 3 3000 6000 2 3000 1500
4-5 9 6 5000 10000 3 5000 1667
4-6 6 4 3000 6000 2 3000 1500
5-7 4 1 2000 5000 3 3000 2000
6-7 2 1 2000 4000 1 2000 2000

Fig. 2.3: Time-cost estimates

The project information may also be expressed in an operational network with incre-
mental expediting costs inserted below the activity line (Fig. 2.4). By emphasizing
the cost of crashing an activity, this representation facilitates the implementation of
time-cost tradeoff.

2.2.2 Normal time and crash time schedules

A number of project schedules can be developed. At one extreme, a normal time
schedule can be designed to minimize the total cost. At the other extreme, a crash-
Fig. 2.4: Network with incremental expediting cost

time schedule can be constructed to minimize the duration of the project. Between
these extremes, intermediate-time schedules can also be developed. The scheduling

Fig. 2.5: Normal time schedule (TD = 26)

process typically begins with the construction of the normal and crash time schedules.
The normal time schedule represents the project with all activities taking place under
normal conditions. Fig. 2.5 represents the normal time schedule with critical path
and slack paths. Under normal time conditions, the project will have a duration of 26
weeks and cost Rs. 31000. The total cost is simply the sum of the costs of all activities.

The crash-time schedule is presented in Fig. 2.6 by crashing all activities, the du-
ration of the project can be reduced to 15 weeks. However, the cost is increased to Rs.
54000.

The normal time and crash time schedules provide the scheduling bounds for the
project. The normal time schedule gives the lowest cost and the longest duration. The
Fig. 2.6: Crash time schedule (TD = 15)

crash-time schedule gives the highest cost and the shortest duration. These extremes
can be compromised into other scheduling alternatives :

• time reduction on the normal time schedule by crashing activities on the critical
path

• cost reduction of the crash-time schedule by uncrashing some activities.

2.2.3 Least cost crash-time schedule

The crash-time schedule provides a directed date of 15 weeks at a cost of Rs. 54000.
While it allows the minimum completion time, it has the maximum project cost. The
schedule can be substantially improved. Several adjustments can reduce costs without
increasing the completion time.
The central concept of reducing the cost is straightforward: activities that need not
be expansively crashed should be assigned low-cost normal times. In Figure 2.7, all
activities are on crash times with crash costs. If the directed date of 15 weeks is to be
maintained, the activities on the critical path must remain crashed. Activities on non-
critical paths, however, can be extended by the amount of associated slack without
affecting the directed date. These activities can be extended towards normal times
with incremental cost savings.
Activities 2-5, for example, is presently crashed in 3 weeks at a cost of Rs. 6000.
The job has 8 weeks of slack. The duration can be increased by 8 weeks before the
project completion date is affected. There is no reason to crash A2−5 . It should be
converted to the normal time of 5 weeks with a cost of Rs. 3000 (Fig. 2.7). The total
cost of the schedule is then reduced from Rs. 54000 to 51000 with no change in the
directed date.
Fig. 2.7

The other non-critical activities should be uncrashed in the same way. Activities
1-3 and 3-4 have a total slack of 4 weeks. Their present crash times can be relaxed to
realize a savings (Fig. 2.8 ). For every week extension of A1−3 , the total activity cost
is reduced by Rs. 500. For every week extension of A3−4 , the cost is reduced by Rs.
667. Because it offers the greater cost benefit, A3−4 should be uncrashed as much as
possible. Since the normal time is 5 weeks, A3−4 can be extended from 2 to 5 weeks.
The remaining week of slack is allocated to extend A1−3 from 2 to 3 weeks. The total
savings from the two extended activities is Rs. (500 + 666.6 × 3) = Rs 2500.

Fig. 2.8

The slack along the path containing A1−3 and A3−4 has been reduced to zero. These
activities are now part of the critical path. Any further extension will extend the
duration of the project.
Fig. 2.9

Activities 4-6 and 6-7 represent a non-critical path with a shared slack of 2 weeks
(Fig. 2.9). The activities can be profitably uncrashed with the extension being applied
to the activity with the larger incremental benefit. A4−6 has an incremental benefit
of Rs. 1500; A6−7 has benefit of Rs. 2000. A6−7 can be uncrashed by 1 week to the
normal time limit of 2 weeks. A4−6 can be extended by the remaining week of slack.
With all of the slack utilized, A4−6 and A6−7 also become part of the critical path. The
uncrashing has saved Rs. 3500.
All activities have now been extended toward low-cost normal times as far as pos-
sible without altering the directed date. Fig. 2.10 provides the least-cost crash-time
schedule. The new schedule has the same directed date of 15 weeks. The uncrashing
of non-critical activities has reduced the total cost from Rs. 54000 to Rs. 45000.

Fig. 2.10: Least-cost crash-time schedule (TD = 15)

2.2.4 Least cost intermediate-time schedules
In most situations, the project planners will not be content with the extremes spec-
ified by the normal time schedule or the least-cost crash-time schedule. They may
want some intermediate position between a low-cost long duration and a high-cost
short duration. A compromise can be made between time and cost in a least-cost
intermediate-time schedule.
Several least-cost intermediate-time schedule will be developed. They will be used
later to form an optimal total project cost schedule. Developments will begin with
the normal cost schedule (Fig. 2.5). The directed date will be progressively reduced
by crashing activities at an increase in cost. The schedule construction will conclude
with the least-cost crash-time schedule (Fig. 2.10) with a directed date of 15 weeks
and a cost of Rs. 45000. These least cost intermediate-time schedules will span the
alternative space of time and cost options.
The normal time schedule (Fig. 2.5) is a least-cost schedule with a duration of 26
weeks. If the duration is shortened to 24 weeks then we determine the most econom-
ical means of providing 2-week reduction. Shortening the duration of non-critical
activities will not reduce the project completion time. The critical path can be short-
ened. 2 weeks reduction can be made by crashing one or more of the activities on the
critical path. The cost of crashing critical path activities are given below:

Incremental cost of crashing

A1−2 Rs. 333
A2−4 Rs. 1000
A4−5 Rs. 1667
A5−7 Rs. 1000

We see that A1−2 is the most economical choice. It can be shortened by 2 weeks at an
increased cost of only Rs. 667. Fig. 2.11 illustrates the least-cost intermediate-time
schedule with a directed date of 24 weeks and a cost of 31667.
If the desired directed date is 23 weeks, the critical path will have to be reduced by
another week. A1−2 still has the lowest crashing cost of Rs. 333. Crashing A1−2 for an
additional week, however, will not reduce the duration of the project (Fig. 2.12). A1−3
and A3−4 are part of a parallel critical path which must also be considered (Fig. 2.13).
To reduce the duration of the project, it is necessary to crash an activity on both of the
parallel lines.
Fig. 2.11: Least-cost intermediate time schedule (TD = 24)

Fig. 2.12

Total incremental cost

A1−2 and A1−3 Rs. 833
A1−2 and A3−4 Rs. 1000
A2−4 and A1−3 Rs. 1500
A2−4 and A3−4 Rs. 1667

Crashing A1−2 and A1−3 is the most economical choice. We now compare this choice
with critical path activities in the rest of the operational network.
The new least-cost intermediate-time schedule with a directed date of 23 weeks is
presented in Fig. 2.14. Both A1−2 and A1−3 have been crashed by 1 week. The total
cost increase to Rs. 32500.
Fig. 2.13

Fig. 2.14: Least-cost intermediate time schedule (TD = 23)

Total incremental cost

A1−2 and A1−3 Rs. 833
A1−2 and A3−4 Rs. 1000
A2−4 and A1−3 Rs. 1500
A2−4 and A3−4 Rs. 1667
A4−5 Rs. 1667
A5−7 Rs. 1000

A1−2 and A1−3 is the lowest-cost choice. However, A1−2 is already fully crashed. It
cannot be reduced any further. The alternatives with incremental costs are shown
below:

Total incremental cost

A2−4 and A1−3 Rs. 1500
A2−4 and A3−4 Rs. 1667
A4−5 Rs. 1667
A5−7 Rs. 1000
Reduction of A5−7 by 3 weeks provides the least-cost intermediate-time schedule for
20 weeks (Fig. 2.15). The added cost of 3 weeks time reduction is Rs. 3000 raising the
total cost to Rs. 35500.

Fig. 2.15: Least-cost intermediate time schedule (TD = 20)

Three additional intermediate-time schedules are presented in Figs. 2.16, 2.17 and
2.18. They complete the time span from the normal to crash time.

Fig. 2.16: Least-cost intermediate time schedule (TD = 18)

.

Fig. 2.17: Least-cost intermediate time schedule (TD = 16)

Fig. 2.18: Least-cost intermediate time schedule (TD = 15)