Given a list of activities required to complete a project along with the duration of each activity and the dependencies between activities, the objective of the Critical Path Method (CPM) is to determine the sequence of activities that minimizes the latest completion time.
Problem Statement
Managing a large-scale project requires coordinating many activities of varying duration and involving numerous dependencies. PERT (Program Evaluation and Review Technique) and CPM (Critical Path Method) are two closely-related operations research techniques that use networks to coordinate activities, develop schedules, and monitor progress of projects. PERT and CPM were developed independently in the 1950s. While the original versions differed in some important ways, the two techniques had much in common. Over time, the techniques have merged and, for the most part, the names are used interchangeably or combined in a single acronym, PERT/CPM.
We introduce a small example that will be used to illustrate various aspects of CPM. Suppose we are constructing a new building; the required construction activities are shown in the table below along with the estimated duration of each activity and any immediate predecessors. An immediate predecessor of an activity \(y\) is an activity \(x\) that must be completed no later than the starting time of activity \(y\). When an activity has more than one immediate predecessor, all of them must be completed before the activity can begin.
| Activity | Duration (weeks) | Predecessor(s) |
| A | 2 | none |
| B | 3 | A |
| C | 3 | A |
| D | 4 | C |
| E | 8 | D |
| F | 6 | B, E |
| G | 2 | F |
There are many questions to be answered when scheduling a complex project but two of the important questions are:
- What is the total time required to complete the project if no delays occur?
- What are the critical bottleneck activities?
A project network is used to represent a project and to show the relationships between the activities. In an activity-on-node (AON) network, each activity is represented by a node. Each predecessor relationship is represented by an arc; there is an arc from node \(i\) to node \(j\) if the activity at node \(i\) is an immediate predecessor to the activity at node \(j\). The duration of the activity at node \(i\) is recorded next to node \(i\). The figure below shows a network representation of the project information from the table above.
1. What is the total time required to complete the project?
If we add up the times required for all of the activities, we get 28 weeks. However, this is not the best answer to the question, since some of the activities can be performed at the same time. Instead, to determine the total time required, we want to consider the length of each path through the network. A path through the network is a route made up of nodes and arcs that traverses the network from the start node to the finish node. The length of a path is the sum of the durations of the activities on the nodes along the path. In this simple example, there are two paths through the network:
- start -> A -> B -> F -> G -> finish, with a length of 13
- start -> A -> C -> D -> E -> F -> G -> finish, with a length of 25
The project duration will be no longer than the longest path through the network. Therefore, the total time required to complete the project equals the length of the longest path through the network — and this longest path is called the critical path. In the example, the total time to complete the project should be 25 weeks if no delays occur.
2. What are the critical bottleneck activities?
The critical bottleneck activities are the activities that are “critical” to completing the project on time; a delay in a critical bottleneck activity will delay the project completion time. Therefore, the activities on the critical path are the critical bottleneck activities. In our example, the critical bottleneck activities are A, C, D, E, F, and G; the project should be managed to avoid delays in any of these activities. There is also a positive aspect to knowing the critical bottleneck activities; a reduction in the duration of a critical bottleneck activity may reduce the time required to complete the project.
Mathematical Formulation
For small projects, it is possible to enumerate all of the paths and identify the critical path. For larger, more complex projects with many dependencies, a more efficient procedure is required. One approach is to formulate the project scheduling problem as a linear programming problem; due to the underlying network structure, even large problems can be solved efficiently. Thus, given a list of activities required to complete a project along with the duration of each activity and the dependencies between activities, the objective of the Critical Path Method (CPM) is to determine the sequence of activities that minimizes the latest completion time.
Sets
\(A\) = set of activities, e.g., \(P = \{A, B, C, D, E, F, G\}\)
\(P\) = set of predecessor pairs, e.g., element \((i,j)\) means that activity \(i\) is an immediate predecessor of activity \(j\)
Parameters
\(d_i\) = duration of activity \(i\), \(\forall i \in A\)
Decision Variables
\(T\) = total time required to complete the project
\(s_i\) = start time of activity \(i\), \(\forall i \in A\)
Objective Function
minimize \(T\)
Constraints
The total time to complete the project must be greater than or equal to the start time plus the duration of all of the activities.
\(s_i + d_i \leq T, \forall i \in A\)
For each predecessor pair \((i,j)\), the start time of activity \(j\) must be greater than or equal to the start time of activity \(i\) plus the duration of activity \(i\).
\(s_i + d_i \leq s_j, \forall (i,j) \in P\)
\(s_i \geq 0\)
To solve this linear programming problem, we can use one of the NEOS Server solvers in the Linear Programming (LP) category. Each LP solver has one or more input formats that it accepts.
GAMS Model
Here is a GAMS model for the example shown above.
set activity / A*G/;
alias (activity,i,j);
set prec(i,j) /
A.(B,C), (B,E).F, C.D, D.E, F.G /;
parameter duration(activity) / A 2, B 3, C 3, D 4, E 8, F 6, G 2 /;
free variable time;
nonnegative variable s(i);
equations ctime(i)
ptime(i,j) ;
ctime(i).. time =g= s(i) + duration(i);
ptime(prec(i,j)).. s(i) + duration(i) =l= s(j);
model schedule /all/;
solve schedule using lp minimizing time;
display time.l, s.l;
If we submit this LP model to Mosek, we obtain a solution with an objective function of 25, meaning that the total time to complete the project is 25 weeks (with no delays). From the values of the \(s(i)\) variables, we obtain a start time for each activity: \(B\) starts at 2, \(C\) starts at 2, \(D\) starts at 5, \(E\) starts at 9, \(F\) starts at 17, and \(G\) starts at 23. What we do not easily obtain from the LP solution is the sequence of nodes on the critical path. The real benefit of using linear programming for project scheduling comes when we need to consider additional constraints or when we want to consider time-cost trade-offs for individual activities.
In some cases, it may be possible to “crash an activity”; that is, the duration of the activity can be reduced by completing it using more costly measures. For example, the duration of an activity might be reduced by working overtime, hiring additional workers, using special equipment, or using more expensive materials. In the extended version of the problem, we assume that there is a set of (duration, cost) pairs associated with each activity. (For example, activity \(x\) has a normal duration of 6 weeks at a cost of $100 or a reduced duration of 4 weeks at a cost of $150.) The objective of the time-cost trade-off problem is to determine how much (if any) to crash each activity in order to reduce the total time to complete the project to pre-specified value. Chapter 9 in Hillier and Lieberman’s textbook provides a detailed example of this method.
Applet
There is a Java applet available on the Cut the Knot website: Scheduling and Critical Path Algorithm.
References
- Hillier, F. S. and Lieberman, G. J. 2005. Chapter 22: Project Management with PERT/CPM. Introduction to Operations Research, 8th ed.. McGraw Hill, Boston, MA.
- Rutherford, T. F. 2011. Lecture Notes: Linear Programming Formulation Exercises, October 11, 2011.