Scheduling Algorithms

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.

 

Decreasing-Time 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,

wpe19.jpg (9178 bytes)

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 wpe9.jpg (904 bytes).
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 wpe9.jpg (904 bytes).
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.)

wpe1D.jpg (7825 bytes)

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.)
wpe1E.jpg (7577 bytes)

As you can see, we were able to improve the project finishing time by violating the Decreasing-Time Algorithm.

 

Critical-Path Algorithm

PRELIMINARIES

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.

wpe25.jpg (11809 bytes)

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.

wpe29.jpg (12162 bytes)

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.

Back