J E Beasley

OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

Network analysis


Network analysis is the general name given to certain specific techniques which can be used for the planning, management and control of projects. One definition of a project (from the Project Management Institute) is

This definition serves to highlight some essential features of a project

With regard to the use of the word unique I personally prefer to use the idea of "non-repetitive" or "non-routine", e.g. building the very first Boeing Jumbo jet was a project - building them now is a repetitive/routine manufacturing process, not a project.

We can think of many projects in real-life, e.g. building the Channel tunnel, building the London Eye, developing a new drug, etc

Typically all projects can be broken down into:

and the problem is to bring all these activities together in a coherent fashion to complete the project.

Two different techniques for network analysis were developed independently in the late 1950's - these were:

PERT was developed to aid the US Navy in the planning and control of its Polaris missile program . This was a project to build a strategic weapons system, namely the first submarine launched intercontinental ballistic missile, at the time of the Cold War between the USA and Russia. Military doctrine at that time emphasised 'MAD - mutually assured destruction', namely if the other side struck first then sufficient nuclear weapons would remain to obliterate their homeland. That way peace was preserved. By the late 1950s the USA believed (or more importantly believed that the Russians believed) that American land based missiles and nuclear bombers were vulnerable to a first strike. Hence there was a strategic emphasis on completing the Polaris project as quickly as possible, cost was not an issue. However no one had ever build a submarine launched intercontinental ballistic missile before, so dealing with uncertainty was a key issue. PERT has the ability to cope with uncertain activity completion times (e.g. for a particular activity the most likely completion time is 4 weeks but it could be any time between 3 weeks and 8 weeks).

CPM was developed in the 1950's as a result of a joint effort by the DuPont Company and Remington Rand Univac. As these were commercial companies cost was an issue, unlike the Polaris project mentioned above. In CPM the emphasis is on the trade-off between the cost of the project and its overall completion time (e.g. for certain activities it may be possible to decrease their completion times by spending more money - how does this affect the overall completion time of the project?)

Modern commercial software packages tend to blur the distinction between PERT and CPM and include options for uncertain activity completion times and project completion time/project cost trade-off analysis. Note here that many such packages exist for doing network analysis.

There is no clear terminology in the literature and you will see this area referred to by the phrases: network analysis, PERT, CPM, PERT/CPM, critical path analysis and project planning.

Network analysis is a vital technique in PROJECT MANAGEMENT. It enables us to take a systematic quantitative structured approach to the problem of managing a project through to successful completion. Moreover, as will become clear below, it has a graphical representation which means it can be understood and used by those with a less technical background.


We will illustrate network analysis with reference to the following example: suppose that we are going to carry out a minor redesign of a product and its associated packaging. We intend to test market this redesigned product and then revise it in the light of the test market results, finally presenting the results to the Board of the company.

After much thought we have identified the following list of separate activities together with their associated completion times (assumed known with certainty).

Activity                                                   Completion 
number                                                     time (weeks)
1         Redesign product                                      6
2         Redesign packaging                                    2
3         Order and receive components for redesigned product   3
4         Order and receive material for redesigned packaging   2
5         Assemble products                                     4
6         Make up packaging                                     1
7         Package redesigned product                            1
8         Test market redesigned product                        6
9         Revise redesigned product                             3
10        Revise redesigned packaging                           1
11        Present results to the Board                          1

It is clear that in constructing this list of activities we must make judgements as to the level of detail (timescale) to adopt. At one extreme we could have just a single activity "do the project" and at the other extreme we could try to break the project down into hourly activities. The appropriate timescale to adopt (which can be different for different activities) grows out of our knowledge of the situation and experience.

Aside from this list of activities we must also prepare a list of precedence relationships indicating activities which, because of the logic of the situation, must be finished before other activities can start e.g. in the above list activity number 1 must be finished before activity number 3 can start.

It is important to note that, for clarity, we try to keep this list to a minimum by specifying only immediate relationships, that is relationships involving activities that "occur near to each other in time".

For example it is plain that activity 1 must be finished before activity 9 can start but these two activities can hardly be said to have an immediate relationship (since many other activities after activity 1 need to be finished before we can start activity 9).

Activities 8 and 9 would be examples of activities that have an immediate relationship (activity 8 must be finished before activity 9 can start).

Note here that specifying non-immediate relationships merely complicates the calculations that need to be done - it does not affect the final result. Note too that, in the real-world, the consequences of missing out precedence relationships are much more serious than the consequences of including unnecessary (non-immediate) relationships.

Again after much thought (and aided by the fact that we listed the activities in a logical/chronological order) we come up with the following list of immediate precedence relationships.

Activity                            Activity
number                              number
1        must be finished before    3       can start
2                                   4
3                                   5
4                                   6
5,6                                 7
7                                   8
8                                   9
8                                   10
9,10                                11

The key to constructing this table is, for each activity in turn, to ask the question:

"What activities must be finished before this activity can start"

Note here that:

Once we have completed our list of activities and our list of precedence relationships we combine them into a diagram/picture (called a network - which is where the name network analysis comes from). We do this below.

Note first however that we asked the key question above:

(i.e. complete all the activities whilst respecting the precedence relationships).

What would you say, e.g.

One answer could be if we first do activity 1, then activity 2, then activity 3, ...., then activity 10, then activity 11. Such an arrangement would be possible here, (check the precedence relationships above), and the project would then take the sum of the activity completion times, 30 weeks.

However could we complete the project in less time? It is clear that logically we need to amend our key question to be:

We shall see below how the network analysis diagram/picture we construct helps us to answer this question.

Note too here that, at this stage, we are merely planning the project - we have not started any of the various activities mentioned above.

Network diagram construction

The network diagram we construct is different depending upon whether we are going to use an activity on node or an activity on arc network.

As will become apparent below this network diagram represents clearly and concisely the entire project - enabling us to get a pictorial overview of what is to happen, the various activities and their relationship one to another.

Now go to activity on node or activity on arc. If you are new to this topic then I suggest you use activity on node as it is (at least in my view) easier to follow. Also note here that (to prevent duplication of material) it is only under activity on node that I discuss the computer (package) solution of the above example.