Management Science Chapter 9

Anderson Sweeney Williams Camm Cochran Fry Ohlmann
An Introduction to
Management Science, 15e
Quantitative Approaches to Decision Making
© 2019 Cengage. All rights reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website or school-approved learning management system for classroom use.
Chapter 9: Project Scheduling: PERT/CPM
9.1 - Project Scheduling Based on Expected Activity Times

9.2 - Project Scheduling Considering Uncertain Activity Times
9.3 - Considering Time-Cost Trade-Offs
2
PERT/CPM (1 of 3)
PERT - Program Evaluation and Review Technique

• Developed by U.S. Navy for Polaris missile project
• Developed to handle uncertain activity times
CPM - Critical Path Method

• Developed by DuPont & Remington Rand
• Developed for industrial projects for which activity times
generally were known
Today’s project management software packages have

combined the best features of both approaches.
3
PERT/CPM (2 of 3)
PERT and CPM have been used to plan, schedule, and control
a wide variety of projects:
• R&D of new products and processes
• Construction of buildings and highways
• Maintenance of large and complex equipment
• Design and installation of new systems
• PERT/CPM is used to plan the scheduling of individual
activities that make up a project.
• Projects may have as many as several thousand activities.
• A complicating factor in carrying out the activities is that some
activities depend on the completion of other activities before
they can be started.
4
PERT/CPM (3 of 3)
Project managers rely on PERT/CPM to help them answer

questions such as:
• What is the total time to complete the project?
• What are the scheduled start and finish dates for each
specific activity?
• Which activities are critical and must be completed exactly
as scheduled to keep the project on schedule?
• How long can noncritical activities be delayed before they
cause an increase in the project completion time?
5
Project Scheduling Based on Expected Activity Times
(1 of 21)
• A project network can be constructed to model the

precedence of the activities.
• The nodes of the network represent the activities.
• The arcs of the network reflect the precedence relationships
of the activities.
• A critical path for the network is a path consisting of activities
with zero slack.
6
(2 of 21)
The owner of the Western Hills Shopping Center plans to

modernize and expand the current 32-business shopping center
complex. The project is expected to provide room for 8 to 10
new businesses. Financing has been arranged through a
private investor. All that remains is for the owner of the
shopping center to plan, schedule, and complete the expansion
project.
Let us show how PERT/CPM can help.
7
(3 of 21)
The first step in the PERT/CPM scheduling process is to develop

a list of the activities that make up the project.
Immediate
Activity Activity Description Expected Activity Time
Predecessor
A Prepare architectural drawings ___ 5
B Identify potential new tenants ___ 6
C Develop prospectus for tenants A 4
D Select contractor A 3
E Prepare building permits A 1
Obtain approval for building
F E 4
permits
G Perform construction D, F 14
H Finalize contracts with tenants B, C 12
I Tenants move in G, H 2
Total 51
The immediate predecessor column identifies the activities that

must be completed immediately prior to the start of that activity.
8
(4 of 21)
Using the activity information, we can construct a graphical

representation of the project, or the project network.
9
Project Scheduling Based on Expected Activity Times (5
of 21)
A path is a sequence of connected nodes that leads from the

Start node to the Finish node. For instance, one path for the
network is defined by the sequence of nodes A-E-F-G-I.
10
of 21)
To facilitate the PERT/CPM computations, we modified the

project network. The upper left-hand corner of each node
contains the corresponding activity letter. The activity time
appears immediately below the letter.
11
(7 of 21)
All paths in the network must be traversed in order to complete

the project, so we will look for the path that requires the greatest
time. Because all other paths are shorter in duration, this longest
path determines the total time required to complete the project. If
activities on the longest path are delayed, the entire project will
be delayed. Thus, the longest path is the critical path. Activities
on the critical path are referred to as the critical activities for
the project.
12
(8 of 21)
We begin by finding the earliest start time and the latest start
time for all activities in the network. Let
ES = earliest start time for an activity
EF = earliest finish time for an activity
t = expected activity time
The earliest finish time for any activity is
EF = ES + t
13
(9 of 21)
Activity A can start as soon as the project starts, so we set the

earliest start time for activity A equal to 0. With an expected
activity time of 5 weeks, the earliest finish time for activity A
is EF = ES + t = 0 + 5 = 5.
We will write the earliest start and earliest finish times in the node
to the right of the activity letter. Using activity A as an example,
we have
14
(10 of 21)
Because an activity cannot be started until all immediately

preceding activities have been finished, the following rule can be
used to determine the earliest start time for each activity:
The earliest start time for an activity is equal to the largest (i.e.,
latest) of the earliest finish times for all its immediate
predecessors.
15
of 21)
Let us apply the earliest start time rule to the portion of the network
involving nodes A, B, and C. With an earliest start time of 0 and an
activity time of 6 for activity B, we show ES = 0 and EF = 6 in the node
for activity B. Activity A
is the only immediate
Predecessor for activity
C. EF for activity A is 5,
so ES for activity C
must be 5. Thus, with
An activity time of 4,
the earliest finish time
for activity C is EF = 9.
16
(12 of 21)
With activities B and C as immediate predecessors, the earliest

start time for activity H must be equal to the largest of the earliest
finish times for activities B and C. Thus, with EF = 6 for activity B
and EF = 9 for activity C, 9 is the earliest start time for activity H
(ES = 9). With an activity time of 12 as shown in the node for
activity H, the earliest finish time is EF = 21.
17
(13 of 21)
Continuing with this forward pass through the network, we can

establish the earliest start time and the earliest finish time for each
activity in the network. Therefore, we now know that the expected
completion time for the entire project is 26 weeks.
18
(14 of 21)
We now continue finding the critical path by making a backward

pass through the network. Because the expected completion
time for the entire project is 26 weeks, we begin the backward
pass with a latest finish time of 26 for activity I.
Once the latest finish time for an activity is known, the latest start
time for an activity can be computed as follows. Let
LS = latest start time for an activity
LF = latest finish time for an activity
Then
LS = LF – t
19
(15 of 21)
Beginning the backward pass with activity I, we know that the

latest finish time is LF = 26 and that the activity time is t = 2.
Thus, the latest start time for activity I is LS = 24. We will write
the LS and LF values in the node directly below the earliest start
(ES) and earliest finish (EF) times. Thus, for node I, we have
20
(16 of 21)
The following rule can be used to determine the latest finish time
for each activity in the network:
The latest finish time for an activity is the smallest (earliest) of the
latest start times for all activities that immediately follow the
activity.
21
(17 of 21)
After we complete the forward and backward passes, we can

determine the amount of slack associated with each activity.
Slack is the length of time an activity can be delayed without

increasing the project completion time.
The amount of slack for an activity is computed as follows:
Slack = LS – ES = LF – EF
22
(18 of 21)
The slack associated with activity C is LS – ES = 8 – 5 = 3 weeks.

Hence, activity C can be delayed up to 3 weeks, and the entire
project can still be completed in 26 weeks. In this sense, activity C
is not critical to the completion of the entire project in 26 weeks.
23
(19 of 21)
Putting this information in tabular form provides the activity

schedule shown
Earliest Latest Earliest Latest
Slack Critical
Activity Start Start Finish Finish
(LS–ES) Path?
(ES) (LS) (FS) (LF)
A 0 0 5 5 0 Yes
B 0 6 6 12 6
C 5 8 9 12 3
D 5 7 8 10 2
E 5 5 6 6 0 Yes
F 6 6 10 10 0 Yes
G 10 10 24 24 0 Yes
H 9 12 21 24 3
I 24 24 26 26 0 Yes
24
(20 of 21)
We previously stated that project managers look for procedures

that will help answer important questions regarding the planning,
scheduling, and controlling of projects. Here are the answers:
1. How long will the project take to complete?

Answer: The project can be completed in 26 weeks if each
activity is completed on schedule.
2. What are the scheduled start and completion times for each
activity?
Answer: The activity schedule shows the earliest start, latest
start, earliest finish, and latest finish times for each activity.
25
(21 of 21)
3. Which activities are critical and must be completed exactly as

scheduled to keep the project on schedule?
Answer: A, E, F, G, and I are the critical activities.
4. How long can noncritical activities be delayed before they

cause an increase in the completion time for the project?
Answer: The activity schedule shows the slack associated
with each activity.
26
Summary of the PERT/CPM Critical Path Procedure
Step 1. Develop a list of the activities that make up the project.
Step 2. Determine the immediate predecessor(s) for each

activity in the project.
Step 3. Estimate the completion time for each activity.
Step 4. Draw a project network depicting the activities and

immediate predecessors listed in steps 1 and 2.
27
Critical Path Procedure (1 of 2)
Step 5. Use the project network and the activity time estimates
to determine the earliest start and the earliest finish time for
each activity by making a forward pass through the network. The
earliest finish time for the last activity in the project identifies the
total time required to complete the project.
Step 6. Use the project completion time identified in Step 5 as

the latest finish time for the last activity and make a backward
pass through the network to identify the latest start and latest
finish time for each activity.
28
Critical Path Procedure (2 of 2)
Step 7. Use the difference between the latest start time and the
earliest start time for each activity to determine the slack for
each activity.
Step 8. Find the activities with zero slack; these are the critical
activities.
Step 9. Use the information from steps 5 and 6 to develop the

activity schedule for the project.
29
Project Scheduling Considering Uncertain Activity Times
In the three-time estimate approach, the time to complete an

activity is assumed to follow a Beta distribution.
An activity’s mean completion time is:

t = (a + 4m + b) / 6
a = the optimistic completion time estimate

b = the pessimistic completion time estimate
m = the most likely completion time estimate
30
Uncertain Activity Times (1 of 2)
An activity’s completion time variance is:
    b  a  / 6
2 2
a = the optimistic completion time estimate

b = the pessimistic completion time estimate
31
Uncertain Activity Times (2 of 2)
In the three-time estimate approach, the critical path is

determined as if the mean times for the activities were fixed
times.
The overall project completion time is assumed to have a

normal distribution with mean equal to the sum of the means
along the critical path and variance equal to the sum of the
variances along the critical path.
32
Crashing Activity Times (1 of 2)
To determine just where and how much to crash activity times,

we need information on how much each activity can be crashed
and how much the crashing process costs. Hence, we must ask
for the following information:
• Activity cost under the normal or expected activity time
• Time to complete the activity under maximum crashing
(i.e., the shortest possible activity time)
• Activity cost under maximum crashing
33
• When determining the time estimates for activities in a project,

the project manager bases these estimates on the amount of
resources (workers, equipment, etc.) that will be assigned to an
activity.
• The original developers of CPM provided the project manager
with the option of adding resources to selected activities to
reduce project completion time.
• Added resources (such as more workers, overtime, and so on)
generally increase project costs, so the decision to reduce
activity times must take into consideration the additional cost
involved.
• In effect, the project manager must make a decision that involves
trading additional project costs for reduced activity time.
34
Considering Time-Cost Trade-offs (1 of 3)
The table shown defines a two-machine maintenance

project consisting of five activities. Management has
substantial experience with similar projects and the times
for maintenanceactivities have very little variability; hence,
a single time estimate is given for each activity.
Immediate
Activity Description Expected Time (days)
Predecessor
A Overhaul machine I ___ 7
B Adjust machine I A 3
C Overhaul machine II ___ 6
D Adjust machine II C 3
E Test system B, D 2
35
The project network is shown here:
36
The length of the critical path, and thus the total time required
to complete the project, is 12 days.
Earliest Latest Earliest Latest

Slack Critical
Activity Start Start Finish Finish
(LS–ES) Path?
(ES) (LS) (FS) (LF)
A 0 0 7 7 0 Yes
B 7 7 10 10 0 Yes
C 0 1 6 7 1
D 6 7 9 10 1
E 10 10 12 12 0 Yes
37
In the Critical Path Method (CPM) approach to project

scheduling, it is assumed that the normal time to complete an
activity,  i which can be met at a normal cost, ci
can be crashed to a reduced time,  i ,
'
'
under maximum crashing for an increased cost, ci .
'
Using CPM, activity i s maximum time reduction,
may be calculated by: M i   i   i .
'
It is assumed that its cost per unit reduction, K i ,

is linear and can be calculated by: K i  Ci  Ci
'
  /M . i
38
For example, if the normal or expected time for activity A is 7

days at a cost of CA = $500 and the time under maximum
crashing is 4 days at a cost of CA = $800, the previous
equations show that the maximum possible reduction in time
for activity A is MA = 7 – 4 = 3 days with a crashing cost of
C A'  C A 800  500 300

