CHAPTER 13

Project
Scheduling:
PERT/CPM

KEY CONCEPTS
 2 CHAPTER 13

ILLUSTRATED ANSWERED
CONCEPT PROBLEMS PROBLEMS

Construction of PERT Networks 1,2 6,8,12,13

PERT Analysis with Certain Times 1 6,7,9

PERT Analysis with Uncertain Times 2,4 8,10,11

Activity Earliest/Latest Times 1,2,5 7,9,14

Time/Cost Analysis 3,4 9-13

LP Formulation for Crashing 3 12,13

REVIEW

1. PERT (Program Evaluation Review Technique) is used to plan the scheduling of individual
activities that make up a project.
2. A PERT network can be constructed to model the precedence of the activities. The nodes
of the network represent the activities.
3. PERT can be used to determine the earliest/latest start and finish times for each activity,
the entire project completion time and the slack time for each activity. (See algorithm at
the end of the Review.)
4. A critical path for the network is a path consisting of activities with zero slack.
5. In the three-time estimate approach, the time to complete an activity is assumed to follow
a Beta distribution. Its mean is t = (a + 4m + b)/6, and its variance is s2 = ((b-a)/6)2.
Here a = the optimistic completion time estimate, b = the pessimistic completion time
estimate, and m = the most likely completion time estimate.
6. 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.
7. In the CPM (Critical Path Method) approach to project scheduling, it is assumed that the
normal time to complete an activity, tj, which can be met at a normal cost, cj, can be
crashed to a reduced time, tj', under maximum crashing for an increased cost, cj'.

8. Using CPM, activity j's maximum time reduction, Mj, may be calculated by: Mj = tj - tj'. It
is assumed that its cost per unit reduction, Kj, is linear and can be calculated by:
Kj = (cj' - cj)/Mj.
 PROJECT SCHEDULING 3

9. Linear programming may be used to solve a CPM problem to minimize the crashing costs
needed to complete a project within a specified time limit.

PERT/CPM CRITICAL PATH PROCEDURE

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

Step 2: Determine the immediate predecessors for each activity in the project.

Step 3: Estimate the completion time for each activity.

Step 4: Draw a project network depicting the activities (on nodes) and immediate
predecessors listed in Steps 1 and 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
finish time for each activity.

Step 7: Use the difference between the latest start time and the earliest start time for each
activity to determine the slack for the 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.
4 CHAPTER 13

FLOW CHART FOR

COMPUTING PROJECT COMPLETION TIME PROBABILITY

Use the a-m-b beta

distribution values to compute
each activitys mean time t
using t = (a+4m+b)/6.

Determine the earliest and

latest start and finish times
and slack time for each activity.

Determine the critical path and

its mean time E(T) by summing
the paths mean activity times.

For each activity on the

critical path, compute the
activitys time variance using
st2 = ((b-a)/6)2.

Compute the critical paths

standard deviation s by
squarerooting the sum of its
activities variances.

For the desired project

completion time T, compute the
z-value using z = (T-E(T))/s.

Using the z-value and the

standard normal distribution
table, determine the probability
of the project duration
not exceeding T.
 PROJECT SCHEDULING 5

FLOW CHART FOR

PROJECT CRASHING

Identify critical path(s)

(CPs) with longest
completion time T.

Every CP No
has a still-crashable
activity ?

Yes

Select minimum-cost
activity or activities
that simultaneously
crash all CPs.

Sufficient No
crashing funds
remain ?

Yes

Crash selected activity

or activities by one time
unit and reduce T by 1.

Desired Project completion time

No Yes
project completion time is T. No more crashing
reached ? desired and/or possible.
 6 CHAPTER 13

ILLUSTRATED PROBLEMS

PROBLEM 1

Kraft's Kustom Kars is in the business of producing custom automobile assemblies. In

particular, Kraft operates a shop that builds and assembles the body and frame of the cars.
Kraft's operations begin with the processing of initial paperwork. This must be done
before any other operations are commenced. Once the paperwork has been completed,
the body of the car can be built in Room A and the frame of the car can be built in Room B.
When the body is built, it is transferred to Room C for finishing work. Similarly, when the
frame is built, it is transferred to Room D for finishing work.
When both are built, although not necessarily finished, the final paperwork can be
completed. When both the body and frame are finished, they are transported to the
assembly Room E, where the body is mounted to the frame.
In the frame building room, Room B, certain chemicals are used which must be
completely eliminated by a thorough washdown to prevent gaseous fumes from becoming a
health hazard. The project is considered complete when the final paperwork has been
completed, the body has been mounted to the frame, and Room B has been completely
washed down.
The table below gives the expected completion times in hours for each activity of the
project.

Activity Description Completion Time

A Initial Paperwork 3
B Build Body 3
C Build Frame 2
D Finish Body 3
E Finish Frame 7
F Final Paperwork 3
G Mount Body to Frame 6
H Room B Washdown 2

a) Draw the PERT network that corresponds to this problem.

b) Find the earliest and latest start and finish times for each activity of the project. How
long should the project take?

c) Which activities must not be delayed if the project is to be completed in the time
calculated in part (b)?

d) Suppose the body finish operation (D) were delayed four hours. By how much would
the entire project be delayed?
 PROJECT SCHEDULING 7

SOLUTION 1

Before constructing the PERT network, summarize in the following table the immediate
predecessor activities for each activity.
Immediate Completion
Activity Predecessors Times (Hr.)
A -- 3
B A 3
C A 2
D B 3
E C 7
F B,C 3
G D,E 6
H C 2
To construct a PERT network, there must be a node for each activity. An activitys
immediate predecessors are the nodes that immediately precede it.
The result is:

B D
3 3 G
6
F
3
A
Start Finish
3
E
7
C H
2 2

b) The earliest start time (ES) for activity A 0. Then the earliest finish time (EF) for an
activity is given by: EF = ES + (completion time). Then ES for an activity = max (EF for
all immediately preceding activities).
The forward pass to calculate ES and EF:

Earliest Earliest
Activity Start (ES) Finish(EF)
A 0 0+3= 3
B 3 3+3= 6
C 3 3+2= 5
D 6 6+3= 9
E 5 5 + 7 = 12
H 5 5+2= 7
F MAX(5,6) = 6 6+3= 9
G MAX(9,12) = 12 12 + 6 = 18
8 CHAPTER 13

The max(EF of the activities immediately preceding the Finish node ) = 18, so the
completion time of the project is 18.

The backward pass to calculate LF and LS :

Latest Latest
Activity Finish (LF) Start (LS)
H 18 18 - 2 = 16
G 18 18 - 6 = 12
F 18 18 - 3 = 15
E 12 12 - 7 = 5
D 12 12 - 3 = 9
C MIN(15,5,16) = 5 5-2= 3
B MIN(9,15) = 9 9-3= 6
A MIN(6,3) = 3 3-3= 0

This gives the completed network below.

D 6 9
B 3 6 3 9 12 G 12 18
3 6 9 6 12 18
F 6 9
3 15 18
A 0 3
Start Finish
3 0 3 E 5 12
7 5 12
C 3 5 H 5 7
2 3 5 2 16 18

The slack time for each activity (LS - ES) is summarized below:

Activity ES EF LS LF Slack
A 0 3 0 3 0
B 3 6 6 9 3
C 3 5 3 5 0
D 6 9 9 12 3
E 5 12 5 12 0
F 6 9 15 18 9
G 12 18 12 18 0
H 5 7 16 18 11

NOTE: One way to partially check the accuracy of your activity earliest/latest time
calculations is to compute every activity's slack two ways: Slack = (LS - ES) = (LF - EF)
 PROJECT SCHEDULING 9

If the preceding is not true, you have an error! Also, the number of different values in
your slack column should not exceed (but does not have to equal) the number of paths in
the project network.

c) Activities A, C, E, G have 0 slack times -- they form the critical path.

d) Activity D has a slack of 3. Hence a 4 hour delay in D would delay the entire project
4 - 3 = 1 hour.

PROBLEM 2

Consider the following project:

Immediate Optimistic Most Probable Pessimistic

Activity Predecessors Time (Hr.) Time (Hr.) Time (Hr.)
A -- 4 6 8
B -- 1 4.5 5
C A 3 3 3
D A 4 5 6
E A 0.5 1 1.5
F B,C 3 4 5
G B,C 1 1.5 5
H E,F 5 6 7
I E,F 2 5 8
J D,H 2.5 2.75 4.5
K G,I 3 5 7

a) Construct the PERT network for this problem.

b) Solve for the expected earliest and latest start and finish times for each activity.

c) Identify the critical path and give the estimated project completion time.

d) What is the probability the project will be completed within one day (24 hours)?

SOLUTION 2
10 CHAPTER 13

a) Nodes are needed for the start node, the finish node, and all of the activities.

D J

H
A E

I
C F
Start Finish

K
B G

b) Calculate the expected times, t, and variances, s2, for each activity.

t = (a + 4m + b)/6 s2 = ((b-a)/6)2

Activity Expected Time Variance

A 6 4/9
B 4 4/9
C 3 0
D 5 1/9
E 1 1/36
F 4 1/9
G 2 4/9
H 6 1/9
I 5 1
J 3 1/9
K 5 4/9

Thus, using the algorithm illustrated in problem 1, we have:

Activity ES EF LS LF Slack
A 0 6 0 6 0
B 0 4 5 9 5
C 6 9 6 9 0
D 6 11 15 20 9
E 6 7 12 13 6
F 9 13 9 13 0
G 9 11 16 18 7
H 13 19 14 20 1
I 13 18 13 18 0
J 19 22 20 23 1
K 18 23 18 23 0
c) The critical path is the path of 0 slack = A-C-F-I-K. The estimated project completion
time is the Max EF of the activities immediately preceding the Finish node = 23.
 PROJECT SCHEDULING 11

d) z = (24 - 23)/s. Here, s2 = s2A + s2C + s2F + s2I + s2K

= 4/9 + 0 + 1/9 + 1 + 4/9 = 2.

Hence, s = 1.414. Thus z = (24-23)/1.414 = .71. From Appendix C,

P(z < .71) = .5 + .2612 = .7612.

PROBLEM 3

National Business Machines (NBM) has just developed a new microcomputer it plans to
put into full scale production in a few months. The table and the PERT network below show
the precedence relations and give the activity times and costs under normal operations and
maximum crashing for a daily (22-hour) production of 1000 microcomputers at its local
plant.
NBM wants to know the minimum cost of producing the 1000 microcomputers within the
22-hour period. Formulate and solve a linear program that will yield this information.

F
E
A K
L
G
B
Start Finish
H M

Normal Normal Crash Crash

Activity Time (hr) Cost Time (hr) Cost
 12 CHAPTER 13

A 2 $2,000 1.5 $3,000

B 4 3,000 3 3,500
C 1 1,500 1 1,500
D 4 5,300 2.5 8,000
E 6 5,400 5 7,000
F 10 6,000 8 9,000
G 8 4,800 5 9,900
H 2 2,800 1 2,900
I 5 4,500 4 5,000
J 12 6,000 6 9,600
K 7 7,000 4 9,700
L 11 8,800 9 9,200
M 4 1,000 1 7,000

SOLUTION 3

First prepare a chart giving maximum crashing,

M = (Normal Time) - (Time Under Maximum Crashing)
and the marginal cost per hour for crashing,
K = ([Cost Under Maximum Crashing] - [Normal Cost])/M

Activity M K
A 0.5 2000
B 1 500
C 0 0
D 1.5 1800
E 1 1600
F 2 1500
G 3 1700
H 1 100
I 1 500
J) 6 600
K 3 900
L 2 200
M 3 2000

Let xA= earliest finish time for Activity A, and yA = amount of time Activity A is crashed.

The linear program must minimize the total extra cost:

MIN 2000yA + 500yB + 1800yD + 1600yE + 1500yF + 1700yG
+ 100yH + 500yI + 600yJ + 900yK + 200yL + 2000yM

Subject to:
(1) The project must be completed within 22 hours: xK < 22, xL < 22, xM < 22
 PROJECT SCHEDULING 13

(2) The amount an activity is crashed cannot exceed its maximum crashing:

yA < 0.5
yB < 1
yD < 1.5
yE < 1
yF < 2
yG < 3
yH < 1
yI < 1
yJ < 6
yK < 3
yL < 2
yM < 3

(3) For each activity:

(Earliest Finish Time) > (Earliest Finish Time of Preceding Activity)
+ [(Normal Activity Time) - (Amount of Time the Activity is crashed)]

xA > 0 + (2 yA) or xA + yA > 2

xB > 0 + (4 yB) or xB + yB > 4
xC > 0 + (1 0) or xC > 1

xD > xA + (4 yD) or xD + yD xA > 4

xE > xB + (6 yE) or xE + yE xB > 6
xG > xB + (8 yG) or xG + yG xB > 8
xH > xB + (2 yH) or xH + yH xB > 2
xI > xC + (5 yI) or xI + yI xC > 5
xJ > xC + (12 yJ) or xJ + yJ xC > 12

xF > xD + (10 yF) or xF + yF xD > 10

xF > xE + (10 yF) or xF + yF xE > 10
xL > xG + (11 yL) or xL + yL xG > 11

xK > xF + (7 yK) or xK + yK xF > 7

xK > xI + (7 yK) or xK + yK xI > 7
xM > xH + (4 yM) or xM + yM xH > 4
xM > xJ + (4 yM) or xM + yM xJ > 4

(4) Non-negativity of the variables:

14 CHAPTER 13

xi > 0 for I = A, B, C, ., M
yj > 0 for j = A, B, D, ., M

The Management Scientist provided the following solution output:

OBJECTIVE FUNCTION VALUE = 4700.000

VARIABLE VALUE REDUCED COSTS
XA 5.000 0.000
XB 3.000 0.000
XC 1.000 0.000
XD 9.000 0.000
XE 9.000 0.000
XF 18.000 0.000
XG 11.000 0.000
XH 13.000 0.000
XI 18.000 0.000
XJ 13.000 0.000
XK 22.000 0.000
XL 22.000 0.000
XM 17.000 0.000
YA 0.000 2000.000
YB 1.000 0.000
YD 0.000 1800.000
YE 0.000 100.000
YF 1.000 0.000
YG 0.000 1500.000
YH 0.000 100.000
YI 0.000 500.000
YJ 0.000 600.000
YK 3.000 0.000
YL 0.000 0.000
YM 0.000 2000.000

Summary:
Crash activity B one hour, activity F one hour, and activity K three hours. The 1000-unit
daily production output will be achieved in 22 hours at a crashing cost of $4700.
 PROJECT SCHEDULING 15

PROBLEM 4

Given the following PERT network for Gus's Painters:

A D

C Finish
Start

B E

The following means and standard deviations were calculated for the activities:

Activity t s
A 6 2
B 3 1
C 6 1
D 15 2
E 12 2

There is a $100,000 bonus for completing the project in 26 weeks. Currently activity E
is assigned to Wilson Brothers. Gus has the option of hiring Jones Inc. for activity E. Their
expected completion time for activity E is 8 weeks (with a standard deviation of 2), but they
will cost Gus $15,000 more to do E than Wilson Brothers. Should Gus hire Jones?

SOLUTION 4

Analysis using Wilson Brothers to do E:

Activity ES EF LS LF
A 0 6 0 6
B 0 3 9 12
C 6 12 6 12
D 6 21 9 21
E 12 24 12 24

Hence the critical path is A - C - E and the overall expected project completion time is
24.
The variance of the critical path is:

s2 = s2A + s2C + s2E = (2)2 + (1)2 + (2)2 = 9. Thus s = 3.

To find the probability of completing the project in 26 weeks, calculate,

z = (26 - 24)/3 = .67.
16 CHAPTER 13

Thus the probability of finishing in 26 weeks is P(z < .67). From Appendix C, the table
gives the P(0 < z < .67) = .2486. Therefore the probability of completing the project
within 26 weeks is .5 + .2486 = .7486.

Thus the expected bonus using Wilson Brothers to do E is:

(.7486)(100,000) + (.2514)(0) = $74,860.

Analysis using Jones, Inc. to do E:

Activity ES EF LS LF
A 0 6 0 6
B 0 3 10 13
C 6 12 7 13
D 6 21 6 21
E 12 20 13 21

Hence the critical path is A - D and the overall expected project completion time is 21.
The variance of the critical path is:

s2 = s2A + s2D = (2)2 + (2)2 = 8. Thus s = 2.828.

To find the probability of completing the project in 26 weeks, calculate,

z = (26 - 21)/2.828 = 1.77.

Thus the probability of finishing in 26 weeks is P(z < 1.77). From Appendix C, the table
gives the P(0 < z < 1.77) = .4616. Therefore the probability of completing the project
within 26 weeks is .5 + .4616 = .9616.

Thus the expected bonus using Jones, Inc. to do E is:

(.9616)(100,000) + (.0384)(0) = $96,160.

Decision:
The difference in expected returns between the two firms is: $96,160 - $74,860 =
$21,300. Since this is greater than the $15,000 cost to hire Jones, Inc., Gus should
hire Jones, Inc.
 PROJECT SCHEDULING 17

PROBLEM 5

For the project represented below, determine the earliest and latest start and finish
times for each activity as well as the expected overall completion time.

G I
A 3 4
9
F H
B 4 5
Start Finish
8
D
3
J
E 8
4

C
10

SOLUTION 5

a) Solving the PERT network for the ES, EF, LS, LF, and slack times by the method
illustrated in problem 1, we can summarize:

Activity ES EF LS LF Slack
A 0 9 0 9 0
B 0 8 5 13 5
C 0 10 7 17 7
D 8 11 22 25 14
E 8 12 13 17 5
F 9 13 13 17 4
G 9 12 9 12 0
H 12 17 12 17 0
I 12 16 21 25 9
J 17 25 17 25 0

The overall project completion time is 25 weeks.

 18 CHAPTER 13

ANSWERED PROBLEMS

PROBLEM 6

Consider a project that has been modeled as follows:

Activity Immediate Predecessors Completion Time (hr.)

A --- 7
B --- 10
C A 4
D A 30
E A 7
F B,C 12
G B,C 15
H E,F 11
I E,F 25
J E,F 6
K D,H 21
L G,J 25

a) Draw the PERT network for this project and determine project's expected completion
time and its critical path.

NOTE: If you are only interested in identifying the critical path and expected project
completion time, there might be an easier approach than determining every activity's
earliest start and finish times. List (if there are not too many) every path in the network
and, for each one, sum the expected times of the activities on that path. You are looking
for the path with the largest sum.

b) Can activities E and G be performed simultaneously without delaying the minimum

project completion time?

c) Can one person perform A, G, and I without delaying the project?

d) By how much can activities G and L be delayed without delaying the entire project?

e) How much would the project be delayed if activity G was delayed by 7 hours and activity
L was delayed by 4 hours? Explain.
 PROJECT SCHEDULING 19

PROBLEM 7

Given the following PERT network of tasks with completion times in hours for
scheduling interns in a hospital:

C K
A 5 H 1
4 2
D
3
E I
Start Finish
5 3
F
B 2 J
3 5 L
G 7
1

a) If interns start at midnight (00:00), determine each activitys ES, EF, LS, LF, and slack.

b) What is the critical path and project completion time?

c) If an intern can do any job and works a 24-hour shift, show that two interns can complete
all the jobs. (Hint: One intern is assigned the critical path jobs.)

PROBLEM 8

A project consists of five activities. Naturally the paint mixing precedes the painting
activities. Also, both ceiling painting and floor sanding must be done prior to floor buffing.

Optimistic Most Probable Pessimistic

Activity Time (hr.) Time (hr.) Time (hr.)
Floor sanding 3 4 5
Floor buffing 1 2 3
Paint mixing 0.5 1 1.5
Wall painting 1 2 9
Ceiling painting 1 5.5 7

a) Construct a PERT network for this problem.

b) What is the expected completion time of this project?

c) What is the probability that the project can be completed within 9 hr.?

PROBLEM 9
 20 CHAPTER 13

Given the following PERT network modeling new home construction by Bonanza
Development:

D I
3 3

A
J L
6
C 1 3

1 E
Start Finish
3
K
5
B F
8 4

H
5

G
10

a) Prepare a table of the earliest and latest start and finish times and slack times for each
activity in Bonanza's project.

b) What is the critical path and the expected project completion time?

c) Reliable Plumbers, the subcontractor performing activity J, is going to be delayed 5

weeks. If the project is delayed, it will cost Bonanza $2000 per week of delay of the
entire project. Reliable is charging $3000 for the plumbing.
Bonanza has three options:
(1) Keep Reliable Plumbers.
(2) Cancel the contract with Reliable Plumbers and hire Local Plumbers, Inc. Local
Plumbers, however, will take two weeks to do activity J, and will charge $7000.
(3) Bonanza can train its own employees who are currently performing activity E to
do the work. This involves a two-week training period as soon as activity E is
done. Then it is expected it will take them three weeks to perform activity J.
The cost of the training is $800 per week and the cost of them doing activity J is
$1,000 per week.

Which alternative do you recommend to Bonanza? Explain.

PROBLEM 10
 PROJECT SCHEDULING 21

Consider the following PERT network with estimated times in weeks. The project is
scheduled to begin on May 1.

E
1
B F
A 3 D 2 H
Start Finish
1 2 7
G
3
C
4

The three-time estimate approach was used to calculate the expected times and the
following table gives the variance for each activity:

Activity Variance Activity Variance

A 1.1 E .3
B .5 F .6
C 1.2 G .6
D .8 H 1.0

a) Give the expected project completion date and the critical path.

b) By what date are you 99% sure the project will be completed?

c) The project has a target completion date of August 28 (17 weeks). If the project is
completed by August 28, the profit on the project will be $10,000. If work is not
completed by August 28, a $5,000 penalty will be incurred, reducing the project's profit
to $5,000. For $2,000 more than is currently being spent for a firm to do activity H, a
more experienced firm can complete the activity in just 5 weeks. Should this offer be
accepted? (Assume the variance for H will not change.)
 22 CHAPTER 13

PROBLEM 11

Consider the following PERT network.

D
I

F
E
A
H J
Start Finish
C

B G

The following chart has been prepared giving the optimistic time (a), the most likely time
(m), and the pessimistic time (b), in weeks for each activity.

Activity a m b Activity a m b
A 2 8 14 F 2 3 10
B 3 12 21 G 3 9 15
C 2 5 8 H 7 8 9
D 4 5 12 I 3 11 13
E 1 3 17 J 7 10 13

a) Determine the critical path, expected project completion time, and standard deviation of
the project completion time.

b) Management insists that the project be completed in 36 weeks and will be charged a
$100,000 fine for any time overrun. If, at a cost of $3,000, the expected completion
time of activity A could be reduced by 2 weeks, should the extra money be spent?
(Assume A's variance does not change.)

c) Why is considering only critical path activities for project completion time not always a
good assumption in probabilistic cases? (HINT: Consider activity E.)
 PROJECT SCHEDULING 23

PROBLEM 12

Plane, Inc. is a manufacturer of heavy equipment and is considering introducing a new

line of small steamrollers. Development is to proceed as follows.
A feasibility study will first be performed. Upon receiving a successful feasibility report, a
manufacturing building is to be secured and a project leader hired. Once the building is
secured, Plane will be committed to the project. Therefore an advertising group will be
selected and the raw materials for the manufacturing process will be purchased. When, in
addition to securing the building, a project leader has been named, a manufacturing staff
will be recruited.
After the manufacturing staff has been selected and the raw materials purchased, a
prototype model of the steamroller will be produced. Following the completion of the
prototype, work will begin on a production run of 100 steamrollers. When both the
prototype model has been built and the advertising staff selected, an intensive advertising
campaign will be launched.
The development phase of this project will be complete with the production of the first
100 steamrollers and the initiation of the advertising campaign.
Two separate cost analyses have been prepared. One is effective under current
(normal) conditions, while the other is effective if the development phase of the activities is
"crashed". These are summarized below. (Times are in weeks.)

Normal Crash
Activity Time Cost Time Cost
Feasibility Study (A) 6 $ 80,000 5 $100,000
Building Purchased (B) 4 100,000 4 100,000
Project Leader Hired (C) 3 50,000 2 100,000
Advertising Staff Selected (D) 6 150,000 3 300,000
Materials Purchased (E) 3 180,000 2 250,000
Manufacturing Staff Hired (F) 10 300,000 7 480,000
Prototype Manufactured (G) 2 100,000 2 100,000
Production Run of 100 (H) 6 450,000 5 800,000
Advertising Campaign (I) 8 350,000 4 650,000

a) Draw the PERT network for this problem.

b) Formulate and solve a linear program for determining the minimum cost of completing
this project in half a year (=26 weeks).

c) What assumptions are made in calculating the "marginal" costs for the activities?

d) Interpret the meaning of the shadow price that would be associated with the constraint
that set the maximum completion time to 26 weeks.

PROBLEM 13
24 CHAPTER 13

Joseph King has ambitions to be mayor of Williston, North Dakota. Joe has determined
the breakdown of the steps to the nomination and has estimated normal and crash costs
and times for the campaign as follows (times are in weeks):

Normal Crash Immediate

Activity Time Cost Time Cost Predecessors

A. Solicit Volunteers 6 $5,000 4 $ 9,000 ----

B. Initial "Free"
Exposure 3 $4,000 3 $ 4,000 ----
C. Raise Money 9 $4,000 6 $10,000 A
D. Organize and Co-
ordinate Schedule 4 $1,000 2 $ 2,000 A
E. Hire Advertising
Firm 2 $1,500 1 $ 2,000 B
F. Arrange Major
TV Interview 3 $4,000 1 $ 8,000 B

G. Advertising
Campaign 5 $7,000 4 $12,000 C,E
H. Personal
Campaigning 7 $8,000 5 $20,000 D,F

a) Joe King is not a wealthy man and would like to organize a four month (16 week)
campaign at minimum cost. Write and solve a linear program to accomplish this task.

b) Dan Wetzel is an independent who is also trying to make a bid to become mayor of
Williston. He has promised a clean campaign, one that he will initially finance on his
own. He has $50,000 to invest in his campaign. Being a student of recent successful
political campaigns, he knows that his best chance to win is be a "fresh new face" at
nomination time. Hence he wishes to keep the entire campaign from beginning to end
at a minimum. Write a linear program that, when solved, will minimize the total time of
the campaign while keeping expenditures to a maximum of $50,000.
 PROJECT SCHEDULING 25

PROBLEM 14

For the project represented below, determine the earliest and latest start and finish
times for each activity as well as the expected overall completion time.

E
G
B
A D
Start Finish

C F

Activity Time ES EF LS LF Slack

A 4
B 3
C 4
D 2
E 5
F 2
G 5
H 6
 26 CHAPTER 13

TRUE/FALSE

___ 15. All activities on a critical path have zero slack time.

___ 16. In PERT, it is assumed that the amount of time to complete any one activity is
independent of the amount of time to complete any other activity in the project.

___ 17. In PERT, an activity's most probable time is the same as its expected time.

___ 18. In PERT, it is assumed that the underlying distribution for each activity in the three-
time estimate approach is a normal distribution.

___ 19. In a given PERT problem, activities F and G are on the critical path. If each is
delayed two weeks, then in all cases, the project will be delayed four weeks.

___ 20. The difference between an activity's earliest finish and latest finish equals the
difference between its earliest start and latest start.

___ 21. In a given PERT problem, activities F and G are not on the critical path and each has
two weeks slack time. If both are delayed by two weeks each, then in all cases, the
project will not be delayed.

___ 22. An activity can be started as soon as any one of the activities that immediately
precedes it is finished.

___ 23. In a given PERT problem, activity F is on the critical path. If its time is reduced by
five weeks, then in all cases, the overall project completion time will be reduced by
five weeks.

___ 24. In PERT, the critical path is the path of longest distance through the network.

___ 25. In CPM, the marginal cost per weeks saving of an activitys completion time is valid
only between its normal time and the time after maximum crashing.

___ 26. It is possible to have more than one critical path at a time.

___ 27. In CPM, if activity Bs normal completion time is 8 weeks and normal cost is $10,000,
and its completion time after maximum crashing is 5 weeks at a cost of $15,000,
then the assumption is that if $13,000 is spent on activity B, its completion time is
6.8 weeks.

___ 28. The project manager should monitor the progress of any activity with a large
variance even if the expected times do not identify the activity as a critical activity.

___ 29. A critical activity can be part of a noncritical path.