Scheduling
AlgorithmsOnce 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
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.
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
any order. 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.
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. |