The thing that seems to cause a problem with the Decreasing-Time Algorithm is that it does not consider the amount of work "lying ahead of a task."  To attempt to come up with an algorithm that incorporates this idea. let's define something called a critical path for a vertex (task).

Critical Path for X
For a vertex, X, of a project digraph, the critical path for X is the path from X to the END that has the longest total sum of processing times.

For instance, in the project digraph below, the critical path for vertex X is X A End.
This is true since of the 2 possible paths from X to End
(1. X F End - 6 hours
2. X A End - 7 hours)
X A End has the longest sum of processing times (7 hours).  

Critical Time for X
The actual total processing time in the critical path for vertex X is called the critical time for X.
For the example above, the critical time for X is 7 hours.

Critical Path (for the Project)
The critical path for the project, or just critical path for short, is the critical path for the START vertex of the project.
For example, the critical path for the project above is Start Q X F End.
This is true since of the 3 possible paths from Start to End
(1. Start Q A End - 5 hours
2. Start Q X F End - 8 hours
3. Start Q X A End - 9 hours
Start Q X A End has the longest sum of processing times (9 hours).  

Critical Time (for the Project)
The critical time for the project, or just critical time for short, is the critical time for the START vertex of the project.
For example, the critical time for the project above is 9 hours.
A project can never be finished in less than the critical time for the project.

The Backflow Algorithm

Finding critical paths and times will be of fundamental importance to us here.   But, for all but the simplest projects, it is difficult to find them just by "looking" at the project digraph.  Fortunately, there is a simple procedure called the Backflow Algorithm which allows us to find the critical path and time for each vertex of a project digraph.

Note: We will indicate critical times for the vertices of a project digraph using square brackets to distinguish them from processing times (for which we use parentheses).

1. Begin at the END vertex of the project digraph and assign it a critical time of zero.
2. Move backwards to each vertex that is incident to (having an arrow pointing to) END and assign it a critical time.
   Note: For vertices incident to (having an arrow pointing to) END, the critical time is the same as the processing time.
3. For each of the vertices in Step 2, move backwards again to each vertex that is incident to (precedes) it and assign it a critical time.
   Note: For each of these vertices, the critical time is its processing time added to the LARGEST critical time of the vertices incident from (having an arrow pointing away from) that vertex.
4. Continue this process until each vertex of the project digraph has a critical time.
   Note: The critical time for each vertex is its processing time added to the LARGEST critical time of the vertices incident from (having an arrow pointing away from) that vertex.

Example:  Let's calculate the critical times for each of the vertices in this project diagraph using the Backflow Algorithm.

STEPS:

1.  Begin at the END vertex and assign it a critical time of 0.  Remember that we will use square brackets [ ] for critical times.

2.  Move backwards to each vertex that is incident to (having an arrow pointing to) END and assign it a critical time.
     Here vertices A and F are incident to END.  Remember that the critical time for these vertices is the same as the processing time.

3.  For each of the vertices in Step 2, move backwards again to each vertex that is incident to (precedes) it and assign it a critical time.
     For each of these vertices, the critical time is its processing time added to the LARGEST critical time of the vertices incident from (having an arrow pointing away from) that vertex.

Vertex A has two vertices incident to it (X and Q).
X is incident from A (with critical time 3) and F (with critical time 2).  Choose the largest of these critical times, 3, and add it to the processing time of vertex X itself, 4, to get a critical time of 7 for vertex X.
Q is incident from A (with critical time 3) and X (with critical time 7).  Choose the largest of these critical times, 7, and add it to the processing time of vertex Q itself, 2, to get a critcal time of 9 for vertex Q.

4.  The only vertex incident from X is Q which has already been done.  The only vertex incident from Q is START.
Since START is incident to only Q, the critical time for START is the critical time for Q, 9, plus the processing time of START, 0, or 9.

The digraph above is, then, the result of applying the Backflow Algorithm.

Back