Program Evaluation and Review Technique (PERT)

Program Evaluation and Review Technique (PERT)
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Background

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

The Input Data

Learning From An Example

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
In Reality:
- They are estimates
- They should be treated as probabilistic (i.e., random variables)

Introducing Stochasticity (cont.)

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.)

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