PROJECT SCHEDULING: PERT/CPM

  • A project is made up of a series of tasks called – activities
  • Some activities must be completed before other activities can be started
  • Some activities (say B) that must be started immediately before another activity (say D) – that is, no other activities must be done after B and before D
  • Activity B is an immediate predecessor for Activity D
  • Activity D is an immediate successor to Activity B
  • A network can be drawn that has nodes representing the activities (with their estimated completion times) and arcs showing the precedence relations.

EXAMPLE: Klone Computers will design and manufacture a new computer, train staff and sales vendors, and advertise the product. The activities and their expected completion times are below.

ActivityTimeImmediate Predecessors

A Prototype Design 90

B Purchase Materials 15

C Manufacture Prototypes 5

D Revise Design 20

E Initial Production Run 21

F Staff Training 25

G Staff Input on Design 14

H Sales Vendor Training 28

I Preproduction Advertising 30

J Post Redesign Advertising 45

To fill in the immediate predecessor column, the following describes the project:

  • The project begins with the prototype design (A)
  • Materials are purchased (B) after the prototype has been designed (A)
  • Prototypes are manufactured (C) after the materials have been purchased (B)
  • The design is revised (D) after getting staff input (G)
  • An initial production run is started (E) after the design has been revised (D)
  • Once the prototype has been designed (A), staff can be trained (F)
  • Staff Input on the prototype (G) occurs after BOTH the manufacture of the prototype (C) and the staff training (F)
  • Sales vendor training (H) begins once the design has been revised (D)
  • A preproduction advertising campaign (I) can start after the prototype is designed (A)
  • The full-blown post-redesign advertising campaign (J) begins once the design has been revised (D AND the preproduction advertising campaign is completed (I)

Draw the network for the project:

  • The goal of many project scheduling models is to complete the project in minimum time
  • PERT/CPM (Program Evaluation and Review Technique/Critical Path Method) is a solution approach for solving for this minimum time
  • It determines a set of earliest start (ES) and earliest finish (EF) times by making a forward pass through the network
  • For activities with no predecessors: ES = 0
  • For all other activities: ES = max (EF of immediate predecessors)
  • For all activities: EF = ES + time to do the activity
  • The expected project completion time E(T) = max EF
  • It determines a set of latest finish (LF) and latest start (LS) times by making a backwards pass through the network
  • For activities with no successors: LF = E(T)
  • For all other activities: LF = min (LS of immediate succesors)
  • For all activities: LS = LF – time to do the activity
  • Slack time for an activity = LS – ES or LF – EF
  • If an activity is delayed by more than its slack time, the project is delayed by the difference between the delay and the slack
  • Activities with slack = 0 cannot be delayed without delaying the project and are called critical activities
  • The set of critical activities forms a critical path through the network
  • A delay in any activity on the critical path delays the project
  • The sum of the completion times on the critical path is the expected project completion time = E(T)
  • A linear program can be solved to determine the completion time for the project:

MIN Time to finish Project

s.t. Activities cannot start before their immediate predecessors are completed

All times ≥ 0

You should know how to use the PERT/CPM template for projects

whose activity completion times are known with certainty.

The PERT/CPM Three-Time Estimate Approach

  • Activity completion times are rarely (if ever) known with certainty, so a probability approach is more realistic in evaluating a project’s expected completion time. A three-time estimate approach allows for such probability analyses
  • Three time estimates are determined (by studies, guesses, etc.) for each activity
  • a = an optimistic completion time (the chance of finishing in < a is very small)
  • m = a most likely completion time (this is the mode)
  • b = a pessimistic completion time (the chance of finishing in > b is very small)
  • Activity approximations
  • An approximation for the distribution of an activity’s completion time is a BETA distribution
  • An approximation for the mean completion time for an activity is a weighted average (1/6, 4/6, 1/6) of the three completion times; so it is
  • An approximation for the standard deviation for the completion time for an activity is its Range/6 or
  • The varianceof an activity’s completion time is the square of the standard deviation =
  • Project assumptions
  1. The distribution of the project completion time is determined by the critical path using the mean activity completion times
  2. The activity completion times are independent – just because one activity takes longer or shorter than expected does not affect another activity’s time.
  3. There are enough activities on the critical path so that the central limit can be used to determine the distribution, mean, variance and standard deviation of the project
  • Project distribution

Given the above assumption this means

  • The project completion time distribution is normal
  • The mean (expected) completion time, µ, of the project is the sum of the expected completion times along the critical path
  • The variance of the completion time, σ2, of the project is the sum of the variance in completion times along the critical path
  • The standard deviation of the completion time, σ, of the project is the square root of the variance of the completion time of the project

The probability of completing by a certain date t, can now be found by finding the P(X < t) from a normal distribution with mean µ and standard deviation σ

You should know how to use the PERT/CPM template for projects

whose activity completion times are given by three time estimates.

Comparing Options Using Probability Approach to Project Scheduling The Expected Value Approach

Example 1

Suppose there is a bonus of $8000 for completing a project within 50 days.

You have two options:

A – Do what you are currently doing and from the template, you find

P(Finish < 50) = .27 and thus P(Finish > 50) = 1 - .27 = .73

The Expected Bonus = (.27)($8000) + .73(0) = $2160

B – For $2000 you can alter the activity completion times. From the template you find the revised P(Finish < 50) = .64 and thus P(Finish > 50) = 1 - .64 = .36

The Expected Bonus = .64($8000) + .36(0) = $5120

But it cost $2000 to do this, so

Net Expected Bonus = $5120 - $2000 = $3120

$3120 > $2160, so you should recommend Option B

Example 2

Suppose there is a cost of $30,000 for not completing a project within 75 days.

You have two options:

A – Do what you are currently doing and from the template, you find,

P(Finish < 75) = .42 and thus P(Finish > 75) = 1 - .42 = .58

The Expected Cost = (.42)(0) + .58($30,000) = $17,400

B – For $5000 you can alter the activity completion times. From the template you find the revised P(Finish < 75) = .55 and thus P(Finish > 75) = 1 - .55 = .45

The Expected Cost = (.55)(0) + .45($30,000) = $13,500

Butit cost $5000 to do this, so

Net Expected Cost = $13,500 + $5000 = $18,500

$17,400 < $18,500, so you should recommend Option A