26/10/2011
Program Evaluation And Review Technique (PERT) Critical Path Method (CPM)
www.labsistemtmip.wordpress.com
g q Program Evaluation And Review Technique • Untuk sebanyak mungkin mengurangi adanya penundaan, maupun gangguan produksi • Mengkoordinasikan berbagai bagian suatu pekerjaan secara menyeluruh dan mempercepat selesainya proyek. • Suatu pekerjaan yang terkendali dan teratur, karena jadwal dan anggaran dari suatu pekerjaan telah ditentukan terlebih dahulu sebelum dilaksanakan. • Pencapaian suatu taraf tertentu dimana waktu merupakan dasar penting dari PERT dalam penyelesaian kegiatan-kegiatan bagi suatu proyek.
1
26/10/2011
Critical Path Method (metode jalur kritis) k iti ) • Diselesaikan secara tepat waktu serta tepat biaya. Metode perencanaan dan pengendalian proyekproyek • Prinsip pembentukan jaringan. • Jumlah waktu yang dibutuhkan dalam setiap tahap suatu proyek dianggap diketahui dengan pasti, • Hubungan antara sumber yang digunakan dan waktu yang diperlukan untuk menyelesaikan proyek.
2
26/10/2011
NOMOR PENGERJAAN
LAMA PENGERJAAN
TANGGAL SELESAI
TANGGAL MULAI
3
26/10/2011
PERT
CPM
Kelangsungan Proyek
Data , Waktu, Biaya
Informasi
Sasaran
Arti Panah
Perencanaan Dan Pengendalian Proyek
Belum Pernah Dkerjakan,
Belum Diketahui
Waktu Pengerjaan
Tepat Waktu, Sebab Dengan Penyingkatan Waktu Maka Biaya Proyek Turut Mengecil,
Anak Panah Menunjukkan Tata Urutan (Hubungan Presidentil)
Menjadwalkan D Dan Mengendalikan Aktivitas
Sudah Pernah Dik j k Dikerjakan
Tepat Biaya
Tanda Panah Ad l h Adalah Kegiatan
Tercepat, Terlama Terlayak
Telah Diketahui Ol h EEvaluator Oleh l t
Waktu PPengerjaan j Waktu Yang Paling Tepat Dan Layak Untuk
A Project
Suatu set pekerjaan yang dilakukan secara sekuensial
Pekerjaan
Tujuan (Goals) Menjamin suatu project
▪ ▪ ▪ ▪
mencapai tujuannya Selesai tepat waktu Sesuai Anggaran Sesuai dengan sumber daya
Menyediakan mekasnisme monitoring
8
4
26/10/2011
Jalur Kritis / Critical Path: Suatu aktivitas sekuensial yang menuju pada
penyelesaian project.
Slack: Jumlah fleksibitas dalam menjadwalan j aktivitas yyang g
tidak kritis.
9
An Activity On Node (AON) Network Representation of the Klonepalm 2000 Computer Project
B 15
C 5
Immediate Estimated E Activity Predecessor Completion Time 21 None A None 90 B A 15 C B 5 B D 20 D G H E 21 20 D 28 F A 25 G C,F 14 H D 28 I A J 30 J D,I 45 45
A
A 90
F 25
G 14
I 30
A A
5
26/10/2011
Activity
Seberapa cepat Turnamen dapat Disesaikan? Aktivitas manakah Yang kritis?
Description
Immediate Predecessor
Time Estimate (days)
A
Select teams
3
B
Mail out invitations
C
Arrange accommodations
D
Plan promotion
B, C
3
E
Print tickets
B, C
5 10
A
5 10
F
Sell tickets
E
G
Complete arrangements
C
8
H
Develop schedules
G
3
I
Practice
J
Conduct tournament
D, H
2
F, I
3
11
Activity
Expected Duration (weeks)
Immediate Predecessors
A
2
B
2
C
3
D
2
B
E
1
C,D
Activities are represented by nodes:
A,2
C,3 E,1
A
B,2
D,2
12
6
26/10/2011
Forward Pass: Pass Calculate Earliest Start Times, Earliest Finish Times
Backward Pass: Calculate Latest Start Times, Latest Finish Times
Slack Latest Start Time – Earliest Start Time
13
A,2
C,3 E,1
B,2
D,2
Activit y
Expecte d Duration (weeks)
Immediate Predecess ors
A
2
B
2
C
3
A
D
2
B
E
1
C,D
Earliest Start Time
Earliest Finish Time
Latest Finish Time
Latest Start Time
Slack
14
7
26/10/2011
A,2
Activit y
Expecte d Duration D ti (weeks)
A B C
3
D E
C,3 E,1
B,2
D,2
Immediate Predecess ors
Earliest Start Time Ti
Earliest Finish Time Ti
Latest Finish Time Ti
Latest Start Time Ti
Slack
2
0
2
2
0
0
2
0
2
3
1
1
A
2
5
5
2
0
2
B
2
4
5
3
1
1
C,D
5
6
6
5
0
Activities with 0 slack are on the critical p path: Activity A Slack
Activity C Activity B
Act. E
Activity D
Act. E Time
0
1
2
3
4
5
6
15
Activity
Duration (weeks)
Imm Pred
A
5
B
4
C
3
D
2
A
E
6
B, C
F
3
D E D,
G
7
E
H
5
F
I
4
F
J
2
G
ES
EF
LF
LS
SLACK
16
8
26/10/2011
Acti vity A
Description
Imm Pred
Select teams S l
Dur
ES
EF
LS
LF
SLCK
3
B
Mail out invitations
C
Arrange accommodations
A
5
D
Plan promotion
B, C
E
Print tickets
B, C
5
F
Sell tickets
E
10
G
C
8
H
Complete arrangements Develop schedules
G
3
I
Practice
J
Conduct tournament
10 3
D, H
2
F, I
3
17
Decision Variables: Variables
Objective Function:
A,2
C,3 E,1
B2 B,2
D2 D,2
Constraints:
18
9
26/10/2011
The terminal activity The single activity that identifies when the project is
completed. If there is no natural terminal activity, add a dummy node with 0 duration: A, 1
D, 4 C, 1
B, 3
E, 2
19
Aktivitas digambarkan melelui tanda panah A,2
Source: 1
C,3
A,2
E,1
E,1 B,2
D,2
C,3
D,2 Source: 1
Demand: 1
B,2
Find the maximum cost flow Interpretation: an arc has a flow of 1 if it is on the critical path
20
10
26/10/2011
Often there are penalties and bonuses for late or early completion of a project.
21
Sebuah kontrak untuk menyelesaikan pekerjaan dalam waktu 16 minggu. Terdapat bonus sebesar $12,000 untuk setiap pekerjaan yang lebih awal per minggunya dari jadwal. Penalti sebesar $15,000 per minggu keterlambatan. Kapankah p waktu ideal dalam menyelesaikan y proyek p y tsb? Aktivitas manakah yang harus diakselerasi dan seberapa banyak?
22
11
26/10/2011
y Activity
Standard Duration (weeks)
Minimum Duration (weeks)
A
5
3
8
B
4
2
14
C
3
1
16
D
2
1
7
A
E
6
3
21
B, C
Extra Cost at Minimum Time ($000)
Imm Pred
F
3
2
4
D, E
G
7
3
8
E
H
5
3
8
F
I
4
3
8
F
J
2
2
N/A
G
Maximum Reduction
Incremental Cost
23
The critical path method (CPM) is a deterministic approach to project planning.
Completion time depends only on the amount of money allocated to the activity.
Reducing an activity’s completion time is called “crashing”.
12
26/10/2011
There are two crucial time durations to consider for each activity. activity Normal completion time (NT) Crash completion time (CT) NT is achieved when a usual or normal cost (NC)
is spent to complete the activity. CT is achieved when a maximum crash cost (CC)
is spent to complete the activity.
The Linearity Assumption [Normal Time - Crash Time] = [Crash Cost - Normal Cost] [Normal Cost] [Normal Time]
13
26/10/2011
Normal NC = $2000 NT = 20 days
A demonstration
Time 20 …and save on completion time on 18 …and save more completion time 16
Total Cost = $2600 of the Job time = 18 days
Linearity assumption
Add to Add more tothe the normal normal cost...cost...
14 12 10
Save 25% on completion time
8 6 4 2
Marginal Cost
= =
Add 25% to the normal cost Crashing CC = $4400 CT = 12 days
Additional Cost to get Max. Time Reduction Maximum Time reduction (4400 - 2000)/(20 - 12) = $300 per day
5 10 15 20 25 30 35 40 45
Cost ($100)
Meetings a Deadline at Minimum Cost Let D be the deadline date to complete a project. If D cannot be met using normal times, additional resources
must be spent on crashing activities. The objective is to meet the deadline D at minimal additional
cost. Tom Larkin’s political campaign problem illustrates the concept.
14
26/10/2011
TOM LARKIN’S POLITICAL CAMPAIGN Tom Larkin has 26 weeks of mayoral election campaign to plan. The campaign consists of the following activities
Immediate Immediate Normal Normal Schedule Schedule Reduced Reduced Schedule Schedule Activity Predecessor Cost Time Cost Activity Predecessor Time Time Cost Time Cost A. None 44 2.0K 22 5.0K A. Hire Hire campain campain staff staff None 2.0K 5.0K B. Prepare position paper None 6 3.0 3 99 B. Prepare position paper None 6 3.0 3 C. AA 44 4.5 22 10 C. Recruit Recruit volunteers volunteers 4.5 10 D. A,B 66 2.5 44 10 D. Raise Raise funds funds A,B 2.5 10 E. DD 22 0.5 11 11 E. File File candidacy candidacy papers papers 0.5 F. EE 13 13.0 88 25 F. Prepare Prepare campaign campaign material material 13 13.0 25 G. EE 11 1.5 11 1.5 G. Locate/staff Locate/staff headquarters headquarters 1.5 1.5 H. C,G 20 6.0 10 23.5 H. Run Run personal personal campaign campaign C,G 20 6.0 10 23.5 I.I. Run media campaign F 9 7.0 5 16 Run media campaign F 9 7.0 5 16
NETWORK PRESENTATION
A
B
C
D
H To meet the deadline date of 26 weeks some activities G be crashed. must FINISH
E
F
I
WINQSB CPM schedule with normal times. Project completion (normal) time = 36 weeks
15
26/10/2011
Mayoral Campaign Crash Schedule AA cctiv tivity ity AA BB CC DD EE FF G G HH II
•
NN TT 44 66 44 66 22 1133 11 2200 99
NN CC ($ ($)) 22000000 33000000 44550000 22550000 550000 1133000000 11550000 66000000 77000000
CC TT 22 33 22 44 11 88 11 1100 55
CC CC 55000000 99000000 1100000000 1100000000 11000000 2255000000 11550000 2233550000 1166000000
TT M M ($ ($)) 22 $$11,5 550000 ,5 33 22000000 22 22775500 22 33775500 11 550000 55 22440000 ****** ** **** 1100 11775500 44 22225500
Heuristic Approach – Three observations lead to the heuristic. • The project time is reduced only by critical activities. • The maximum time reduction for each activity is limited. • The amount of time a critical activity can be reduced before another. path becomes critical is limited.
– Small crashing problems with small number of critical paths can be solved by this heuristic approach. – Problems with large number of critical paths are better solved by a linear programming model.
16
26/10/2011
Linear Programming Approach V Variables Xj = start time for activity j. Yj = the amount of crash in activity j.
Objective Function Minimize the total additional funds spent on crashing activities.
Constraints ▪ The project must be completed by the deadline date D ▪ No activity can be reduced more than its Max. time reduction ▪ Start time of an activity Finish time of immediate predecessor
≥
Minimize total crashing costs Min1500YA + 2000YB + 2750YC + 3750YD + 500YE + 2400YF + 17500YH + 2250YJ Meet the deadline
ST X (FIN ) ≤ 26
X(FIN) ≥ X I + (9 − YI ) X(FIN) ≥ X + (20 − YH ) X I ≥ X F + (13 − YF )
YA ≤ 2
XH ≥ X G + 1
YB ≤ 3
Maximum time-reduction constraints
X H ≥ X C + (4 − YC )
YC ≤ 2
X G ≥ X E + (2 − YE )
YD ≤ 2
X F ≥ X E + (2 − YE )
YE ≤ 1
A
YF ≤ 5
C
YH ≤ 10
X E ≥ X D + (6 − YD )
H
G B
D
E
Activity can start only after all the predecessors are completed.
X D ≥ X B + (6 − YB ) X D ≥ X A + (4 − YA )
FINISH X C ≥ X A + (4 − YA )
F
I
17
26/10/2011
Most of the activities become critical !!
Deadline
Crashing costs
WINQSB Crashing Optimal Solution
Other Cases of Project Crashing Operating Optimally within a given budget ▪ When a budget is given, minimizing crashing costs is a constraint, not an objective. ▪ In this case the objective is to minimize the completion time.
Incorporating Time Time-Dependent Dependent Overhead Costs ▪ When the project carries a cost per time unit during its duration, this cost is relevant and must be figured into the model. ▪ In this case the objective is to minimize the total crashing cost + total overhead cost
18
26/10/2011
TOM LARKIN - Continued The budget is $75,000. The objective function becomes a constraint Minimize X(FIN) ( ) 1500 YA+ 2000 YB + 2750 YC + 3750 YD + 500 YE + 2400 YF +1750 YH + 2250 YJ
This constraint becomes the objective function X(FIN)
≤ 26
1500 YA+ 2000 YB + 2750 YC + 3750 YD + 500 YE + 2400 YF +1750 YH + 2250 YJ ≤ 75,000 - 40,000 = 35,000
The rest of other crashing model constraints remain the same.
Normal time is 13 weeks Project completion time
Normal time is 17 weeks Overall crashing cost
WINQSB Crashing Analysis with a Budget of $75000
19
26/10/2011
Administrative Costs of $100 per week. The campaign must be completed within 26 weeks, but there are weekly operating expenses of $100. The Objective Function becomes Minimize 1500 YA+ 2000 YB + 2750 YC + 3750 YD + 500 YE + 2400 YF +1750 YH + 2250 YJ + 100X(FIN)
The other crashing model constraints remain the same.
20
