Original Critical Path Method and beyond

Recently I have organised a Linked Poll on the origin of the Critical Path Method:

The accurate response, which was supported by a credible paper, was promptly shared in the comments, but it had little influence on the result. Nearly all participants stated that it relied on either a “single estimation” (48%) or a “3-point estimation” (41%). Merely 11% (!) provided the correct answer, which is that the critical path method originally requires estimation of each activity with time and cost ranges. These ranges extended from Optimistic to Normal estimates, as opposed to extending from optimistic to pessimistic estimates, as some respondents may have believed.

Let’s review how the Critical Path Method evolved over the time and what we can learn from the origin.

The Critical Path Method (CPM) initially had two main phases. The first phase was known as the “time analysis phase,” while the second was the more complex “time-cost trade-off phase.” This is why CPM emerged in the late 1950s, as computers became accessible for analysis. The first phase, involving schedule time analysis, was quicker perform manually. However, the second phase, which required a heuristic solution, could not be carried out effectively without the aid of a computer.

Over the time the critical path method was split into two separate methods. The first phase of the original technique evolved into today’s CPM method, while the second phase became what we now know as the ‘CPM Least Cost Scheduling Technique’. Now most project delivery tools are only capable of supporting the first phase and do not include time-cost optimization analysis. These tools can calculate just two basic CPM metrics: Total Float and Free Float. They lack support for schedule optimization methods and metrics like Critical Path Activity Drag, Drag Cost, FLEX, Super Float. etc. 

The fundamental assumption of the CPM model is that it is possible to assign a time range for each activity, indicating the time frame within which the activity is expected to be completed.

The duration of most tasks can fluctuate based on factors like the number of work crews, the efficiency of the machinery used, and the length of the workday, material supply. Typically, planners develop plan assuming a standard crew size, regular workdays, and the use of “owned” equipment when estimating the activity duration. These estimated activity durations under these conditions are referred to as Normal durations. When time is not a critical factor, management often allocates resources at the normal level.

In the CPM cost model, there’s another method for estimating time. In this approach, management considers the quickest possible time to complete activities. When there’s a strong deadline, management may allocate the best available resources and work around the clock to meet it. The fastest possible time required to complete an activity is termed the Crash Duration. In the CPM cost model, it is assumed that no activity can be completed faster than its crash duration. When management optimizes its resources to achieve each task at its crash duration, this scheduling approach results in a shorter overall project duration.

Changing the activity durations will affect the project duration and the project cost. From the project’s point of view, we can distinguish between two types of cost.

The first type of costs is called the direct cost, and indicates the cost that is directly attributable to a task. The sum of the direct costs of a project’s activities is called the Project Direct Cost.

The other type of costs is called the Indirect or overhead Cost, also known as fixed cost. This type includes the cost factors that are not easily attributable to activities, but rather belong to the whole project. The elements of indirect cost are, for example, the amounts of rent of social facilities, management salaries, interest charges, etc. These costs are usually linear. One day saved on a project saves one day’s fixed costs, ten days saved on a project saves ten times more. The sum of project direct cost and indirect cost is called the Project Total Cost.

In the CPM cost model, there is a special emphasis on the change of the direct cost. The direct cost that is related to normal activity duration is called the Normal Cost. Shortening the duration of an activity to its crash duration usually results in higher accomplishing cost. Premium for overtime will increase the accomplishing cost of an activity. In order to shorten the activity, material costs can also increase.

The cost related to crash duration is called the Crash Cost. The nature of change of the cost can be presented this way.

There is a lower time limit, the crash duration, which no amount of expenditure can shorten. There is an upper limit, which is the normal duration, and one can make no more savings by letting the task go slowly. The change of the cost between the normal and the crash time points is usually convex, i.e., the costs shortening the activity duration by a new additional day are higher than the extra cost increment of the previous shortening.

The upper cost and time limits are not actually the absolute limits but practical upper limits. An activity may cost more and take longer but it doesn’t make sense to do so. Now we are aware that there are some complex scenarios when it is beneficial to increase an activity duration but at that time it probably wasn’t known.

In the CPM cost model, a linear approximation is used instead of the convex activity time-cost curve. Using the linear approximation, the so called Сost Slope can also be defined.

In a network where an activity duration can change between its lower and upper bound, different project durations are possible. The same project duration can be achieved in hundreds of different ways. If all the activities are considered to be accomplished in their normal time, then we get the maximal project duration. If all the activities are considered to be accomplished in their crash time, we get the Minimal Project Duration. Many project durations between these two extremes can be achieved and all of them can be achieved in hundreds of different ways which result in hundreds of different project direct costs. The set of the possible solutions is shown as:

Two points of the set of feasible solutions come automatically. If time analysis is done using normal durations, we will get point ‘All Normal Points’ which is the optimal solution for cost. If time analysis is done using crash durations, we will get point ‘All Crashed Points’ which is the most expensive solution.
The initial goal in the CPM method is to identify the curve of minimum direct costs, which represents the Minimum Direct Cost Solutions.
On this curve also one point represents Time Optimised Solution with the minimum cost in the most accelerated schedule.

If the line of ‘project minimum cost’ is defined, adding line of ‘indirect cost the optimal duration’ allows to determine ‘the least Project total cost’.

Original heuristic method originates from James E. Kelly and Morgan Walker was very sophisticated.

Later to make the CPM time-cost trade-off technique understandable for construction industry experts simpler heuristic method were developed by pioneers of network techniques.

First simple heuristic algorithms were presented by John Fondahl in earlier 60th. A decade later Nicolai Siemens offered an alternative simple CPM method. Both methods are based on the primary-dual theory of operation’s research. In 80th-90th some books were published where these and other methods explained and compared.

Even in recent years science papers dedicated to CPM cost model optimisation were published and can be easily found via internet search.

By May 1957 the CPM theory had advanced to the point where it was felt that the approach would be successful. At that time a cooperative effort to implement the method was undertaken by Remington Rand and duPont in order to determine the extent to which any further work was advisable.

Remington Rand supplied the required programs for duPont’s UNIVAC I computer located in Newark, Delaware. Engineers from DuPont provided a small pilot problem with which to make the preliminary tests. The results of this phase of the development were officially demonstrated in September, 1957. The demonstration showed that the technique held great promise. At the same time testing based on practical implementation indicated that a computer with greater capacity was essential.

First successful implementing of method was actually without calculation of cost. Time priority for the plant shutdown project (Louisville Works) was so obvious that Normal and Crashed costs haven’t been even gathered. While it was only time optimisation, the result (March 1959) was accepted as big success and soon hundreds of CPM papers were published, few algorithms were developed and deployed on to mainframe computers.

Apollo and Artemis were the first large-scale project management systems available on mini-computers (as opposed to mainframes) and the world’s first commercially successful relational database system. Artemis originated as the Artemis Project Management System developed by Metier Management Systems in 1978, a sister product to Apollo, Metier’s first PERT network scheduling system launched in 1977.

After over two decades of success Artemis encountered financial problems similar to many other high technology firms in the post dot.com bubble era but after some transformations the system still exist today under different name – Aurea Planning Solutions.

Two other systems released decades ago still used in project management and have more advanced methods then popular planning tools:

• Micro Planner X-Pert (or X-Pert) is a project management software package in continuous development since 1979.
• Spider Project launched in 1992 has unique methods to calculate Time-Cost balanced project and porfolio delivery plans.

While original CPM was revolutionary it was some problems with this method that are worth to mention. Some of them creates a legacy we have to deal with even now.

• CPM is based on preferred option to deliver project. Practically the result could be achieved more than one way. Different options may require different activities, equipment and skills, not just have different durations and costs. Complex algorithms that support ‘conditional logic’ were proposed but only a few project delivery tools work with conditions since.

• CPM is based on assumption that required resources supply will be available. Practically we know that it is rarely the case. Projects around the Globe continue to be planned with assumption that if resource demand is identified it will be a solution to guarantee timely supply.

• Originally network logic was based on ‘Finish-to-Start’ dependency type only. Later, other dependency types and time lags were proposed. It addresses logical issues but even further increase the complexity of heuristic algorithms.

Even development of logically correct schedule based on Normal durations is a challenge for many projects. It requires good analytical skills but planners are rarely tested on this skill. Many of them know how to use one or two scheduling tools but don’t know theory of scheduling and not able to develop feasible delivery plan that reflect reality.

• Original CPM didn’t have an integration with risks management. Proper schedule and risk integration is common challenge for may projects now.

• Apart from Crashing, there are other methods to accelerate project delivery but original CPM didn’t support them. Fast-tracking is the most know alternative.

The Critical Path method wasn’t the only invention in project management in late 50th. An  alternative know as ‘PERT analyses’ is based 3 point estimations was developed by the US Navy Special Projects Office, Bureau of Ordnance (SPO). In fact,  Kelly and Walker used the name ‘main chain’, and the term ‘Critical Path’ was invented and promoted by the team developed the PERT (Program Evaluation and Review Technique).  By the late 1960s both CPM and PERT had merged into ‘Network based management systems’. It is a separate intersting story.