- Forward


Program Evaluation and Review Technique (PERT)
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Background
Back Forward
  • The Question:
    • How long will it take to complete a specific (design or implementation) project (or part of a project)?
  • A Review of the Issues:
    • Units Matter
    • Task Details Matter
    • Task Dependencies Matter
    • Personnel Capabilities Matter
  • PERT:
    • Developed in the 1950s
An Example
Back Forward

The Input Data

images/pert-example_times-and-dependencies.gif
Learning From An Example
Back Forward
  • Apparently:
    • 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
Back Forward
  • 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.)
Back Forward

The Dependency Graph

images/pert-example_dependencies.gif images/pert-example_dependency-graph.gif
Using the Dependency Graph
Back Forward
  • 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
Back Forward
  • 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.)
Back Forward
  • 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.)
Back Forward

The Dependency Graph with Task Times

images/pert-example_times.gif images/pert-example_graph-with-times.gif
Using the Graph with Task Times
Back Forward
  • 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.)
Back Forward
  • 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
Back Forward
images/pert_longest-path-algorithm.gif
An Example (cont.)
Back Forward
  1. Node 1:
    • \(L_1 = 6\)
  2. Node 2:
    • \(L_2 = L_1 + 5 = 6 + 5 = 11\)
  3. Node 3:
    • \(L_3 = L_1 + 2 = 6 + 2 = 8\)
  4. Node 4:
    • \(L_4 = L_1 + 6 = 6 + 6 = 12\)
  5. 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\)
  6. ...
An Example (cont.)
Back Forward

The Labeled Graph

images/pert-example_labeled-graph.gif
Interpreting the Labeled Graph
Back Forward
  • 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.)
Back Forward
  • 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
Back Forward
  • Thus Far:
    • We have assumed that the task times (i.e., the required times for the tasks) are known and deterministic
  • In Reality:
    • They are estimates
    • They should be treated as probabilistic (i.e., random variables)
Introducing Stochasticity (cont.)
Back Forward
  • A Common Approach - Three Estimates:
    • \(t_o\) denotes the optimistic time required
    • \(t_m\) denotes the most likely time required
    • \(t_p\) denotes the pessimistic time required
  • Assumptions:
    • \(\sigma = \left[ \frac{1}{6} (t_p - t_o) \right]\) (i.e., there are 6 standard deviations between tails)
    • The task times are \(\beta\)-distributed with mode, \(t_m\), lower bound, \(t_o\), and upper bound, \(t_p\)
Introducing Stochasticity (cont.)
Back Forward
  • Expected Task Times:
    • Are approximately \(E[t] = \frac{1}{3}\left[ 2 t_m + \frac{1}{2} (t_o + t_p) \right]\)
  • Some Additional Assumptions:
    • Activity times are identically and independently distributed
    • The critical path is longer than any other path
  • The Implications:
    • The mean and standard deviation of the project time are the sums of the means and standard deviations of the task times on the critical path
    • The project time (which is the sum of the task times) is normally distributed (by the central limit theorem)
  • Inferential Statistics:
    • We can test hypotheses about the project completion times
There's Always More to Learn
Back -