Điều hành dự án bằng phương pháp PERT-PCM và ứng dụng giải bài tốn lập lịch thi công công trình.doc

Chương mở đầu

GIỚI THIỆU CHUNG VỀ NHIỆM VỤ

Đề tài “Điều hành dự án bằng phương pháp PERT-PCM và ứng dụng giải

bài tốn lập lịch thi công công trình”, bao gồm

- Tìm hiểu phương pháp PERT-PCM (phương pháp sơ đồ mạng lưới).

- Ứng dụng giải bài tốn lập lịch thi công công trình.

+ Lưu trữ lịch thi công các dự án

+ Cho biết thới gian bắt đầu một dự án và thời gian kết thúc dự án

+ Thêm một số hạng mục khi dự án đang được thi công

+ Bỏ một số hạng mục khi dự án đang thi công

+ Đưa ra lịch thi công các hạng mục tối ưu nhất

Trang 1

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 thành chúng. Trong mạng, mỗi cung có hướng biểu diễn hoạt động và

cả sơ đồ mạng biểu thị mối quan hệ giữa các hoạt động. Mỗi nút biểu thị một biến

cố hoặc sự kiện (event), đánh dấu hồn thành một số hoạt động (activity) là các cung

đi vào nút, và bắt đầu các hoạt động ứng với các cung ra khỏi nút.

Pha điều hành (scheduling phase) có nhiệm vụ xây dựng biểu đồ thời gian, chỉ

rõ thời điểm bắt đầu và kết thúc của mỗi hoạt động và mối quan hệ giữa các hoạt

động. Nói riêng, điều quan trọng là phải tính chính xác các hoạt động tới hạn, tức là

găng (critical), cần chú ý đặc biệt khi thực hiện, để tồn bộ dự án được hồn thành

đúng hạn.

Trang 2

Pha kiểm tra bao gồm việc sử dụng sơ đồ mạng lưới, và biểu đồ thời gian để

theo dõi và báo cáo định kì tiến triển của dự án. Nếu cần thì phải phân tích lại và xác

định sơ đồ mới cho phần dự án còn lại.

I. Lập sơ đồ mạng lưới

Như trên đã nói, pha đầu của phương pháp PERT-CPM là lập kế hoạch thể hiện

ở một sơ đồ mạng lưới, biểu diễn như một đồ thị có hướng. Hãy xét một dự án xây

dựng một tồ nhà. Việc tách dự án thành các hoạt động như đào đất, xây móng, xây

tường thô, lợp mái, đặt đường dây điện … là do kiến trúc sư hoặc kỹ sư xây dựng

làm. Dựa vào đó, người quản lý dự án lập được sơ đồ mạng lưới như H.1.1. Các số

bên cạnh cung là thời gian thực hiện hoạt động đó.

Qua sơ đồ mạng lưới H.1.1 ta thấy rõ mối quan hệ giữa các hoạt động về thời

gian. Chẳng hạn hoạt động (6, 8) là trát ngồi-phải sau (4, 6) là lợp mái, nhưng độc

lập với (5, 7) là chỉnh tường trong. Cũng vậy (4, 7) độc lập với (4, 5) và (5, 7). Ở

đây có hai hoạt động giả (dummmy activity) với thời gian để thực hiện bằng 0 được

đưa vào để đảm bảo qui tắc sơ đồ.

Cung giả (11, 12), ký hiệu bởi đường đứt đoạn, đưa vào để đảm bảo qui tắc

không có hai hoạt động cùng biến cố bắt đầu và kết thúc, tức là không có 2 cung có

cùng gốc và ngọn (tức là đồ thị đơn). Việc sơn tường trong và làm sàn có cùng biến

cố dầu là nút 9, tức là biến cố lát ván tường xong, và biến cố cuối là nút 12 (làm sàn

và sơn tường xong, bắt đầu hồn thiện trong). Do đó ta phải thêm nút 11 là biến cố

