It's possible to put all of the necessary information
in a table
Unfortunately:
The table can be confusing
Allaying the Confusion:
Use some discrete math (i.e., a graph)
Task Dependency Graphs
Vertices/Nodes and Edges/Arcs:
Vertices represent milestones (i.e., events that
can be used to mark the progress of the project)
Edges represent dependencies (i.e., if \(i\) must be
completed before \(j\) then include an edge
from \(i\) to \(j\) with a weight equal
to the duration of the task
A Small Improvement:
Include a "dummy vertex" that represents the start of the
project
An Example (cont.)
The Dependency Graph
Using the Dependency Graph
The dependencies:
Are easy to see
Tasks that can be worked on at the same time:
Can still be difficult to see so you may have to
move nodes around to make it clearer
Improving the Dependency Graph
We Have More Information:
The time required to complete each task
Where Should it Go?
In some cases the answer is obvious
In others we have to be more careful
Improving the Dependency Graph (cont.)
The General Idea:
The time required to complete a task goes on the
inbound edge
The Complication:
Some nodes have more than one inbound edge (i.e., multiple tasks
must be completed before they can be worked on)
The Resolution:
Put the time required to complete the task on all inbound edges
An Example (cont.)
The Dependency Graph with Task Times
Using the Graph with Task Times
Recall:
We want to know how long it will take to complete the
project
An "Obvious" Way to Proceed:
Find the shortest path from the dummy vertex to the final
vertex
Oops:
The shortest path is actually the "easiest" sequence
of tasks (i.e., the sequence of tasks with the most slack)
Using the Graph with Task Times (cont.)
Recall:
We want to know how long it will take to complete the
project
The Correct Way to Proceed:
Find the longest path from the dummy vertex to the final
vertex
The Rationale:
You want to find the path that has the least (i.e., zero)
slack
You want to find the critical path
A Labeling Algorithm
An Example (cont.)
Node 1:
\(L_1 = 6\)
Node 2:
\(L_2 = L_1 + 5 = 6 + 5 = 11\)
Node 3:
\(L_3 = L_1 + 2 = 6 + 2 = 8\)
Node 4:
\(L_4 = L_1 + 6 = 6 + 6 = 12\)
Node 5:
From 2: \(L_2 + 4 = 11 + 4 = 15\)
From 3: \(L_3 + 4 = 8 + 4 = 12\)
Choose the larger, so \(L_5 = 15\)
...
An Example (cont.)
The Labeled Graph
Interpreting the Labeled Graph
Above Each Vertex:
The time to that vertex
The predecessor task on the critical path
Finding the Critical Path:
Work backwards from the last task using the predecessors
(e.g., 14 from 12 from 10 from 5 from 2 from 1 from 0)
Finding Slack Times:
The labels on vertices that are not on the critical path provide
information about how much that task can slip
An Example (cont.)
Consider Vertex 12:
It is on the critical path (so it can't slip)
It isn't completed until month 23
Consider Vertex 9:
It is NOT on the critical path, so it can slip
It isn't completed until month 14
The next task (i.e., 12) isn't completed until month 23
The next task (i.e., 12) requires 4 months
Task 9 can slip by 23-14-4=5 months without effecting
the completion date
Introducing Stochasticity
Thus Far:
We have assumed that the task times (i.e., the required
times for the tasks) are known and deterministic