Mạng PERT(Program Evaluation and Review Technique)

Mục Lục
1. Giới thiệu về mạng PERT.......................................................................................................2
2. Bài toán đặt ra.........................................................................................................................2
3. Phương pháp tính các thông số của công việc trong dự án..................................................3
4. Các nguyên tắc khi lập sơ đồ mạng lưới:..............................................................................3
5. Khái niệm đường Găng:.........................................................................................................7
6. Xét ví dụ cụ thể.......................................................................................................................8
7. Đánh giá độ phưc tạp, ưu nhược điểm của thuật toán:.......................................................11

1


Mạng PERT(Program Evaluation and Review Technique)
1. Giới thiệu về mạng PERT.
Sơ đồ mạng PERT (Kỹ thuật ước lượng và đánh giá chương trình, hay Kỹ
thuật ước lượng và kiểm tra dự án): là phương pháp áp dụng kết hợp giữa lý
thuyết xác suất thống kê (để ước tính thời lượng công việc trong các dự án mà
công việc có thời lượng không xác định trước), với dạng sơ đồ mạng đường
găng sử dụng lý thuyết đồ thị.
2. Bài toán đặt ra.
Dự án A có n công việc tên là 1, 2, …, n. Việc thứ i, i=1,..,n, có một số việc
tiên quyết, lưu trong danh sách TQi, tức là bắt buộc phải thực hiện xong các việc
trong TQi mới được thực hiện việc i. Dự án A được khởi động vào thời điểm t 0.
Tính thời điểm sớm nhất có thể hoàn thành dự án A và chỉ ra thời điểm bắt đầu
sớm nhất, muộn nhất có thể được đối với từng công việc và thời gian dự trữ của
từng công việc.
Muốn tính được điều đó, cần phải biết được các thông số thời gian sau:
+ Thời điểm sớm và muộn của từng sự kiện (hay thời gian sớm nhất và
muộn nhất đạt tới các sự kiện )

S i = P i - Xi
4. Các nguyên tắc khi lập sơ đồ mạng lưới:
Tất cả mỗi tên công việc từ trái đến phải về phái sơ đồ phát triển đến sự
kiện cuối cùng.
Trong sơ đồ mạng lưới không có chu trình khép kín hay chỗ giao nhau.

3


Mạng PERT(Program Evaluation and Review Technique)
Sự đánh số các sự kiện từ trên xuống dưới, từ trái qua phải và theo thứ tự
liên tiếp từ sự kiện đầu tiên đến sự kiện cuối cùng. Sự kiện ở đầu mũi tên mang
số lớn hơn sự kiện ở đuôi mũi tên. Chỉ đánh số các sự kiện có nhiều mũi tên
cùng đến khi các sự kiện ở đuôi những mũi tên này đã được đánh số.
Trong sơ đồ lớn nếu một nhóm công việc có liên hệ với nhau mà khi biểu
diễn trong sơ đồ mạng nó trở thành một mạng con gộp lại thành dạng công việc
thời gian thực hiện một công việc gộp lại lấy bằng khoảng thời gian dài nhất từ
sự kiện đầu tiên đến sự kiện cuối cùng.

Nếu một nhóm có công việc tính chất như nhau cùng làm song song thì
làm gộp chúng lại thành một việc duy nhất biểu thị bằng một cung.

Nếu công việc có tính chất khác nhau cùng làm song song có chung sự kiện
khởi công và kết thúc thì phải thêm các sự kiện phụ thuộc và công việc giả(sự
phụ thuộc)

4


Mạng PERT(Program Evaluation and Review Technique)



Mạng PERT(Program Evaluation and Review Technique)

5. Khái niệm đường Găng:
Đường Găng là đường đi từ sự kiện xuất phát đến sự kiện hoàn thành có
chiều dài lớn nhất.
Các công việc nằm trên đường Găng gọi là “Công việc Găng” (Critical
Task ). Thời gian của đường Găng cũng là thời gian hoàn thành dự án, hoặc là
thời gian xây dựng công trình. Trong sơ đồ mạng thường có một đường Găng
nhưng cũng có thể có nhiều đường Găng, thậm chí tất cả các công việc đều
Găng.
Việc tìm ra đường Găng trong sơ đồ mạng trên cơ sở tính toán, là một trong
những ưu điểm nổi bật của sơ đồ mạng.
Trên thực tế, đường Găng đóng vai trò hết sức quan trọng trong tiến độ
quản lý dự án vì: Trong bất kỳ lĩnh vực hoạt động nào, nhất là trong ngành điều
khiển tự động, nguyên tắc quan trọng để giải quyết tốt nhiệm vụ phức tạp là phải
nắm vững những công việc chủ yếu, quan trọng. Đường Găng bao gồm những
công việc chủ yếu, quan trọng đó. Trên thực tế, người có kinh nghiệm thường
biết được các công việc chủ yếu nhưng đó là những nhận biết cảm tính. Còn với
những dự án lớn, phức tạp, mới mẻ thì ngay cả chuyên gia nhiều kinh nghiệm
cũng không thể biết hết được. Trong quản lý dự án, xác định đường Găng trên
cơ sở tính toán, tức là tìm ra trong số những công việc phải hoàn thành, những
công việc nào quan trọng, là then chốt mà nếu hoàn thành được nó thì toàn bộ kế
hoạch dự án cũng được hoàn thành.

