Chương 8
Bài toán Sơ Đồ Mạng
trong Hoạch Định Dự Án
2
C8. Bài toán Sơ đồ Mạng
trong Hoạch định Dự án
1. Giới thiệu chung về Dự án
2. Diễn tả Sơ đồ Mạng của Dự án
3. Phương pháp CPM, PERT
33
1. Giới thiệu chung về Dự án
•
Dự án là một quá trình gồm các công việc, nhiệm vụ
có liên quan với nhau, được thực hiện nhằm đạt được
mục tiêu đã đề ra trong điều kiện ràng buộc về thời
gian, nguồn lực và ngân sách.
•
Đặc điểm
•
Mục tiêu rõ ràng
•
Thời hạn nhất định
•
Nguồn lực sử dụng hạn chế
•
Độc đáo
4
1. Giới thiệu chung về Dự án (tt)

2 kỹ thuật hoạch định dự án
•

2. Diễn tả Sơ đồ Mạng của Dự án

Quy ước
•
Sự kiện (Event): Là sự kết thúc của 1 hay một số công tác,
để cho các công tác tiếp sau có thể bắt đầu được.
•
Công tác (Công việc – Activity): Là hoạt động sản xuất
giữa 2 sự kiện.
•
Công tác thực: Là hoạt động sản xuất cần nguồn lực (gồm
nhân vật lực) và thời gian. Công tác thực -> Mũi tên liền.
•
Công tác giả (Công tác ảo – Dummy): Dùng chỉ mối liên hệ
giữa các công tác, không đòi hỏi nguồn lực và thời gian.
Công tác giả -> Mũi tên chấm chấm.
•
Công tác chờ đợi: Là công tác không cần nguồn lực mà chỉ
cần thời gian. Công tác chờ đợi -> Mũi tên liền.
7
2. Diễn tả Sơ đồ Mạng của Dự án (tt)

Sơ đồ biểu diễn Công tác và Sự kiện, có 2 cách
•
Sơ đồ AOA (Activity On Arc network):
Công tác -> Mũi tên, Sự kiện -> Nút.
•
Sơ đồ AON (Activity On Node network):
Công tác -> Nút, Sự kiện -> Mũi tên.
1

C
Biến cố
Công việc C chỉ tiến hành sau khi
cả 2 công việc A và B kết thúc
Công việc
9
3. Phương pháp CPM, PERT (tt)
Phương pháp CPM (tt)
Các quy tắc khi xây dựng sơ đồ

Quy tắc 1: Mỗi hoạt động chỉ được biểu diễn bằng
1 mũi tên duy nhất trên sơ đồ.

Quy tắc 2: Không thể tồn tại 2 hoạt động được biểu
diễn bằng cùng các biến cố đầu và cuối.

Quy tắc 3: Để bảo đảm biểu diễn đúng mối QH
trước sau của các công việc
10
3. Phương pháp CPM, PERT (tt)
Phương pháp CPM (tt)

Các thông số của sơ đồ mạng:
•
Thời điểm sớm nhất để sự kiện xảy ra (EO, Earliest Occurrence of an
Event): Là thời điểm sớm nhất để cho sự kiện xảy ra khi tất cả các công
tác trước sự kiện đều hoàn thành.
•
Thời điểm sớm nhất để công tác bắt đầu (ES, Earliest Start of an
Activity): Là thời điểm sớm nhất để cho công tác bắt đầu. Đó là khoảng

LO
i
LS
jk
LS
ij
Thời điểm sớm nhất để sự kiện i xảy ra
Thời điểm muộn nhất để công tác ij bắt đầu
Thời điểm muộn nhất để sự kiện i xảy ra
Thời điểm sớm nhất để công tác ij bắt đầu
12
3. Phương pháp CPM, PERT (tt)
Phương pháp CPM (tt)
Cách xác định các thông số của sơ đồ mạng
(EO và ES, LO và LS)

Xác định EO và ES
EO
i
= ES
ij
Đi xuôi dòng sơ đồ mạng tính EO
j
tại các sự kiện thứ j
EO của sự kiện đầu tiên bằng 0: EO
1
= 0
Tại các sự kiện j có nhiều công tác đến, thì EO
j
tương

ij
Nếu có nhiều công tác xuất phát từ sự kiện i, ta có
}t{LOMin}{LSMinLO
ijjiji
−==
ji
14
3. Phương pháp CPM, PERT (tt)
Phương pháp CPM (tt)
Phân tích kết quả CPM

Qua Sơ đồ mạng, xác định được
•
Thời gian tối thiểu để hoàn thành dự án.
•
Thời gian dự trữ của các công tác F (Float).
•
Đường găng và các công tác găng.
15
3. Phương pháp CPM, PERT (tt)
Phương pháp CPM (tt)

Thời gian tối thiểu để hoàn thành dự án (= EO
cuối
)
Đây là thời điểm sớm nhất để sự kiện cuối cùng của dự án xảy ra.

Thời gian dự trữ của các công việc F (Float)
F là khoảng thời gian tối đa mà một công việc có thể chậm trễ so với kế
hoạch đã định mà không ảnh hưởng đến thời gian tối thiểu để hoàn thành dự

Ví dụ
Công việc giả
17
3. Phương pháp CPM, PERT (tt)
Phương pháp PERT
Phương pháp PERT
Sự không chắc chắn trong ước tính thời gian

3 loại thời gian ước tính
•
Các loại thời gian ước tính kết hợp với nhau để xác định thời
gian hoàn thành kỳ vọng t
e
(Expected Time) và phương sai σ.
•
Ba loại thời gian ước tính
•
Thời gian lạc quan a
•
Thời gian bi quan b
•
Thời gian thường xảy ra nhất m
17
ji
a ≤ m ≤ b
18
3. Phương pháp CPM, PERT (tt)
Phương pháp PERT (tt)

Thời gian kỳ vọng t

2
2
ab
−
=
σ
∑
=
22
ij
σσ
19
3. Phương pháp CPM, PERT (tt)
Phương pháp PERT (tt)
Các bước thực hiện phương pháp PERT
•
Vẽ sơ đồ mạng
•
Tính t
e
và σ
ij
2
của từng công tác
•
Dùng CPM với t
ij
= t
e
xác định công tác găng

6 7
0 0
2 2
2 10
3
13
8
0
1
A
C
B
D
E
F
5,
64/36
H
2,
4/ 36
3,
4/ 36
4,
16/36
4,
36/36
G
2,
4/36
4

22
a) Tính xác suất hoàn thành dự án
(1) D = 15 tuần
-> p = 0,5 = 50%.
(2) D = 14 tuần

-> p = 0,2843 = 28,43% (tra bảng phân phối chuẩn)
(3) D = 16 tuần

-> p = 0,7157 = 71,57%.
b) Tính thời gian hoàn thành dự án D
p = 35% -> Z = - 0.385

= 14.32 tuần
Ví dụ: (tt)
Z
D S
ij
=
−
=
−
=
∑
σ
2
15 15
1 76
0
,

,
,
D S Z
= + × = − ×
σ
15 0 385 176. .
23
END