giả và cung giả (11, 12).

Cung giả (5, 8) để chỉ rằng hoạt động (4, 5) phải hồn thành trước khi bắt đầu

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 x2 bắt đầu khi xong 1/3 việc x1, việc x3 bắt

đầu khi xong một nửa x1, thì ta phải thêm các nút đánh dấu các biến cố xong 1/3x1

và xong 1/2x1 đó như ở H1.2.

Khởi công

2 Đào móng

4 Xây móng

10 Xây thô

6Lợp mái

Trang 3

1

2

3

4

5

7

9

1

1

1

2

6

8

1

0

1

3

4 Chỉnh thẳng tường ngồi

Đặt dây điện 7

7 Trát ngồi

5 Chỉnh thẳng tường trong

9 Sơn ngồi

8 Ép ván lát tường

Làm sàn 4 5 Sơn tường Hồn thiện ngồi 2

0 Hồn thiện trong

6

Kết thúc

Hình 1.1

Tóm lại: Sơ đồ mạng lưới phải là một đồ thị có hướng, đơn, liên thông,

không có khuyên (tức là cung có gốc và ngọn cùng là một nút), không có chu trình

có hướng (directed cycle), có nút khởi công và nút kết thúc.

2

1

x1

3

1

x1

2

1

x1

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à Ei. Các Ei đượ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ì E1 = 0. Đến nút 2 trong sơ đồ H1.1 thì E2 rõ ràng bằng 2 vì biến cố

hồn thành hoạt động (1, 2) phải là E1 + t12, ở đây t12 là thời gian thực hiện hoạt động

(1, 2). Việc tính E3, E4, E5, E6, E9, E10 và E11 cũng tương tự vì các nút tương ứng chỉ

có một cung vào, khi đó:

Ei = Ej + tji

Ở đây j là nút ngay trước i. Chẳng hạn E6 + t46 = 16 + 6 = 22. Nếu có nhiều cung

vào nút, tức là nhiều hoạt động kết thúc tại biến cố, thì từ định nghĩa Ei rõ ràng đây

Trang 4

X2

X3

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

E7 = max {E4 + t45,E5 + t57} = max {16 + 7, 20 + 5} = 25,

E8 = max {E5 + t58,E6 + t68} = max {20 + 0, 22 + 7} = 29

Tổng quát, công thức tính Ei cho mọi trường hợp là :

Ei = maxmax {Ej + tji},

j

ở đây j là các nút ngay trước i, tức là có cung nối tới i. Các Ei được ghi ở H.1.3 là số

đầu trong ngoặc ở mỗi nút.

Thời điểm muộn (latest time) của biến cố j là thời điểm muộn nhất mọi cung đi

vào biến cố j đều hồn thành mà không làm thay đổi thời điểm kết thúc dự án sớm

nhất có thể, ký hiệu là Lj. Đối lại với Ej, các Lj được tính theo hướng lùi (backward

pass), tức là đi từ nút kết thúc. Theo định nghĩa, ở nút kết thúc thì En = Ln, ở thí dụ

H.1.1 là E13 = L13 = 44. nếu ở biến cố chỉ có một cung ra, tức là một hoạt động được

bắt đầu thì, thời điểm muộn là :

Lj =Li - tji,

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ó :

Lj = i

min {L - t } i ji

Ở đây min theo các

nút i ngay sau j và tji

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 :

L9 = min {L11 – t9 11,

L12 – t9 12} = min (38 –

4, 38 - 5) = 33

Hãy chú ý sự ‘’đối

xứng ‘‘ của quá trình

tính Ei và Lj. Các Lj

được ghi ở số thứ 2

trong ngoặc ở mỗi nút

trong H.1.3.

II.2. Tính thời gian

dự trữ.

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

Trang 5

1

2

3

4

5

7

9

1

1

1

2

6

8

1

0

1

3

1

2

4

4

4

4

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