7


Mạng PERT(Program Evaluation and Review Technique)

4

4

Xây móng, tường

2,3

14

5

Làm mộc

3

20

6

Lắp cửa

4,5

4

7

Đổ trần – mái


Xây hàng rào, cổng

7,8

4

Việc TQ Thời gian

Bước 1: Thêm công việc bắt đầu (0) và công việc kết thúc (12) cho tất cả
các công viêc. Dựa vào công thức tính thời gian sớm nhất để bắt đầu công việc i
tính từ khi bắt đầu dự án: Xi = Max ( Xj + Tj ) với X1 = 0 ta có được bảng sau:

8


Mạng PERT(Program Evaluation and Review Technique)
TT

Công việc

TQ

f(i,j)

Biểu thức tính (max)

0

Khởi công


4

0+3

3

4

Xây móng, tường

2,3

14

3+6, 3+4

9

5

Làm mộc

3

20

3+4

7


5

9+14, 23+25

48

9

Quét vôi

6,8

3

27+4, 48+5

53

10

Lắp đặt thiết bị

6,8,9

5

27+4, 48+5, 53+3

56


Pj = Min (Pi – Ti) với P cuối cùng = Độ dài thời gian thực hiện dự án ta có được
bảng sau:
TT

Công việc

TQ

f(i)

Biểu thức tính (min)

0

Khởi công

1

Khảo sát

0

3

9-6, 9-4

3

2


53-4, 48-25, 53-5

23

5

Làm mộc

3

20

53-4

49

6

Lắp cửa

4,5

4

56-3, 61-5

53

7


Mạng PERT(Program Evaluation and Review Technique)
9

Quét vôi

6,8

3

61-5

56

10

Lắp đặt thiết bị

6,8,9

5

61-0

61

11

Hàng rào, cổng

7,8

nhất

KT muộn nhất
(p)

TT

Tên công việc

0

Khởi công

1

Khảo sát

0

3

0

0

0

3

2


4

Xây móng, tường

2,3

14

9

0

9

23

5

Làm mộc

3

20

29

22

29


23

48

8

Trát tường, trần

4,7

5

48

0

48

53

9

Quét vôi

6,8

3

53


57

4

57

61

12

Hoàn thiện

10,11

0

61

0

61

61

0

0

Vậy đường Găng gồm các công việc 1-2-4-7-8-9-10-12. Nếu dự trữ của sự

Điều đó trong thực tế chưa hẳn đã đúng. Bởi trên thực tế có rất nhiều dự án bị
chi phối bởi các điều kiện khách quan cũng như chủ quan, khiến cho thời gian
cũng như nhiều yếu tố khác của dự án không cố định. Ta chỉ có thể ước lượng nó
trong khoảng nào đó hợp lý. Đòi hỏi nhiều kỷ thuật để lập và sử dụng. Khi khối
lượng công việc của dự án lớn, việc lập sơ đồ này trở nên khá phức tạp và khó
quan sát. Vì vậy, phương pháp đường Găng được sử dụng nhiều trong giai đoạn
đầu của quản lý dự án vì tính hiệu quả, đơn giản, song giai đoạn sau người ta kết
hợp cả các phương pháp khác để quản lý dự án một cách chính xác hiệu quả
hơn.
11


Mạng PERT(Program Evaluation and Review Technique)

Tài liệu tham khảo
1. Các bài giảng trên lớp và giáo trình lưu hành nội bộ của thầy giáo
TS.Đào Thanh Tĩnh
2. Cẩm nang thuật toán (Tập 2) - Robert Sedgewick - NXB Khoa học &
Kỹ thuật, 2001
3. Trang wed http://vi.wikipedia.org/

12