Third Shelf

As part of planning a software project, it is always important to pay attention to the activities and the order in which they execute. This is known as a project schedule.

To create a project schedule, we have to model the project’s activities and their dependencies. Or, if you prefer, their relationships. A project schedule is typically drawn as a graph — arrows joining circles. The fancy way saying this is, edges for the arrows (a.k.a links) and vertices for the circles (a.k.a nodes). This type of graph is typically drawn from left to right, with the project’s starting date on the left.

So, what do the circles and arrows mean? Well, it depends.

Activity-on-node

This is a simple graph where the circles represent the activities and the arrows the dependencies. It is also known as a precedence network. We call it a precedence network because a node, or activity, cannot be executed until all of its preceding activities executed.

To draw an activity-on-node graph, we have to follow some rules:

• only one starting node;
• only one ending node;
• each activity has a duration;
• links have no durations;
• time moves from left to right;
• the graph may not contain any loops;
• the graph may not contain any dangles – a node that just stops in the middle of nowhere.

By the way, this activity label is based on British Standard BS 4335.

Critical Path applied to Activity-on-node

A critical path is the order in which we should execute activities, so that we can get the project done as fast as possible. Not only that, it also shows us which activities will cause us to miss the end date, if they are delayed. How do we determine the critical path?

Well, for each activity we need to have some idea of, how long it will take to do, what is the earliest we can start and complete the activity as well as the latest we can start and complete it. That is the Duration, Early Start, Early Finish, Late Start and Late Finish parts of the activity label.

To calculate the earliest dates, we need to do something called a forward pass. That is, we look at every activity and calculate its early start and early finish dates. The first activity’s early start values always starts at zero.

In the network graph above, we see that Task A and Task C can start immediately. However, Task B must wait until Task A and Task C completes (it’s predecessors). Since Task C has the longest duration (10 days) between Task A and Task C, Task B can only start in 10 days and will complete on day 13. The earliest that Task D can start is in 2 days time, after Task A completed. With this in mind, the earliest that the project can complete is in 13 days time.

Next, we need to do a backward pass on the same network to calculate the Late Start and Late Finish values. This gives us the latest date at which an activity must start and complete without delaying the end date of the project. The late finish date for the project is the same as the early finish date.

In this example, we see that the project will complete in 13 days. So, we work from the end date backwards. Starting at 13 days, we can see that Task B will take 3 days to complete and so the latest start date is 10 days (13-3). Task D also needs to finish on day 13.  This task takes 4 days to complete and so the latest date to start this task is in 9 days time (13-4). Task C on the other hand must finish within 10 days and has to start immediately (10-10). Since Task A will take 2 days to complete and we know that the latest finish date is only in 9 days time, we only have to start this task on day 7 (9-2).

To find the critical path in the graph, we find the sequence of tasks that will move the end date, if there is a delay in any of its activities.

If there is a delay in Task C so that it only completes on day 11, it will delay Task B and ultimately the end date. We have to pay special attention to the critical path throughout the project so that we can handle any delays as soon as possible. The critical path sets the activity span. That is, the shortest time in which we can complete the project. If we want to shorten the time of the project, we have to cut the time of the activities in the critical path.

Activity-on-arrow

In activity-on-arrow networks, the arrows, or links, represent the activities. The nodes represent events of activities starting or finishing. Just like the activity-on-node graph, so too activity-on-arrow graphs have rules when it comes to drawing the network graph. They are:

• only one starting node;
• only one ending node;
• duration is on the link;
• nodes have no duration;
• time moves from left to right;
• nodes are numbered sequentially;
• graph may not contain any loops;
• graph may not contain any dangles.

Critical Path applied to Activity-on-arrow

Before we can find the critical path in an Activity-on-arrow graph, we need to do a forward pass. It follows the same principles as activity-on-node. The only exception is that in activity-on-arrow we use the events and not the activity start and end dates.

Let’s look at an example (Hughes and Cotterell, 2009):

The earliest date when an event can start is the date when all the events that it depends on is complete. In the example above, activities A, B and F can start immediately. So, the earliest date for event 1 is zero. Since activity A takes 6 weeks to complete, we can only start activity 2 in 6 weeks time at the earliest. Activity B takes 4 weeks to complete and so event 3 can only be achieved in week 4. Activity F is dependent on the ending date of activity E and so we only know that activity F will complete in 10 weeks. Activity E can start in 4 weeks time and will take 3 weeks to complete. From that we know that activity E will only end in 7 weeks time. We then take the longer of the two ending dates (between E and F) and find that event 5 will only be achieved in 10 weeks time. Event 4 can only start in week 9 (6 + 3) > (4 + 4).  We now see that the project will only finish at the end of week 13, at the earliest.

Next, we do a backward pass on the same graph to calculate the latest date at which each event should be achieved. It follows the same principles as the backward pass for activity-on-node.

To find the critical path, we make use of slack. Slack is the difference between the earliest date and latest date. It tells us how late an event can be without affecting the end date of the project. The critical path is that path with all the nodes having a zero slack.

References

1. Hughes, B. & Cotterell, M. 2009. Software Project Management, 5e. Berkshire: McGraw-Hill Education.