This method is an old OR favourite. It was developed in the late fifties and is still a very popular practical tool. In this module we use it as an illustration of dynamic programming (DP) in action.
To explain the method it would be best ot consider the data displayed in the following table for a very small project:
Activity | Duration
(days) | Immediate
Predecessors |
Training | 6 | -- |
Purchasing | 9 | -- |
Production | 8 | Training, Purchasing |
Quality Control | 7 | Training, Purchasing |
Assembling | 10 | Quality Control |
Transporting | 12 | Assembling |
It is a small project consisting of six activities or jobs
Observe that for each activity we must have three pieces of information: its title (obviously), its duration and its set of immediate predecessors. The first two are obvious, so we shall examine only the third.
If an activity does not have any immediate predecessors (eg. Training and Purchasing), then it can commence immediately. On the other hand, if an activity does have immediate predecessors, then it cannot commence before the completion of all its immediate predecessors. For example, Production cannot commence before Training and Purchasing have both been completed.
The mission of the critical path method is to determine how early can the project be completed and to identify the critical activities, namley the activities whose delays will cause a delay in the completion of the entire project.
The dynamic programming approach to this problem is based on the following innocent looking concepts:
| ET[A] := | Earliest time that activity A can commence (given the precedence constraint and the duration of its predecessors) |
| LT[A] := | Latest time that activity A can be completed without causing a delay in the completion of the entire project. |
(1) | TF[A] := | (LT[A] - ET[A]) - t(A) (total float of activity A.) |
The total float of an activity is then (by definition) the longest possible delay in the completion of this activity that will not cause a delay in the completion of the entire project. This suggest the following intuitive notion:
| Critical activity := | An activity whose total float is equal to zero (TF[A]=0) |
In short, all we have to do to identify the critical activities is compute (as prescribed by (1)) the total floats of all the activities and identify those activities whose total floats are equal to zero. This means that we have to compute the ETs and LTs for all the activities. The following are typical DP observation. If you have difficulties understanding their logic, have a quick look the shortest path problem. But first some notation and terminology:
| | P[A} := | Set of all immediate predecessors of activity A. |
| | S[A] := | Set of all immediate successors of activity A. |
| | T := | Completion time of the entire project, assuming no delays. |
| | Initial activity := | An activity with no predecessors (P[A] is empty). |
| | Terminal activity := | An activity with no successors (S[A] is empty). |
The first observation indicates the obvious, namely it observes that the activities that do not have immediate predessors can commence immediately and that the last activity to be completed must be an activity with no immediate successors:
(5) | ET[A] = | max { t(x) + ET(x): x in P[A] } , if P[A] is not empty. |
(6) | LT[A] = | min { LT(x) - t(x) : x in S[A] } , if S[A] is not empty. |
Our DP code is based on these functional equations.
It is common practice to produce a Gantt Chart for project management problems. Don't panic if you do not know exactly what a Gantt chart is and how to draw it. Have a look at the following table which is the Gantt Chart for the problem specified by the table above.
|
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
|
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
Purchasing |
|
|
Quality Control |
|
|
|
Assembling |
|
|
|
Transporting |
|
|
Training |
|
|
|
Production |
|
|
|
|
| Time (days) |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1
0 |
1
1 | 1
2 | 1
3 | 1
4 | 1
5 | 1
6 | 1
7 | 1
8 | 1
9 | 2
0 |
2
1 | 2
2 | 2
3 | 2
4 | 2
5 | 2
6 | 2
7 | 2
8 | 2
9 | 3
0 |
3
1 | 3
2 | 3
3 | 3
4 | 3
5 | 3
6 | 3
7 | 3
8 |
Critical Activity | Non-critical activity | Total float |
The JavaScript facility is not complete yet but you can definitely experiment with it. It provides a spreadsheet like input form and will determine the critical path and plot the Gantt Chart. However, it does not provide at present any facility to examine the intermediate results.