Thursday, November 25, 2010

Algorithm for quickly drawing activity networks

Caveat: this post is probably going to be long and tedious; it certainly will be boring. If you're not interested in drawing activity networks (the first step in CPM or PERT analyses in project management), then don't read on. You have been warned....

The exam in Project Management is about two weeks in the future. At the moment I am somewhat under-employed at work, so I am using the time to go over exam questions. I have noticed that it takes me about three or four attempts to draw an activity network, time which could be better spent elsewhere. I thus need a method which will allow me to draw the network correctly on the first attempt.

After googling several sites, I finally found what I was looking for. As Heriot Watt displays the data in a slightly different manner, I modified the algorithm displayed therein. After playing with the algorithm a few times, I discovered that I can significantly speed it up whilst not losing any accuracy. So I'm going to present my version of the algorithm here - all errors are thus mine!

Here is the data:

Table 1: Estimated activity times for works to be completed by Contractor X
ActivityOptimistic time (weeks)Likely time (£)Pessimistic time (weeks)
A–B123
B–C369
B–H456
C–D81012
D–E345
D–F234
E–G345
F–J123
G–H135
G–I468
G–K135
H–L123
I–L123
I–M4710
J–K123
K–M123
L–M234
M–N234
As there are optimistic and pessimistic times quoted in the data, one can assume that this is going to be PERT analysis. This makes no difference when drawing the activity network.

Here's the algorithm:
repeat
1. List all the current nodes (A, B, C, etc. This list will shorten during execution)
2. Cross off each destination node which can be reached by a node on the list (if the activity is AB, then one crosses B off the list)
3. Remove from the list all uncrossed nodes and put them aside
until the list is empty

So: the initial list is all the nodes: A, B, C, D, E, F, G, H, I, J, K, L, M, N.
First iteration: everything gets crossed off the list bar A (not surprisingly as this is the starting node).
Second iteration: everything gets crossed off the list bar B (as A is no longer on the list, no node has B as a destination node)
Third iteration: everything gets crossed off the list bar C
Fourth iteration: everything gets crossed off the list bar D (I warned you this would be tedious)
Fifth iteration: everything gets crossed off the list bar E and F
Sixth iteration: everything gets crossed off the list bar G and J
Seventh iteration: everything gets crossed off the list bar H, I and K
Eighth iteration: everything gets crossed off the list bar L
Ninth iteration: everything gets crossed off the list bar M
Tenth iteration: everything gets crossed off the list bar N

The result of the above is a grid with ten columns and three rows, like this:




EGHL
ABCDFJIMN
K


In practice, one doesn't actually draw the grid. Here one discovers that the algorithm isn't sufficient and that one needs two heuristics. When there are two (or even three) nodes in a column, how does one know their vertical placement? One heuristic which I developed is that the node with the most activities should be placed in the middle. If one considers H, I and J: H only leads to L, whereas I leads to L and M; K leads only to M. So I has to be in the middle. Why are H and K the way they are? Because G leads to H whereas J leads to K, and this is the easiest way of drawing the connections. As I leads both to L and M, L has to be "above" M. The second heuristic is that the final position of each node in the grid is dependent on the preceding and succeeding nodes and can only be determined when actually drawing.

Here's the activity network as given in the worked answer
Here, E is effectively in row 2 and F in row 3, as opposed to 1 and 2, but that's not important.

For reasons which I don't entirely understand, we are not allowed to use scrap paper during the exam; everything has to be written in the bound answers book, although scrap workings can be crossed out and labeled 'scrap'. Using this technique will save the amount of scrap working that I have to produce, and will naturally save time. Unfortunately, it's going to be a bit difficult copying the clean network from the scrap workings.

No comments: