Project Scheduling: PERT/CPM
73-220 Lecture 20
1
Agenda ●
Review of last class. – PERT/CPM with unknown activity times
●
Project scheduling – PERT/CPM – Considering time-cost trade-off.
●
Next Class
2
Crashing Activity Times ■
In the Critical Path Method (CPM) 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’.
■
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.
3
Example: EarthMover, Inc. EarthMover is a manufacturer of road construction equipment including pavers, rollers, and graders. The company is faced with a new project, introducing a new line of loaders. Management is concerned that the project might take longer than 26 weeks to complete without crashing some
activities. 4
Example: EarthMover, Inc. Immediate Completion Activity Description Predecessors Time (wks) A Study Feasibility --6 B Purchase Building A 4 C Hire Project Leader A 3 D Select Advertising Staff B 6 E Purchase Materials B 3 F Hire Manufacturing Staff B,C 10 G Manufacture Prototype E,F 2 H Produce First 50 Units G 6 I Advertise Product D,G 8 It can be verified that it takes 30 weeks to complete the whole project. 5
Example: EarthMover, Inc. ●
Crashing The completion time for this project using normal times is 30 weeks. Which activities should be crashed, and by how many weeks, in order for the project to be completed in 26 weeks?
6
Example: EarthMover, Inc. ■
Normal Costs and Crash Costs
Normal Crash Activity Time Cost Time Cost A) Study Feasibility 6 $ 80,000 5 $100,000 B) Purchase Building 4 100,000 4 100,000 C) Hire Project Leader 3 50,000 2 100,000 D) Select Advertising Staff 6 150,000 3 300,000 E) Purchase Materials 3 180,000 2 250,000 F) Hire Manufacturing Staff 10 300,000 7 480,000 G) Manufacture Prototype 2 100,000 2 100,000 H) Produce First 50 Units 6 450,000 5 800,000 I) Advertising Product 8 350,000 4 650,000
7
Key Considerations ● ● ●
Determine the max reduction time and unit time crashing cost for each activity. Decision variables are set up in two groups: finish time and time to crash for each activity. Three groups of constraints: – Finish time >= earliest start + activity time. – Crashed time <= max reduction. – New deadline has to be honoured.
» Finish time for a node linked to Finish has to be within the new deadline.
– Note:
» Earliest start >= finish time of each immediate predecessor. » activity time = normal activity time – time to crash.
8
Max Reduction and Crashing Cost Activity Max reduction Unit crashing cost A B C D E F G H I
1 0 1 3 1 3 0 1 4
20,000=20,000/1 0 50,000=50,000/1 50,000 = 150,000/3 70,000=70,000/1 60,000=180,000/3 0 350,000=350,000/1 75,000=300,000/4 9
Example: EarthMover, Inc. ■
Linear Program for Minimum-Cost Crashing Let:
Xi = finish time for activity i Yi = the amount of time activity i is crashed
Min 20YA + 50YC + 50YD + 70YE + 60YF + 350YH + 75YI s.t.
YA < 1 YB < 0 YC < 1 YD < 3 YE < 1 YF < 3 YH < 1 YI < 4
XA > XB > XC > XD > XE > XF > XF > XG >
0 + (6 - YA) XA + (4 - YB) XA + (3 - YC) XB + (6 - YD) XB + (3 - YE) XB + (10 - YF) XC + (10 - YF) XE + (2 - YG)
XG > XH > XI > XI > XH < XI <
XF + (2 - YG) XG + (6 - YH) XD + (8 - YI) XG + (8 - YI) 26 26
Xi, Yj > 0 for all i 10
Multiple Nodes Linked to Finish G Finish H ●
Two ways to formulate new deadline constraints: – Without introducing a new decision variable. » xG <= T, xH <= T (new deadline) » each of the activities directly linked to the finish node has to be finished within the new deadline.
– Introduce a new decision variable xFIN to indicate the project finish time. » xFIN >= xG, xFIN >= xH » xFIN <= T (new deadline)
11
Notes for the LP Solution After the LP model is solved, # of unit times to crash for each activity is obtained (See the worksheet on the next slide). ● To derive a new activity schedule for the crashed times, it is necessary to apply the routine PERT/CPM technique again. ●
12
Excel Solution Problem Data Activity A B Normal time 6 Crash time 5 Normal cost 80 Crash cost 100 Maximum reduction 1 Crash cost per day20
4 4 100 100 0 0
Decision variables Activity A B Finish time 5 Crash time 1
9 0
C
D 3 2 50 100 1 50
C
E 6 3 150 300 3 50
D 8 0
F 3 2 180 250 1 70
E 18 0
G 10 7 300 480 3 60
F 16 0
H 2 2 100 100 0 0
G 16 3
I 6 5 450 800 1 350
H 18 0
8 4 350 650 4 75
I 24 0
26 0
Objective function Min 200 Constraints Finish timeA B LHS 6 Type >= >= RHS 6 Maximum crash A time B LHS 1 Type <= <= RHS 1 Project completion time LHS 24 Type <= <= RHS 26
C 4
D 3
>= 4
>= 3
C 0
>=
D
>=
E
>=
F
>=
G
>=
H
I 6
>= 2
I 8
>= 6
8 >=
8
8
I 0
<= 0
H 2
2
0 <=
3
G 2
10
3 <=
1
G 11
10
0 <=
3
F 10
3
0 <=
1
F 7
6
0 <=
0
E 9
0 <=
1
4
26 26
13
Next Class ●
Homework:
– Develop activity schedule and determine the critical path for the example based on the NORMAL activity times. – Develop activity schedule and determine the critical path for the example based on the CRASHED activity times.
● ●
Do more questions from Chapter 10. Read Section 11.1 EOQ Model in Inventory Management.
YOU LEARN DECISION ANALYSIS BY DOING DECISION ANALYSIS!! 14