Chương I ĐIỀU HÀNH DỰ ÁN BẰNG PHƯƠNG PHÁP
PERT-CMP
(Phương pháp sơ đồ mạng lưới)
Dự án (Project) là một tập hợp các hoạt động (Activity) liên quan với nhau và
phải được thực hiện theo một thứ tự nào đó cho đến khi hồn thành tồn bộ các hoạt
động. Hoạt động được hiểu như là một việc đòi hỏi thời gian, và nguyên liệu (Resource)
để hồn thành. Trước kia để điều hành dự án người ta thường dùng biểu đồ Gantt (Gantt
bar chart), là một đồ thị gồm các đường kẻ ngang, biểu thị điểm khởi công và kết thúc
hoạt động. Nhược điểm của biểu đồ là không xác định được quan hệ giữa các hoạt
động, nên không áp dụng được cho các dự án lớn (large-scale project), đòi hỏi đặt kế
hoạch (planning), điều hành thực hiện (scheduling) va kiểm tra (controlling) một cách
hệ thống và hiệu quả, thậm chí phải tối ưu hố hiệu quả (về thời gian và tiết kiệm nguyên
liệu). Vì vậy, gần như đồng thời vào năm 1956-1958, hai phương pháp kế hoạch, điều
hành và kiểm tra dự án đã ra đời. Phương pháp đường găng hoặc phương pháp đường
tới hạn (Critical path method, viết rắt là CPM) được E.I.du Pont de Nemous và công ty
xây dựng của ông đưa ra. Phương pháp thứ hai có tên là Kỹ thuật xem xét và đánh giá
dự án (Project evaluation and review technique, viết tắt là PERT) là kết quả nghiên cứa
của một công ty tư vấn theo đặt hàng của hải quân Mỹ, dùng để điều hành các hoạt
động nghiên cứu và phát triển chương trình tên lửa đối cực. Hai phương pháp được
hình thành độc lập nhưng rất giống nhau, cùng nhằm vào mục đích điều hành thời gian
là chính. Sự khác nhau chính là trong CPM thời gian ước lượng cho công việc, được coi
là tất định (Deterministic), còn trong PERT có thể là ngẫu nhiên (Probabilistic). Ngồi ra
CPM có tính đến quan hệ thời gian. Ngày nay, khi đã phát triển lên, hai phương pháp
được coi là một, dưới một tên chung là Phương pháp điều hành dự án PERT-CPM,
hoặc Phương pháp sơ đồ mạng lưới hoặc hệ thống kiểu PERT (PERT-type system). Nó
được dùng để thực hiện rất nhiều kiểu dự án, từ xây dựng, lập trình máy tính, sản xuất
phim đến vận động tranh cử chính trị hoặc các cuộc giải phẫu phức tạp.
Phương pháp điều hánh dự án PERT-CPM gồm ba pha (tức là ba khâu): kế
hoạch, điều hành và kiểm tra điều chỉnh. Pha kế hoạch có nội dung là lập một sơ đồ
mạng lưới (arrow network diagram hoặc arrow diagram), tương tự một đồ thị có hướng.
Pha này mở đầu bằng việc tách dự án thành nhiều hoạt động riêng và định thời gian hồn

hoạt động (8, 10) (nếu bỏ cung giả này thì thời điểm làm hai việc là độc lập).
Cung giả này là phục vụ cho qui tắc sơ đồ mạng lưới phải thể hiện đủ quan hệ
thứ tự cần có.
Nếu quan hệ thời gian có dạng: việc x
2
bắt đầu khi xong 1/3 việc x
1
, việc x
3
bắt
đầu khi xong một nửa x
1
, thì ta phải thêm các nút đánh dấu các biến cố xong 1/3x
1
và
xong 1/2x
1
đó như ở H1.2.
1
2
3
4
5
7
9
11
12
6
8
10

x
1
2
1
x
1
Hình 1.2
II. Phân tích các chỉ tiêu thời gian. Xác định đường căng.
Pha điều hành có nhiệm phân tích các chỉ tiêu thời gian và đưa ra các bảng và số
liệu cần thiết trên sơ đồ mạng lưới. Nếu trong dự án phải điều hành cả nguyên liệu
(hoặc nhân lực) thì phải xét cả các chỉ tiêu đó, ta sẽ nói đến ở mục sau.
II.1. Tính các thời điểm.
Chỉ tiêu ở đây là thời điểm sớm của biến cố (earliest time for an event) là thời
điểm biến cố xảy ra khi mọi hoạt động trước nó được bắt đầu sớm nhất có thể. Thời
điểm sớm của biến cố i thường ký hiệu là E
i
. Các E
i
được tính theo hướng tăng (forward
pass), tức là đi từ nút khởi công theo thứ tự tăng của nút i. Như vậy với nút khởi công 1
thì E
1
= 0. Đến nút 2 trong sơ đồ H1.1 thì E
2
rõ ràng bằng 2 vì biến cố hồn thành hoạt
động (1, 2) phải là E
1
+ t
12
, ở đây t

i
rõ ràng đây là
thời điểm mọi hoạt động đó vừa xong cả, tức là phải lấy maximum của các tổng. Chẳng
hạn
E
7
= max {E
4
+ t
45
,E
5
+ t
57
} = max {16 + 7, 20 + 5} = 25,
E
8
= max {E
5
+ t
58
,E
6
+ t
68
} = max {20 + 0, 22 + 7} = 29
Tổng quát, công thức tính E
i
cho mọi trường hợp là :
E

điểm muộn là :
L
j
=L
i
- t
ji
,
Tức là thời điểm muộn của nút ngay sau nó trừ đi thời gian thực hiện hoạt động nối hai
nút. Các biến cố 12, 11, 10, 8, 7, 6, 3, 2 và 1 ở H.1.1 là trường hợp này. Nếu có nhiều
cung ra khỏi biến cố, thì theo định nghĩa ta có :
L
j
=
i
}t-{L min
jii
Ở đây min theo các nút i ngay sau j và t
ji
là thời gian thực hiện hoạt động nối (j, i). Các
nút 9, 5, 4 là ở trường hợp này, chẳng hạn :
L
9
= min {L
11
– t
9 11
, L
12
– t

4
4
4
(44, 44)
6
0
2
(38, 42)
(29, 33)
(22, 26)
(0, 0)
(2, 2)
(6, 6)
(16, 16)
(20, 20)
(25, 25)
(33, 33)
1
4
5
(38, 38)
2
4
10
4
5
8
Trong thời gian dự trữ (slack hoặc float) của một biến có là hiệu thời điểm muộn và thời
điểm sớm của nó : d
i

ij
, nhưng với giả thiết là mọi
hoạt động đều bắt đầu sớm có thể, vậy :
FF
ij
= E
j
– E
i
– t
ij
.
Trên sơ đồ mạng lưới thì d
i
là hiệu hai số trong ngoặc ở nút i, thường được ghi bằng số
trong ô vuông cạnh nút. Thời gian dự trữ chung của hoạt động TF
ij
được ghi trong ô
vuông cạnh ở mỗi cung. Còn thời gian dự trữ độc lập của hoạt động FF
ij
ít quan trọng
hơn, thường không ghi, xem H.1.3.
II.3. Đường găng. (đường tới hạn)
Các hoạt động có thời gian dự trữ chung bằng 0 cần được chú ý đặc biệt vì trì
hỗn nó sẽ ảnh hưởng đến thời gian kết thúc dự án. Từ đó có :
Định nghĩa II.3.1. Đường găng hoặc đường tới hạn (critical path) là một đường đi
từ nút khởi công đến nút kết thúc mà mọi hoạt động trên đường đều có thời gian dự trữ
chung bằng 0. (Chẳng hạn trên H.1.3 có một đường găng là 1 –> 2 –> 3 –> 4 –>5 –> 7
–> 9 –> 12 –> 13 ) hoạt động (i, j có TF
ij

gian dự trữ của các biến cố 6, 8 và 10 đều thay từ 4 thành 0. Lúc này đường 1 –> 2 –
> 3 –> 4 –> 6 –> 8 –> 10 –> 13 là đường găng thứ hai.
Các chỉ tiêu thời gian của dự án ở H.1.3 được ghi vào bảng 1.1
Biến cố Thời
điểm
Thời
điểm
Thời
gian dự
Hoạt
động
Thời gian
dự trữ
Hình 1.3
sớm muộn trữ chung
1 0 0 0 (1, 2) 0
2 2 2 0 (2, 3) 0
3 6 6 0 (3, 4) 0
4 16 16 0 (4, 5) 0
5 20 20 0 (4, 6) 4
6 22 26 4 (4, 7) 2
7 25 25 0 (5, 7) 0
8 29 33 4 (6, 8) 4
9 33 33 0 (7, 9) 0
10 38 42 4 (8, 10) 4
11 37 38 1 (9, 11) 1
12 38 38 0 (9, 12) 0
13 44 44 0 (10, 13) 4
(12, 13) 0
Bảng1.1. Chỉ tiêu thời gian xây nhà

≤ E
j
, LS
ij
≥ L
i
. Thật vậy, ta có
E
j
=
k
max
{E
k
+ t
kj
} ≥ E
i
+t
ij
= EC
ij
,
Vì i cũng là một trong các nút k ngay trước j. Bất đẳng thức thứ hai tương tự.
Thời gian dự trữ của một đường đi (total float of a path) P từ nút khởi công đến
nút kết thúc, ký hiệu TF
p
, là thời gian có thể kéo dài thêm các hoạt động trên đường
này mà không ảnh hưởng đến thời điểm hồn thành công trình, tức là
TP =