The Critical Path method is a technique used in Software Engineering to map out the best order of execution of project activities in order to complete the project in the least amount of time.
The final path that is mapped out is referred to as the critical path.
Often in software engineering, a project is decomposed into activities and sub-activities (or tasks and sub-tasks) before it begins. These decomposed tasks may or may not depend on one another for completion. Let’s consider an example.
The following table represents a project that has been decomposed into activities ranging from A to F.
Task | Predecessor | Duration |
A | - | 5 |
B | A | 4 |
C | A | 5 |
D | B | 6 |
E | C | 3 |
F | D, E | 4 |
Each task is associated with a duration that represents the approximate time needed to complete the task.
Further, some tasks have predecessors. Predecessors represent dependency. This means that before a particular task is started, its predecessors must already be completed.
Before we can proceed to finding the critical path, we draw out the precedence diagram.
This is a network diagram that shows us all the activities (referred to as nodes) within the project, and uses arrows (→) to represent the dependencies.
The precedence (or activity-on-node) diagram starts with the independent node: an activity with no predecessors. In the above example, this node is A.
The following is the precedence diagram for the project described above:
Once we have the precedence diagram, we proceed to add more detail to it.
This is achieved by replacing each node with the following box:
The following legend describes the box above:
The slack time for an activity is defined as the amount of time an activity can be delayed without causing another activity to be delayed as well.
Filling in values for the detailed diagram will require two passes of the precedence diagram: a forward pass, and a backward pass.
During the forward pass, we move from the starting node to the final node and fill in values for ES, D, and EF.
The ES value for an independent activity will be 0.
The ES value for an activity with predecessors is the maximum EF value among its predecessors.
The EF value for a node is the sum of its ES and D values.
After the forward pass, our detailed precedence diagram looks like this:
During the backward pass, we move from the final node to the starting node and fill in values for LS, ST, and LF.
The LF value for the final node will be equal to its EF value.
The LF value for predecessor nodes is equal to the minimum LS value of the successor nodes.
To calculate ST, the following formula may be used:
To calculate LS, the following formula may be used:
After the backward pass, the detailed precedence diagram looks like this:
To map out the critical path, we will traverse the precedence diagram from start to finish in such a way that our total slack time remains minimum, or ideally, zero.
We can see that the above diagram gives us two paths from start to finish. These are:
A → C → E → F
A → B → D → F
For the first path (A → C → E → F), the total slack time is 4 (0 + 2 + 2 + 0).
For the second path (A → B → D → F), the total slack time is 0 (0 + 0 + 0 + 0).
The critical path for the project is:
A → B → D → F
The above critical path provides us with an efficient order of execution for the activities that keep the total slack time at 0.
Free Resources