PERT / CPM:ALGORITHM FOR CRITICAL PATH, Free Slack

<< PERT / CPM:DUMMY ACTIVITIES, TO FIND THE CRITICAL PATH

PERT / CPM:Expected length of a critical path, Expected time and Critical path >>

Operations Research (MTH601)

Start

B,6

E,6

Fig. 13

We see that there are three paths or routes from start to end.

The following are the paths.

(1) Start - A - D - End

(2) Start - B - C - D - End

(3) Start - B - E - End.

The times taken to complete the activities on the three paths are

5+3

= 8 days

6 + 7 + 3 = 16 days

6+6

= 12 days

The longest path is B-C-D and the duration is 16 days. Hence the critical path is B-C-D and the project

completion time is 16 days.

Thus, whether we use the arrow diagram or the activity on node diagram, we get the same result. This

procedure can be applied without much effort for small projects involving only a few activities but the same

procedure may be cumbersome if the project involves a large number of activities. However, there is an effective

method of finding the critical path as explained in the next section.

ALGORITHM FOR CRITICAL PATH

Consider the following project.

Job's name

Immediate predecessor

Time to complete the job

10 days

3 days

a,b

4 days

7 days

4 days

c,e

12 days

We draw the project graph by an arrow diagram as shown in Fig 14. The activity `g' is a dummy activity

consuming no time.

g 0

Operations Research (MTH601)

Fig. 14

Early start and early finish programme

We define the 'early start' of a job in a project as the earliest possible time when the job can begin. This is

the first number in the bracket. The early finish time of a job is its early start time plus the time required to perform

the job. We put this as the second number in the same bracket. Thus if in fig. 15 the early start of the job a will be 0

as this is the first job. The early finish 0 + 10 = 10. For convenience we denote the start time of a project as 0. So we

have early start and early finish times as (0, 10) for job a. For job b, the early start time will also start and the early

finish times are (0, 3). The jobs d and g can start, at the earliest, as soon as the job a is completed, because 'a' is the

predecessor for d and g. Hence the early start time for job d will be 10 and early finish time for job d will be

10 + 7 = 17. For the job g the early start and early finish will (10, 10) since g happened to be a dummy job. Next we

take the job c which has two predecessors namely b and g. The job c can be started, at the earliest on 10. So the job c

can start, at the earliest only on 10 and the early finish of the job c will be 10 + 4 = 14. Similarly the early start of

job e is 17 and finish is 17 + 4 = 21. The job f has two predecessors namely c and e, c is finished at the earliest on 14

and e on 21. So, the job f can start at the earliest only on 21 and finished at the earliest on 33.

All the above data are recorded as shown in figure 15.

d(10,17)

(0,10)

(10,10)

4 e

(17,21)

(0,3)

(21,33)

c (10,14)

Early - Start

Early - Finish

Schedule

Fig. 15

Operations Research (MTH601)

Thus the project can be completed in 33 days. If the earliest completion time of the project is 33 days

after it has begun, the longest path through the network must be 33 days in length. When we compare the alternate

paths available for completion of the project (a-d-e-f = 33; a-g-c-f = 26; b-c-f = 19) from the beginning to the end we

will find that the critical path is 33 days, with the jobs a, d, e, f on the critical path.

Late start and Late finish programme

The activities not on the critical path can be delayed without delaying the completion date of the project. A

normal question may arise at this juncture as to how much delay can be allowed for non-critical jobs. How late can a

particular activity be started and still maintain the length of the project duration? For answering these questions we

find the late start and late finish times for each activity in the project graph.

We define the late start of an activity as the latest time that it can begin without pushing the finish date of

the project further into the future. Similarly late finish of an activity is the late start time plus the activity duration.

We have seen that the early start and early finish time of activities are calculated in the forward direction

from left to right. To calculate the late start and late finish times, we begin at the end of the network and work

backwards. In the example cited above we begin with the node 6. The job leading to the node is job f. It must be

completed by day 33 so as not to delay the project. Therefore, day 33 is the latest finish. In general duration of the

critical path will be taken as the late finish time of the project.

The time taken for the activity f is 12 days, so that it must begin at day 21 and end on 33. Thus the late start

of the activity f is day 21.

We represent the late start and late finish times of the activity f within brackets (21, 33) in figure16. The

job f has two predecessors namely c and e. The late-finish times for both jobs can be take as day 21. If this is so, c's

late start will be 21-4 or day 17 and e's late start will be 21-4 or day 17. We can record the late start and late finish

times jobs c and e in the figure within brackets.

Now, the job d is the only predecessor to e and d can finish as late as day 17 which is the late start of e, so d

can start as late as on day 10. Coming to the activity g, which is the predecessor to c, the late finish time of job g is

the same as late start time of c. So late start and late finish time of g will be (17, 17). Since b precedes c, b also can

finish as late as on day 17 and start as late as on day 14.

d (10, 17)

(0, 10)

g (17, 17)

(17, 21)

(21, 33)

(14, 17)

(17, 21)

Late - Start

Late - Finish

Schedule

Operations Research (MTH601)

Fig. 16

Next we take job a, which has two successors namely d and g, which have days 10 and 17 as the late start

times respectively. So the job a must finish as late as on day 10 in order that a can be made to start on day 10. The

finish time of the activity a will be least of the late start time of the successor activities. Hence the late finish of the

activity a must be day 10 and it starts on day 0. This is also shown figure 16.

The above information of early start-early finish programme and late start-late finish programmes is very

useful as we shall see next.

Slack or Float

In the figure 15 and figure 16 which represent the early start-early finish and late start-late finish

programmes, we observe that the late start and early start times are identical for some jobs. (Similarly late and early

finish times). For example for the job a, the early and late start time is 0, for the job d, early and late start time is 10,

for e they are 17 and for f also they are 21, whereas for job b the early start is day 0 and late start is day 14. This

indicates that the job b can start as early as day 0 or as late as on day 14, without delaying the project completion

date of 33 days. This difference between late start of the job and the early start of the same job is called as 'slack' or

'float'. It is also termed as 'total slack' or 'total float'. This denotes the maximum delay that can be allowed for this

job. Similarly for job g, the early start time is day 10 and late start time is 17. There is a difference of 7 days which

is the slack for job 'g'. Similarly we have a slack of 7 days for the job 'c' also.

The jobs having no slack thus become critical and the jobs with slacks are non-critical. So if we connect the

jobs having no slacks, we get the critical path. This is the method of finding the critical path. In the example the jobs

a, d, e, f have no slack and the path connecting a, d, e and f or 1-2-4-5-6 becomes the critical path.

We can summaries the slack for all jobs given in the tabular below.

Jobs

Early

Late

Slack

start

finish

start

finish

This critical path is shown in figure 17

Operations Research (MTH601)

Fig. 17

Free Slack:

Free Slack is defined as the amount of time an activity can be delayed without affecting the early start time

of any other job. In other words, the free slack of any activity is the difference between its early finish time and the

earliest of the early start times of all its immediate successors. In the example above, if we take the activity b, its

early finish time is day 3 and its immediate successor c starts at the earliest on day 10. 'c' can start as late as on day

17, but there is not compulsion on c to start exactly on day 10. If he chooses to start on day 10 (earliest start time)

ten b will b\have only 7 days as free slack (difference between early start of c and early finish of b). Similarly for the

job c also we have free slack as the difference between the early finish of c and early start of its immediate successor

'f' i.e. 21-14 = 7 days. Free slack can never exceed total slack. The total slack and free slack for all activities are

given in the following table.

Activity

Total Slack

Free Slack

Independent slack:

It is that portion of the total float within which an activity can be delayed for start without affecting slacks

of the preceding activities. It is computed by subtracting the tail event slack from the free float. If the result is

negative it is taken as zero.

Example The following table gives the activities of a construction project and duration.

Activity

1-2

1-3

2-3

2-4

3-4

4-5

Duration (days)

(i) Draw the network for the project.

(ii) Find the critical path.

(iii) Find the total, free and independent floats each activity.

Solution:

The first step is to draw the network and fix early start and early finish schedule and then late

start-late finish schedule as in figure 18 and figure 19.

Operations Research (MTH601)

(20, 32)

(0, 20)

10 (20, 30)

(36, 46)

(30, 36)

(0, 25)

Early-Start

Early-Finish

Schedule

Fig. 18

(24, 36)

(0, 20)

(20, 30)

(36, 46)

(30, 36)

(5, 30)

Late-Start

Late-Finish

Schedule

Fig. 19

Activity

Total Slack

Free Slack

Independent

Slack

1-2

1-3

2-3

2-4

3-4

4-5

To find the critical path, connect activities with 0 total slack and we get 1-2-3-4-5 as the critical path.

Check with alternate paths.

1-2-4-5

= 42

1-2-3-4-5 = 46*

(critical path)

1-3-4-5

= 41

5PERT MODEL

Operations Research (MTH601)

PERT was developed for the purpose of solving problems in aerospace industries, particularly in research

and development programmes. These programmes are subject to frequent changes and as such the time taken to

complete various activities are not certain, and they are changing and non-standard. This element of uncertainty is

being specifically taken into account by PERT. It assumes that the activities and their network configuration have

been well defined, but it allows for uncertainties in activity times. Thus the activity time becomes a random variable.

If we ask an engineer, or a foreman or a worker to give a time estimate to complete a particular task, he will at once

give the most probable time required to perform the activity. This time is the most likely time estimate denoted by

tm. It is defined as the best possible time estimate that a given activity would take under normal conditions which

often exist.

But he is also asked to give two other time estimates. One of these is a pessimistic time estimate. This is the

best guess of the maximum time that would be required to perform an activity under the most adverse circumstances

(1)

supply of materials not in time

(2)

non-cooperation from the workers

(3)

the transportation arrangements not being effective etc.

Thus the pessimistic time estimate is the longest time the activity would require and is denoted by tp. On

the other hand if everything goes on exceptionally well or under the best possible conditions, the time taken to

complete an activity may be less than the most likely time estimate. This time estimate is the smallest time estimate

known as the optimistic time estimate and denoted by to.

Thus, given the three time estimates for an activity, we have to find the expected duration of an activity or

expected time of an activity as a weighted average of the three time estimates. PERT makes the assumption that the

optimistic and pessimistic activity (to and tp) are occur. It also assumes that the most probable activity time tm, is four

times more likely to occur than either of the other two. This is based on the properties of Beta distribution. Beta

distribution was chosen as a reasonable approximation of the distribution of activity times. The Beta distribution is

unimodel, has finite non-negative end points and is not necessarily symmetrical-all of which seen desirable

properties for the distribution of activity times. The choice of Beta distribution was not based on empirical data.

Since most activities in a development project occur just once, frequency distribution of such activity times cannot

be developed from past data.

So, if we follow Beta distribution with weights of 1, 4, 1 for optimistic, mostly likely and pessimistic time

estimates respectively a formula for the expected time denoted by te can be written as

to + 4tm + t p

te =

For example if we have 2, 5 and 14 hours as the optimistic (to), most likely (tm) and pessimistic (tp) time

estimate then the expected time for the activity would be

2+4(5)+14

te =

= 6 hrs

Operations Research (MTH601)

If the time required by an activity is highly variable (i.e) if the range of our time estimates is very large,

then we are less confident of the average value. We calculate them if the range were narrower. Therefore it is

necessary to have a means to measure the variability of the duration of an activity. One measure of variability of

possible activity times is given by the standard deviation of their probability distribution.

PERT simplifies the calculation of standard deviation denoted by St as estimated by the formula,

t p - to

St =

St is one sixth of the difference between the two extreme time estimates, namely pessimistic and optimistic time

estimates. The variance Vt of expected time is calculated as the square of the deviation.

⎛ t p - to ⎞

Vt = ⎜

⎜ 6 ⎟

(i.e.)

⎟

⎝

⎠

In the example above

14-2

St =

= 2 hrs

(14-2)2

= 4 hr2

Vt =

Table of Contents: