Once a set of precedence relations for a project is given, the essential scheduling problem becomes the creation of a Priority List. There are many possible strategies that lead to the creation of a Priority List. Here we will consider only two of these strategies: the Decreasing-Time Algorithm and the Critical-Path Algorithm.
The Decreasing-Time Algorithm (DTA) is based on a
seemingly simple strategy:
Simply put, the DTA creates a Priority List by listing the tasks in
decreasing order of processing times (longest task first, shortest task last). Tasks
with equal processing times can be listed in any order.
For example, given the project diagraph below,
the Priority List using the Decreasing-Time Algorithm (the so-called decreasing-time list) is X A F Q R (or X A Q F R).
Once again, keep in mind that precedence relations always override the Priority List when there is a conflict between the two. So, for instance, here task X cannot actually be assigned first even though it is first on the Priority List since precedence relations demand that task Q precede task X.
A Problem with the Decreasing-Time Algorithm
Although the strategy of scheduling the longer tasks first sounds good, it does have a major flaw. The DTA ignores any information in the project digraph that might indicate that one or more tasks should be done early rather than late. For instance, if one or more tasks with long processing times can't begin until task X (with a very short processing time) is finished, then assigning task X early will probably result in a shorter finishing time even though assigning task X early violates the DTA.
For example, suppose a project consists of five tasks:
Y(6), Q(4), R(3), D(2), X(1) and the only precedence relation is .
But looks what happens if we temporarily ignore the DTA and go ahead and assign
task X to P1 in the beginning.
As you can see, we were able to improve the project finishing time by violating the Decreasing-Time Algorithm.
Once the concept of critical time is understood, we can explain the Critical-Path Algorithm.
The Critical-Path Algorithm (CPA) is based on a strategy
similar to that of the Decreasing-Time Algorithm:
Simply put, the CPA creates a Priority List by listing the tasks in
decreasing order of critical times. Tasks with equal critcal times can be listed in
To illustrate, let's go back to the example used earlier to explain the Backflow Algorithm.
The first step in applying the CPA to a project digraph is to use the Backflow Algorithm to replace all processing times with critical times. The result is shown below. Click here if you need to go back and see how the critical times were obtained.
Now create the Priority List by listing the tasks in decreasing order
of critical times.
Once again, keep in mind that precedence relations always override the Priority List when there is a conflict between the two.
Although the Critical-Path Algorithm is generally better than the Decreasing-Time Algorithm, neither is guaranteed to produce an optimal schedule. In fact, no efficient scheduling algorithm is presently known that always gives an optimal schedule. However, the Critical-Path Algorithm is the best general-purpose scheduling algorithm currently known.