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:
Do the longer jobs first and save the shorter jobs for last.
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.
A Priority List created by the DTA is often called a decreasing-time
list.
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 
.
Using the Decreasing-Time Algorithm, the Priority List is Y Q R D X.
Now suppose there are two processors P1 and P2 . Task Y is the
longest task but cannot be assigned yet since .
So, let's assign the next longest task, Q, to processor P1 and the next longest
task, R to P2.
At hour 3, processor 2 completes task R and is ready again and is assigned task D.
At hour 4, processor 1 completes task Q and is ready again and is assigned task X.
At hour 5, both processors are ready again and task Y can be assigned to processor 1.
At hour 11, task Y is completed for a total project time of 11 hours.
(See the diagram below.)
But looks what happens if we temporarily ignore the DTA and go ahead and assign
task X to P1 in the beginning.
We still can't assign task Y (since task X is not done) but we can assign task Q to P2.
At hour 1, processor 1 completes task X and is ready again and can now be assigned task Y.
At hour 4, processor 2 completes task Q and is ready again and is assigned task R.
At hour 7, processors 1 and 2 both complete their tasks and are ready again and P1 is assigned task D.
At hour 9, processor 1 completes task D for a total project time of 9 hours.
(See the diagram below.)
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:
Do the jobs with the largest critical times first and save the jobs with shorter
critical times for last.
(The DTA does the jobs with the largest processing times first.)
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
any order.
A Priority List created by the CPA is often called a critical-path
list.
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.
The Priority List is: Q X A F.
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.