KA     $100 per day
MA 3 3
39
Crashing Activity Times (3 of #)
We make the assumption that any portion or fraction of the

activity crash time can be achieved for a corresponding
portion of the activity crashing cost. For example, if we
decided to crash activity A by only 1.5 days, the added cost
would be 1.5 ($100) = $150, which results in a total activity
cost of $500 + $150 = $650.
40
The complete normal and crash activity data for the two-
machine maintenance project are given here:
Max in
Time Time Total Cost Total Cost Crash Cost
Reduction
Normal Crash Normal Crash per Day
in Time
7 4 $ 500 3 $100
$ 800
3 2 200 350 1 150
6 4 500 900 2 200
3 1 200 500 2 150

2 1 300 550 1 250
$1700 $3100
41
Which activities should be crashed—and by how much—to

meet the 10-day project completion deadline at minimum
cost?
Your first reaction to this question may be to consider

crashing the critical activities—A, B, or E. Activity A has the
lowest crashing cost per day of the three, and crashing this
activity by 2 days will reduce the A-B-E path to the desired 10
days.
42
Keep in mind, however, that as you crash the current critical

activities, other paths may become critical.
Thus, you will need to check the critical path in the revised
network and perhaps either identify additional activities to
crash or modify your initial crashing decision.
For a small network, this trial-and-error approach can be used

to make crashing decisions; in larger networks, however, a
mathematical procedure is required to determine the optimal
crashing decisions.
43
End of Presentation: Chapter 9
44

Management Science Chapter 9

Uploaded by

Copyright:

Available Formats

Management Science Chapter 9

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Management Science Chapter 9

Uploaded by

Copyright:

Available Formats

Anderson Sweeney Williams Camm Cochran Fry Ohlmann

9.1 - Project Scheduling Based on Expected Activity Times

9.3 - Considering Time-Cost Trade-Offs

PERT - Program Evaluation and Review Technique

CPM - Critical Path Method

Today’s project management software packages have

Project managers rely on PERT/CPM to help them answer

• A project network can be constructed to model the

The owner of the Western Hills Shopping Center plans to

Let us show how PERT/CPM can help.

The first step in the PERT/CPM scheduling process is to develop

The immediate predecessor column identifies the activities that

Using the activity information, we can construct a graphical

A path is a sequence of connected nodes that leads from the

To facilitate the PERT/CPM computations, we modified the

All paths in the network must be traversed in order to complete

The earliest finish time for any activity is

Activity A can start as soon as the project starts, so we set the

Because an activity cannot be started until all immediately

With activities B and C as immediate predecessors, the earliest

Continuing with this forward pass through the network, we can

We now continue finding the critical path by making a backward

Beginning the backward pass with activity I, we know that the

After we complete the forward and backward passes, we can

Slack is the length of time an activity can be delayed without

The amount of slack for an activity is computed as follows:

The slack associated with activity C is LS – ES = 8 – 5 = 3 weeks.

Putting this information in tabular form provides the activity

We previously stated that project managers look for procedures

1. How long will the project take to complete?

3. Which activities are critical and must be completed exactly as

4. How long can noncritical activities be delayed before they

Step 1. Develop a list of the activities that make up the project.

Step 2. Determine the immediate predecessor(s) for each

Step 3. Estimate the completion time for each activity.

Step 4. Draw a project network depicting the activities and

Step 6. Use the project completion time identified in Step 5 as

Step 9. Use the information from steps 5 and 6 to develop the

In the three-time estimate approach, the time to complete an

An activity’s mean completion time is:

a = the optimistic completion time estimate

An activity’s completion time variance is:

a = the optimistic completion time estimate

In the three-time estimate approach, the critical path is

The overall project completion time is assumed to have a

To determine just where and how much to crash activity times,

• When determining the time estimates for activities in a project,

The table shown defines a two-machine maintenance

The project network is shown here:

Earliest Latest Earliest Latest

In the Critical Path Method (CPM) approach to project

It is assumed that its cost per unit reduction, K i ,

For example, if the normal or expected time for activity A is 7

C A'  C A 800  500 300

We make the assumption that any portion or fraction of the

3 2 200 350 1 150

6 4 500 900 2 200

3 1 200 500 2 150

Which activities should be crashed—and by how much—to

Your first reaction to this question may be to consider