Luận văn thạc sĩ Công nghệ thông tin: Bài toán điều khiển tiến độ và phân phối tài nguyên trong quản lý dự án

Dinh nghĩa sơ đồ mạng : Là một hệ thống các công việc được sắp xếp theomột trình tự nhất định kể từ khi bắt đầu cho đến khi kết thúc một quá trình để tạonên một sản phẩm nào đó.Trong một

NGUYEN THỊ THAM

BAI TOAN DIEU KHIEN TIEN DO

VA PHAN PHOI TAI NGUYEN

TRONG QUAN LÝ DỰ ÁN

Chuyên ngành: KHOA HỌC MÁY TÍNH

Mã số: 60 48 01

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC:

TS NGUYEN THỊ HONG MINH

HA NOI - 2008

TRANG PHU BÌA

MUC LUC

DANH MUC CAC KY HIEU, CAC CHU VIET TA’

DANH MỤC CAC BANG

DANH MUC CAC HINH VE, DO THI

MO ĐÀU _CHƯƠNG 1 TONG QUAN VE LÝ THUYET DO THỊ VÀ SO DO MẠNG 31.1 Tổng quan về lý thuyết đồ thị

1.1.1 Khái niệm và định nghĩa

1.1.2 Biểu diễn đồ thi

1.1.3 Các thuật toán tìm đường đi trong,

1.2 Phương pháp sơ đồ mạng

1.2 1 Giới thiệu chung

1.2.2 Một số khái niệm trên sơ đồ mạng

1.2.3 Phương pháp đường găng.

1.2.3.1 Giới thiệu chung về phương pháp đường gin;

1.2.3.2 Các bước tính toán trong phương „P CPM 1.2.3.3 Ví dụ 5

1.2.4 Phương pháp ước lượng đánh giá

-1.2.4.1 Khái niệm cơ bản về phương pháp PERT

1.2.4.2 Ước lượng thời gian hoàn thành công việc

1.2.4.3 Các thông số thời gian trong sơ đồ1.2.4.4 Tính xác suất hoàn thành công việc 1.3 Ứng dụng sơ đồ mạng trong quản lí tié

1.3.1 Sơ đồ mạng trên trục thời gian

1.3.2 Đưa sơ đồ mạng lên trục thời gia

1.3.3 Chuyển sơ đồ mạng sang sơ đồ ngang

1.3.4 Quy tắc lập sơ đồ mang sự kié

CHUONG 2 CÁC BÀI TOÁN TRONG QUAN LÝ Di

2.1 Bài toán lập và điều khién tiến độ,

2.1.1 Sơ đồ mạng biểu diễn tiến lộ dự án

2.1.2 Thuật toán cho bài toán lập và điêu khiên tiên di

2.2 Bài toán phân phối tài nguyên nhân ly

2.2.1 Giới thiệu chung

2.2.2 Biểu đồ tài nguyên và các quy tắc ưu tiên

2.2.3 Các phương pháp phân phối tài nguyên

2.2.4 Cân đối tai nguyên

2.2.4.1 Thuật toán đưa ra mức tài nguyên ban dau2.2.4.2 Thuật toán cân đối tài nguyên

2.3 Bài toán tối ưu chỉ phí và giá thành

2.3.1 Giới thiệu chung

2.3.2 Thời gian và giá thành

2.3.3 Chỉ phí trực tiếp, chi phí gián tié

2.3.4 Giá thành toàn bộ dự án

2.3.5 Cân đối giá thành

2.3.6 Thuật toán tôi ưu chi phí và gia than!

CHƯƠNG 3 CHƯƠNG TRÌNH QUẢN LÝ DỰ ÁN

3 1.Phân tích cấu trúc dữ liệu của chương trình

3 2.Các form giao diện

3 3.Một số hàm chức năng cơ bản của chương trình.KẾT LUẬN

TÀI LIỆU THAM KHẢO

DANH MỤC CAC KÝ HIEU, CAC CHỮ VIET TAT

CPM: Critical Path Method — Phương pháp đường găng

PD: Project duration - Khoảng thời gian mong muốn của dự án

PERT:Program Evaluation and Review Technical - Kỹ thuật ước lượng và đánh giá

DANH MỤC CÁC BẢNG

Bang 1.1 Các bước gan nhãn, tìm đường đi ngắn nhất từ đỉnh 1

Bảng 2.1 Ví dụ - các công việc của một dự án

Bang 2.2 Bảng các công việc và thông số về thời gian và chỉ phí.

Hình 1.7 Tiến độ lắp ghép khung nha sau khi thêm các mũi tên và vòng tròn.

Hình 1.8 Sơ đồ mạng thẻ hiện tiến độ lắp ghép khung nhà.

Hình 1.9 Sơ đồ mạng ban da

Hình 1.10 Sơ đề lạng sau khi đã tính các giá trị khởi sớm.

Hình 1.11 Sơ đề mang sau khi đã tính các giá trị khởi muộn

Hình 1.12 Sơ đồ mạng sau khi đã xác định đường găng

Hình 1.13 Ham phân bó xác suất của thời gian sự kiện

Hình 1.14 Đường cong chuân

Hình 1.15 Ví dụ minh họa - Sơ đô mạng ban đầu .

Hình 2.1(a) Biểu đồ sử dụng tài nguyên tốt es Hình 2.1(b) Biểu đồ sử dung tai nguyên chấp nhận được

Hình 2.1(c) Biểu đồ sử dụng tài nguyên không tốt

Hình 2.2 Biểu đồ tài nguyên.

Hình 2.3(a) SDM ban đầu theo thời gian sớm nhát và biéu đồ nhân lực ban đầu

Hình 2.3(b) Biéu đồ phân phối tài nguyên theo phương pháp song song và quy tắc ưu tiên dự trữ nhỏ nhất 55

Hình 2.3(c) Biêu đồ phân phối tài nguyên theo phương pháp nối tiếp và quy tắc ưu tiên dự trữ nhỏ nhất 56

Hình 2.4 Đồ thị biểu diễn môi quan hệ giữa chi phí thời gian và giá thanh Ề 62 Hình 2.5 Đồ thị chi phí gián tiếp

Hình 2.6 Đồ thị chỉ phí trực tiếp

Hình 2.7 Rút ngắn thời gian bằng phương pháp sơ đô mạng

Hình 2.8 Sơ đồ mạng sau khi rút ngắn công việc E

Hình 3.1 Biểu đồ công việc và tài nguyên ban đầu ¬ TS

Hình 3.2 Biểu đồ cân đối tài nguyên với mức tài nguyên MTN =18 cho toàn bộ dự án TỐ

Hình 3.3 Biểu đồ cân đối tài nguyên bắt đầu từ thời điểm 30, MTN = 17

"vị

Hình 3.4 Một số phương án khác

hiện nhiều công đoạn khác nhau, ví dụ: các công đoạn trong một dây chuyền sảnxuất; các công đoạn dé hoàn thành một công trình xây dựng, một công trình khoahọc hay một chiến dịch quảng bá sản pham , những việc lớn như vậy được gọi

chung là đ án Một dự án bao gồm nhiều công việc Muốn thực hiện dự án một

cách khoa học, đúng tiến độ và đạt chất lượng cao chúng ta cần phải biết chính xác:

- Dự án cần bao nhiêu thời gian đê hoàn thành?

- Mỗi công việc của dự án cần bắt đầu và kết thúc vào lúc nào dé đảm bảo tiến

độ của dự án Nếu công việc có thê bị kéo dài thì có thê kéo dài bao nhiêu thờigian dé vẫn đảm bảo kế hoạch?

-_ Những công việc nao là trọng tâm, cần tập trung sự chỉ đạo, đầu tư nguồn lực

trong toàn bộ dự án?

- Tài nguyên, bao gồm nguồn nhân công, thiết bị phân phối cho từng công

việc và toàn bộ dự án là bao nhiêu? Việc điều phối như thé nào dé đảm bảo sự

tối ưu giữa chỉ phí và giá thành?

Dé giải quyết các câu tra lời và tính toán cho những yếu tố trên, một phương.pháp đã được áp dụng phổ biến là phương pháp sơ đô mạng Sơ đồ mạng bắt nguồn

từ lí thuyết đồ thị, nên còn được gọi là phương pháp Graph, là một công cụ toán

học hiện đại cho phép diễn tả kế hoạch tiến độ của các dự án thông qua mối quan

giữa các công việc Sơ đồ mạng được sử dụng đề lập kế hoạch và điều khién tiền độtriển khai các dự án, cung cấp khả năng hỗ trợ điều phối việc sử dụng tai nguyên

trong toàn bộ dự án.

Khi chưa có những phần mềm chuyên dụng cho quản lí dự án thì những ngườiquản lí du án phải thực hiện các kĩ thuật tính toán thủ công, điều này có thể gây khókhăn và không hiệu quả trong quá trình quản lí dự án Đặc biệt khi dự án có những

vướng mắc, điều chỉnh dẫn đến những thay đổi về mặt thời gian

đẻo, linh hoạt và đạt hiệu qua cao Đề tài “Bai todn điều khiển tiến độ và phân phốitài nguyên trong quản lý dự án ” nằm trong hướng nghiên cứu này với các mục tiêu:

- _ Nghiên cứu những nền tang lí thuyết cần thiết về sơ đồ mạng, lí thuyết đồthi, làm cơ sở cho việc phân tích và đưa ra các thuật toán để giải quyếtcác bài toán trong quản dự án như: Bai todn lập và điều khiển tiến độ; Bàitoán phân phối tài nguyên; Bài toán cân đổi chỉ phí và giá thành

- Xây dựng một hệ thống thử nghiệm hỗ trợ quản lí dự án, áp dụng cho các

dự án xây dựng.

Luận văn bao gồm các phần chính sau:

Chương 1: Tổng quan về If thuyết dé thị và sơ đồ mạng Chương này sẽ trìnhbày một số kiến thức tổng quan về lý thuyết đồ thị, một số khái niệm và thuật toán

cơ bản trên dé thị Một số phương pháp sơ đồ mạng và ứng dụng của hai phươngpháp sơ đồ mạng phổ biến là CPM (Critical Path Method) và PERT (Project

Evaluation and Review Technique) trong các bài toán quản lý dự án.

Chương 2: Các bài toán trong quản lý dự án Chương này tập trung vào việc

giải quyết ba bài toán cơ bản trong quan lý dự án gồm: Bai todn lập và điều khiểntiễn độ; Bài toán phân phối tài nguyên; Bài toán cân đối chỉ phí và giá thành Mỗibài toán sẽ bao gồm các nội dung : đặt bài toán, phân tích các yếu tố liên quan vànêu các thuật toán tương ứng đề giải quyết

Chương 3: Chương trình quản lý dự án Chương này triển khai chương trình

mô phỏng hệ thống hỗ trợ công việc trong quản lý dự án, tập trung vào hai bài toánquản lý tiến độ và quản lý tài nguyên Chương trình có thé đưa ra nhiều tùy chọn dénhà quản lý quyết định cho phù hợp với từng tình huống cụ thể trong quá trình thực

hiện dự án.

1.1 Tổng quan về lý thuyết đồ thị

1.1.1 Khái niệm và định nghĩa

Đồ thị G là một cặp (V,E), trong đó V là tập đỉnh và E = {(x,y) | x, yeV} là

tập cung (cạnh) Về thực chất, đồ thị là một tập hợp các đối tượng được biêu diễn

bằng các đỉnh và giữa các đỉnh có một quan hệ biểu diễn bằng các cạnh

Đồ thị thường được ký hiệu là G hay G(V,E)

Hình 1.2 Đường đi œ

Ta có: 1a2b3elg5, là một đường đi trong dé thị G,(V,E) trong hình 1.1 xuấtphát từ vp = 1 đến vạ = 5

Chu trình: Là một đường đi khép kin, tức là đỉnh cuối vạ = vo của đường đi

Một chu trình đơn là chu trình không có đỉnh lặp lại.

Đồ thị G gọi là dé thj liên thông nêu với cặp đỉnh (u, v) bất kỳ đều tồn tạimột đường đi nối hai đỉnh này Đồ thị G không liên thông thì mỗi đồ thị con liênthông cực đại của nó được gọi là một thành phần liên thông

Đồ thị có trọng số: Ứng với mỗi cạnh ta gán cho một số (nguyên hay thực)không âm w mang thông tin nào đó có liên quan đến cạnh gọi là trọng số của cạnh

đó Dé thị mà mọi cạnh đều có trọng số gọi là đồ thị có trong số (Weitghted Graph).Trọng số có thé là quãng đường trên bản đồ giao thông, cước phí vận tải trên đường

đó, thông lượng trên mạng thông tin, Trong đồ thị có trọng số, độ dài đường điđược định nghĩa là tổng trọng số của các cạnh trên đường đi đó

Dé thị có hướng: Là đồ thị mà mọi cạnh của nó đều xác định thứ tự các đỉnh

kể (khi đó các cạnh còn được gọi là các cung) Hình 1.3 biểu diễn dé thị có hướng

(a) GAVE) (b) G3(V,E)

Hình 1.3 Dé thị có hướng(a) Không có trọng số; (b) Có trọng số

nếu không có chú ý gì thêm, ta hiểu là các đồ thị có hướng Khi nói đến cung, tahiểu đó là cung trong đồ thị có hướng.

1.1.2 Biểu diễn đồ thị

Để có thể giải các bài toán liên quan đến đồ thị trên máy tính, chúng ta cầnphải có các phương pháp dé biểu diễn đồ thị Các phương pháp biểu diễn đồ thị haychính là các cầu trúc dữ liệu mô tả đồ thị thường được sử dụng là:

- Biểu diễn bằng ma trận kè

- _ Biểu diễn bằng danh sách kề

-_ Biểu diễn bằng danh sách cung (cạnh)

Biểu diễn bằng ma trận kè

Để biểu diễn đồ thị có hướng, có trọng số G với n đỉnh ta sử dụng một ma

trận A cỡ nxn với các phân tử (aj) của ma trận được xác định như sau:

w, nếu có cung (i, j) với trọng số wy

a= œ nếu không có cung (i,j)

Ví dụ: Ma trận ké biểu diễn đồ thị Ga(V,E) với 5 đỉnh trong Hình 1.3 như

Sau :

> 8 8 a8 8 ny 8 8 8 œ 8 œ8 8 8 8 8 BN 8 œ8 8 8

Phương pháp biéu diễn đồ thi bằng ma trận kể có ưu nhược điểm sau:

Ưu điểm: Các phép toán cơ sở của đồ thị đều cho phép dễ dàng, thuận tiệncho việc truy nhập các cung, các đỉnh kề Cho cặp đỉnh (i, j) bat kỳ thì xác định

đỉnh, tức là ma trận kể sẽ thưa, có nhiều phần tử bằng œ, khi đó tuy có ít dit liệu cần

lưu trữ nhưng ta vẫn phải lưu cả một ma trận kích thước lớn.

Biểu diễn đồ thị bằng danh sách kè

Để biểu diễn đồ thị bằng danh sách kể có thé thay n dòng của ma tran bằng ndanh sách móc nối Nút đầu của mỗi danh sách là đỉnh được xét, theo sau là cácđỉnh kể với nó và trọng số của cung tương ứng

Ví dụ: Danh sách kể biểu diễn đồ thị G3(V,E) với 5 đỉnh trong Hình 1.3 như

Sau :

1| L {2 [8 >[4 [6] >[ NIL 2] LÌ {4 [2 | >[ NIL

Cấu trúc mỗi nút của danh sách có thê được khai báo như sau:

struct Node

{ int Index;

float weight Node *next;

he

Biểu diễn một đồ thị có n đỉnh là một mảng các danh sách liên kết G: NodeG[n];

Biểu diễn đồ thị bằng danh sách cung

Trong trường hợp đồ thị thưa có n đỉnh, m cạnh (đồ thị có số cung thoả mãnbất đẳng thức: m<6n), người ta thường biểu diễn đồ thị dưới dang danh sách cung.Trong cách này, ta sẽ lưu trữ danh sách tất cả các cung của đồ thị có hướng Mỗicung e = (u, v) của đồ thị sẽ tương ứng với hai biến Đầu và Cuối (và trọng số nếu có).Khi đó dé lưu trữ đồ thị ta cần 2m don vị nhớ Nhược điểm của cách biéu diễn nay

là để xác định những đỉnh nào kể với một đỉnh cho trước, ta phải làm m phép sosánh khi đuyệt qua tất cả các cạnh của đồ thị

Ví dụ: Danh sách cung của dé thị G;(V, E)

Ví ụ đồ thị biểu diễn khoảng cách giữa một số tỉnh/thành phó của Việt Nam:Trọng số ghi trên mỗi cạnh là khoảng cách tính bằng km

Một thuật toán được áp dụng tương đối phổ biến dé giải bài toán tìm đường

đi do Dijkstra đề xuất năm 1959 gọi là thuật toán Dijkstra mà chúng tôi sẽ trình bàytrong mục 1.1.1.1 sau đây Trường hợp riêng của bài toán tìm đường đi khi đồ thịkhông có chu trình thì thuật toán Dijkstra có thể được cải tiến để độ phức tạp chỉcòn O(n) - với n là số đỉnh của đồ thị, thuật toán này được trình bày trong mục1.1.1.2.

Bài toán đặt ra là:

Xuất phát từ đỉnh 1, chúng ta cần tìm đường đi ngắn nhất tới các đỉnh còn

lại?

Thuật toán Dijkstra giải quyết bài toán trên, được xây dựng trên ý tưởng sau:

Cho đỉnh s e V, tìm đường đi ngắn nhất từ s tới mọi đỉnh v e V Thuật toán

thực hiện việc gán nhãn d[v] tạm thời cho mỗi đỉnh v dé lưu đường đi ngắn nhất từđỉnh s tới v trong mỗi bước, sau đó thực hiện việc giảm giá trị của nhãn đến khikhông thể giảm được nữa thì d[v] chính là đường đi ngắn nhất từ s đến đỉnh v

Bước 1: Gan nhãn tạm thời cho mọi đỉnh veV là trong số của cạnh (s, v), ký

hiệu là d[v]: d[v] = a[s, v], d[s] = 0 Gọi T là tập chứa các đỉnh được gán nhãn tam

thời: T = V\s.

Bước 2: Tìm u e T: d[u] = min {d[z], z e T}

Thực hiện giảm giá trị nhãn d[v] của mỗi đỉnh v eV cho đến khi không thểgiảm được nữa theo quy tắc: Nếu từ đỉnh u eT có cung đi vào đỉnh v mà có d[u] +

a[u, v] < d[v] thì ta thay nhãn d[v] của đỉnh v bởi giá trị nhỏ hơn là d[u] + a[u, v] và

ghi nhận đỉnh trước v trong đường đi ngắn nhất từ s tới v là u: Truoc[v] =u

Bước 3: Loại đỉnh u ra khỏi T (u đã được gán nhãn có định sau bước 2).

Bước 4: Nếu T # ©, lặp lại bước 2, ngược lại, dừng

Thuật toán Dijkstra có thể được trình bày dưới dạng giả mã (pseudo - code)như sau:

THUẬT TOÁN: DIJKSTRA

Input: Đồ thị (V, E) có hướng, n đỉnh, với ma trận trọng số biểu diễn A =(ajnxn aj> 0 V ij e V; s € V là đỉnh xuất phát

Output: Khoảch cách ngắn nhất từ đỉnh s đến tat cả các đỉnh còn lại là d[v],

ve V Truoc[v] ghi lại đỉnh đi trước v trong đường đi ngắn nhất từ s đến v

Truoc[v] = uy

}

}//while

}//Dijkstra

Vi dụ: Với đồ thị G trong Hình 1.5, bài toán tìm đường đi ngắn nhất từ đỉnh

1 tới các đỉnh còn lại được tính toán theo thuật toán Dijkstra có các kết quả trìnhbày theo bảng dưới đây Quy ước mỗi ô trong bảng là 2 thành phần của nhãn theo

thứ tự d[v], Truoc[v], trong đó d[v] là nhãn ghi tại đỉnh v ghi khoảng cách từ

đỉnh xuất phát I tới đỉnh v tại bước đang xét, Truoc[v] là đỉnh trước v trongđường đi ngắn nhất từ 1 đến v Đỉnh được đánh dấu * là đỉnh được chon dé cố định

nhãn ở bước lặp dang xét, nhãn của nó không biến đổi ở các bước tiếp theo, vì thé tađánh dấu -.

Bang 1.1 Các bước gan nhãn, tìm đường đi ngắn nhất từ đỉnh 1

-Như vậy: khoảng cách từ đỉnh 1 đến đỉnh 6 là 5, dựa vào giá trị của

Truoc [v], ta tìm ra được đường di từ đỉnh | tới đỉnh 6 là: 1 -> 2 -> 4 -> 3 -> 6.

Chú ý: Nêu chỉ cần tìm đường đi ngắn nhất từ đỉnh s đến một đỉnh t nào đóthì ta có thể kết thúc thuật toán khi đỉnh t trở thành đỉnh có nhãn cố định

1.1.3.2 Thuật toán tìm đường trong đồ thị không có chu trình

Một trường hợp riêng khác của bài toán tìm đường đi ngắn nhất, đó là khi đồthị không có chu trình Để xây dựng thuật toán cho các đồ thị đạng này chúng ta

dựa trên định lý sau:

Dinh lý: Gia sử đồ thị G là đồ thị không có chu trình Khi đó các đỉnh của

nó có thể đánh số sao cho mỗi cung của đồ thị chỉ hướng từ đỉnh có chỉ số nhỏ hơnđến đỉnh có chỉ số lớn hơn, nghĩa là mỗi cung của nó có thé biểu diễn dưới dạng

([i], v[j]) trong do i<j.

Dinh lý được chứng minh đơn giản theo ([3], trang 227 —> 228).

Theo định lý này, khi xét đồ thị không có chu trình ta có thể giả thiết cácđỉnh của nó được đánh số sao cho mỗi cung chỉ đi từ đỉnh có chỉ số nhỏ đến đỉnh cóchỉ số lớn hơn Thuật toán tìm đường đi ngắn nhất trên đồ thị không có chu trình

được mô tả như sau:

Thuật toán: Tìm đường đi ngắn nhất từ đỉnh nguồn đến tất cả các đỉnh cònlại trên đồ thị không có chu trình:

Input: Đồ thị G = (V, E), trong đó V={v[1], v[2], , v[n]}, mỗicung (v[i], v[j]) e E, ta có i<j, A = (aj) là ma trận trọng số, aj>0 Vij e V

Output: Khoảng cách từ v[1] đến tất cả các đỉnh còn lại được ghi trong

(Project Evaluation and Review Technique) sẽ trình bày ở các chương sau.

1.2 Phương pháp sơ đồ mạng

1.2.1 Giới thiệu chung

Sơ đồ mạng bắt nguồn từ lý thuyết dé thị nên còn được gọi là phương phápGraph Đó là một công cụ toán học hiện dai, diễn tả kế hoạch tiến độ hoặc một dự

án, trong đó thể hiện trình tự và mối quan hệ giữa các công việc Trong sơ đồ mạng,công việc được biểu diễn một cách rõ ràng, sinh động, không chỉ cho ta thấy nội

dung công việc (như tên, thời gian thực hiện, tài nguyên yêu cầu, ) mà còn chothấy mối liên hệ giữa chúng Sơ đồ mạng là một mô hình toán học động, thê hiệntoàn bộ dự án thành một hệ thống nhất, chặt chẽ, trong đó thấy rõ vị trí từng côngviệc đối với mục tiêu chung và sự ảnh hưởng lẫn nhau giữa các công việc Nó cóthể áp dụng các phương pháp toán học vào việc phân tích, xây dựng và điều khiển

kế hoạch Nó cho khả năng kiểm soát tat cả các công việc và quản lý tiến độ một

cách khoa học và chính xác.

Để hiểu khái niệm về sơ đồ mạng ta xét ví dụ sau :

Giả sử lắp ghép khu nhà công nghiệp 1 tang, ta có các công việc chính sau:

1, Làm móng mất 5 ngày

Vận chuyền cần trục về mat 1 ngày

Lắp dung cần trục tháp mat 3 ngày

Van chuyền cầu kiện mắt 4 ngày

Theo tiến độ trên, công việc lam móng nhà, vận chuyển can truc va vanchuyển cấu kiện có thé tiên hành đồng thời va không phụ thuộc lẫn nhau Còn côngviệc lắp dựng cân trục chỉ có thé tiến hành sau khi vận chuyển cân trục về côngtrường Cũng như vậy, việc lắp ghép khung nhà chỉ có thé tiến hành khi các công

việc 1, 2, 3 ,4 đã hoàn thành.

Để biểu thị mối liên hệ phụ thuộc giữa các công việc, ta dùng các mũi tên nét

đứt dé nôi các công việc có liên quan đên nhau, được sơ đô mới:

Thời gian Tên công việc

Làm móng nhà

‘Van chuyển cần trục Lắp dựng cần trục

Lắp ghép khung nha

Hình 1.7 Tiến độ lắp ghép khung nhà sau khi thêm các mũi tên và vòng tròn

Tiếp tục đơn giản sơ đồ trên hình 1.7, bằng cách đánh số thứ tự các vòngtròn, ghi tên và thời gian các công việc, gộp các vòng tròn cùng xuất phát ban dau,

ta được một sơ dé gọi là sơ đồ mạng như sau:

Dinh nghĩa sơ đồ mạng : Là một hệ thống các công việc được sắp xếp theomột trình tự nhất định kể từ khi bắt đầu cho đến khi kết thúc một quá trình để tạonên một sản phẩm nào đó.

Trong một dự án, một công việc là một nhiệm vụ phải được hoàn thành thậm

chí là một mốc chính đánh dấu sự hoàn thành của một hay nhiều công việc khác,nghĩa là, công việc đó chỉ có thé bắt đầu khi tat cả các công việc cần thực hiện trước

phải đã được hoàn thành.

Như vậy chúng ta có thé thấy, sơ đồ mạng có thé biểu diễn bằng hình ảnhcủa một đồ thị có hướng với tập các nút và các cung biéu diễn các công việc và mối

quan hệ giữa các công việc.

Trong sơ đồ mạng trong hình 1.8 trên, đồ thị tương ứng với mỗi cung biểudiễn một công việc trong dự án và mỗi đỉnh (nút) biểu diễn một sự kiện (đánh dấu

sự bắt đầu hay kết thúc một hay một số công việc nào đó)

Mạng được biểu diễn bằng đồ thị với các đỉnh là các sự kiện nên chúng tagọi là mạng sự kiện và đồ thị tương ứng gọi là đồ thị sự kiện Với đồ thị sự kiện thì

sơ đồ mạng tương ứng cho chúng ta cái nhìn rõ ràng về thời gian, trình tự thực hiệncủa các công việc có lợi cho quản lý tiến độ, tuy nhiên lại không cho chúng ta khả

năng quản lý chặt chẽ tới từng công việc như thời gian thực hiện, tài nguyên sử

dung, Giải pháp trong trường hợp này là sử dụng đồ thị có hướng với các nútbiểu diễn các công việc và các cung biểu diễn mối quan hệ giữa các công việc Đồthị tập trung biểu diễn các công việc nên ta gọi là đồ thị công việc

Vi dụ dé thị công việc cho dự án lắp ghép khung nhà công nghiệp 1 tầng với

các công việc sau:

1 Làm móng mất 5 ngày với 10 nhân công

2 Vận chuyển cân trục về mat 1 ngày với 3 nhân công

3 Lấp dựng cần trục tháp mất 3 ngày với 5 nhân công sau khi đã vận

chuyển cân trục

4, Vận chuyên cấu kiện mắt 4 ngày với 7 nhân công.

5 Lắp ghép khung nhà mat 7 ngày với 15 nhân công

Biểu diễn các công việc ở các đỉnh của đồ thị gồm các thông tin :

"Tên công việc

Thời gian | Nhân công

Các công việc trước

Trong đó :

- Tên công việc : là tên gọi của công việc

~_ Thời gian : là khoảng thời gian cần thiết dé hoàn thành công việc

- _ Nhân công : số lượng nhân công cần thiết đề giải quyết công việc

- Các công việc trước : Các công việc cần hoàn thành trước khi thực hiện

công việc này.

Khi đó : đồ thị công việc cho dự án lắp ghép khung nhà công nghiệp 1 tangđược biểu diễn như sau :

1.2.2 Một số khái niệm trên sơ đồ mạng

Để hiểu rõ các yếu tố trên các sơ đồ mạng và sử dụng trong các tính toán,chúng ta đưa ra một số khái niệm sau :

1 Công việc

Danh từ công việc (Task) ở đây được hiểu là một quá trình nào đó, có thể làmối liên hệ phụ thuộc, được thể hiện bằng một cung và được gọi tên bằng ký hiệu

của hai sự kiện trước và sau Có loại hai công việc:

Công việc thực: là công việc cần sự chỉ phí về thời gian và tài nguyên hoặcchỉ cần thời gian trong các công việc cần chờ đợi Công việc này được thể hiện

8 Đỗ bê tong 6

4 ngàyCông việc ảo: là công việc chỉ mối liên hệ giữa hai hay nhiều công việc, nóibằng một nét liền Ví dụ:

lên sự bắt đầu của công việc này phụ thuộc vào sự kết thúc của công việc kia Côngviệc ảo không đòi hỏi sự chỉ phí về tài nguyên cũng như thời gian, nó được thé hiệnbằng một nét đứt Ví dụ:

Sự kiện không có cung đi ra gọi là sự kiện cuối của công việc Sự kiện không

có cung đi vào là sự kiện xuất phát, thường ký hiệu bằng số 1

3 Tài nguyên

Trong sơ đồ mạng, tài nguyên (Resource) được hiểu là thời gian và vật chatcần thiết cho quá trình xây dựng như: tiền vốn, nhân công máy móc, thiết bị,

4 Thời gian công việc

Thời gian công việc được ký hiệu là tj là khoảng thời gian để hoàn thànhcông việc theo ước lượng, ấn định trước hoặc tính toán, coi đó là trọng số mỗi cungtrong đồ thị sự kiện

5 Đường, đường găng

Đường (Path) là một chuỗi các công việc được sắp xếp sao cho sự kiện cuốicủa công việc trước là sự kiện đầu của công việc sau Chiều dài của đường đượctính theo thời gian, bằng tong thời gian các công việc nằm trên đường

Độ dai của một đường ¿ trong sơ đồ mạng là tong số độ dài các cung của

nó, ký hiệu là L(w) và bao giờ cũng đi từ sự kiện xuất phát đến sự kiện hoàn thành,

do đó có rất nhiều đường như vậy

Ta có: L()= Stu)

“em

Đường găng (Critipal Path) là đường có độ 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 Trong sơ đồmạng, công việc là công việc găng nếu D, = 0 (dự trữ lớn nhất) hoặc, d, = 0 (dựtrữ bé nhất), nghĩa là nếu công việc này làm chậm lại t ngày thì thời gian hoàn thành

dự án sẽ tăng lên t ngày Sự kiện găng là sự kiện nôi giữa hai công việc găng, là sự

kiện có dự trữ D, =0.

6 Thời gian của các sự kiện

Thời gian sớm của sự kiện i (TS } là thời điểm sớm nhất của một hoặcnhiều công việc bắt đầu bằng sự kiện ¡ có thể khởi công

Công thức tính thời gian sớm của sự kiện j: Ta tính từ sự kiện đầu :

TỶ =0

Tỷ =max {7° +1, : V ¡ là sự kiện trước đi tới j >1) }

Thời gian muộn của các sự kiện i (T,"): là thời điểm muộn nhất của mộthoặc nhiều công việc bắt đầu bằng sự kiện ¡ có thể khởi công

Muốn vậy ta phải đi ngược lại từ sự kiện cuối n đến sự kiện đang xét ¡ vớiđiều kiện :

pM ops

rw = min {7} +t, : V j là sự kiện kết thúc của công việc i-j (i<n)}

Thời gian dự trữ cia sự kiện: Là khoảng chênh lệch giữa hai thời điểm thờigian muộn và thời gian sớm của sự kiện.

Thời gian dự trữ của sự kiện ¡: p, =7; ~7Š

Do là thời gian mà sự kiện có thể làm chậm lại mà không làm ảnh hưởng tới

thời hạn hoàn thành dự án.

Để thiết lập công thức ta ký hiệu trong một nút sự kiện như sau:

Trong đó:

i: Su kiện đang xét; j, k, 1 là các sự kiện tiếp theo

h, k là các sự kiện trước đó và h là sự kiện đi đến ¡ có đường dài nhất

7; : Thời gian sớm của sự kiện đang xét 7“: Thời gian muộn của sự kiện đang xét.

¿„: Thời gian của công việc i-j.

7 Thời gian của các công việc

Thời gian sớm của các công việc:

Một công việc i-j có hai thời điểm sớm : khởi sớm (7/"`) và kết sớm (7°).

Hiển nhiên, một công việc là khởi sớm nếu nó bắt đầu ở thời điểm sớm của

Thời gian muộn của các công việc:

Tương tự như thời gian sớm của các công việc, mỗi công việc i-j có 2 thời

điêm muộn là khởi muộn Gia) va két muộn l ”); một công việc là khởi muộnnếu nó bắt đầu ở thời điểm muộn của sự kiện đầu:

Và kết muộn nó kết thúc ở thời điểm muộn của sự kiện sau:

đòn — TM

7" =T,

Khi thời gian của một công việc cô định, công việc đó được kêt thúc muộn

nếu nó khởi muộn:

km = phhm

Ty =1, + ty Nhận xét: Mỗi sự kiện chỉ có hai thời gian sớm và muộn, nhưng mỗi công

việc gồm hai sự kiện đầu và cuối nên có 4 thời gian: T° T° 7,0" ,7," Tuy nhiênchi cần tính được thời gian sớm, thời gian muộn của sự kiện là có thê suy ra thờigian sớm, thời gian muộn của công việc và tuỳ theo vị trí của sự kiện là đầu haycuối của công việc mà nó là khởi công hoặc kết thúc

Thời gian dự trữ của công việc:

Xét về bản chất, cách tính toán, có các loại dự trữ sau: dự trữ lớn nhất, dự trữ

bé nhất, dự trữ do khởi sớm, dự trữ do khởi muộn Nhưng trên thực tế chỉ sử dụng

hai loại dự trữ sau:

Dự trữ lớn nhất (D,): còn gọi là dự trữ toàn phần (dự trữ tổng cộng hay dựtrữ chung) Nếu ta sử dụng nó dé thay đổi các thời điểm khởi-kết sớm, khởi-kếtmuộn hoặc kéo dài thời gian công việc ¢, thì chỉ làm ảnh hưởng đến các công việctrước và sau công việc đó chứ không làm thay đổi thời hạn hoàn thành dự án Dựtrữ lớn nhất được tính theo công thức:

1.2.3 Phương pháp đường găng

1.2.3.1 Giới thiệu chung về phương pháp đường găng

Dự án phức tạp gồm một dãy các công việc, trong đó có một số phải đượcthực hiện theo một thứ tự nhất định và một số khác có thể thực hiện song song vớicác công việc khác Tập các công việc này có thể thiết kế như một mạng

Năm 1957, phương pháp đường găng (CPM) đã được phát triển như một môhình mạng cho quản lý dự án CPM là một phương pháp quyết định sử dụng ướclượng về thời gian cho mỗi một công việc Trong khi CPM dễ hiểu và dé sử dụng,

nó không chi ảnh hưởng về sự thay đồi thời gian mà còn có thể ảnh hưởng lớn đếnthời gian hoàn thành của một dự án phức tạp.

Phương pháp đường găng CPM (Critical Path Method) có ý nghĩa thực tiễn

va ứng dụng rộng rãi trong bat kỳ lĩnh vực nao Nó xác định trình tự công việc trong

dự án một cách khoa học, điều khiển việc sử dụng tài nguyên một cách hợp lý, côngviệc nào quan trọng cần thiết phải hoàn thành đúng thời hạn dé hoàn thành kếhoạch Từ đó ta cũng có thé tiến hành các công việc cũng như sử dụng tài nguyên

vào những công việc đó một cách hợp lý.

Một trong những nguyên tắc để điều khiển các dự án là phải tìm ra và nắmđược “khâu chủ yếu” Đường găng trong sơ đồ mạng chính là khâu chủ yếu đó.Trong kế hoạch tiến độ, xác định đường găng chính là tìm ra trong số các công việcphải tiền hành những công việc nào là then chốt, chủ yếu quyết định thời gian hoàn

thành dự án Chính vì ý nghĩa trên, nên người ta gọi phương pháp này là phương

pháp đường găng.

Những công việc găng nằm trên đường găng phải hoàn thành đúng thời hạn

đã định, nghĩa là phải khởi và kết đúng thời điểm đã định Nếu vì một lý đo nào đó

mà một công việc găng bị chậm trễ thì đường găng sẽ bị kéo dài thêm, tức là thời

hạn hoàn thành dự án cũng bị kéo dài.

1.2.3.2 Các bước tính toán trong phương pháp CPM

Để tính toán các thông số trong so đồ mang theo phương pháp CPM, ta chia

sự kiện thành 4 ô với các thông số được ghi trên mỗi sự kiện như

hình bên phải sau: <P,

Trong do: Xx)

j: sự kiện đang xét.

h: sự kiện đứng trước có đường đi đến sự kiện j đài nhất

Nếu có nhiều đường dài bằng nhau đến sự kiện j thì phải ghi lại hết các chỉ

số của các sự kiện đó

7Ÿ : Thời gian sớm của sự kiện đang xét.

7*; Thời gian muộn của sự kiện đang xét.

Các bước tính toán của phương pháp CPM được xây dựng trên ý tưởng của

thuật toán tìm đường đi Dijkstra với các bước như sau (xem [5]):

Bước 1: Lượt đi (tinh từ trái sang phải) Tinh các thời điểm sớm của sự kiện (7Ÿ ).

Bắt đầu từ sự kiện xuất phát :

TS =0.

Đối với mỗi sự kiện tiếp theo j (1<j<n), thời gian sớm được tính theo công

thức :

Tỷ =max{f;Ỷ +1}, với mọi ¡ là sự kiện trước của sự kiện j

Sự kiện nào đứng trước có đường đi đến sự kiện đang xét bằng đường đàinhất được ghi ở ô bên dưới của sự kiện đang xét (h)

Lặp lại việc tính toán trên theo thứ tự tăng dan của các chỉ số sự kiện cho đến

sự kiện cuôi cùng n thì kết thúc bước 1

Bước 2 : Lượt về (tính từ phải sang trái) Tính thời điểm muộn của sự kiện( 7;”)

Bắt đầu từ sự kiện cuối cùng :

Từ =TS

Tính ngược lại sự kiện (n-1), (n-2), ta có công thức:

Đối với mỗi sự kiện i (1<i<n), thời điểm muộn của sự kiện i (7;“) được tính

theo công thức:

7," =min{7 =r„}, với mọi j là sự kiện sau của sự kiện i

Cứ như vậy ta tính lùi đến sự kiện xuất phat số 1 và kết thúc bước 2

Bước 3: Xác định đường găng

Điều kiện cần và đủ của đường găng là đi qua các sự kiện găng và là đườngdai nhất Dé xác định đường găng ta chia thành hai giai đoạn:

Giai đoạn 1 : Đi từ sự kiện đầu đến sự kiện cuối, đánh dấu tất cả những sự

kiện găng (những sự kiện có dự trữ D, =0).

Giai đoạn 2 : Từ các sự kiện cuối cùng, ta lùi về các sự kiện găng bằng các

chỉ số ghi ở ô dưới của sự kiện

Làm tương tự như trên cho đến sự kiện xuất phát 1, ta sé thu được đườnggăng Một dự án có thê có nhiều đường găng

1.2.3.3 Ví dụ

Cho sơ đồ mạng sự kiện biểu diễn bằng đồ thị sau:

Trong sơ dé hình 1.9, có 6 sự kiện được đánh số từ 1 đến 6 tại các đỉnh

Trọng số trên cạnh từ ¡ đến j là thời gian thực hiện ¿„ của công việc, thực hiện khi

sự kiện ¡ kết thúc đến lúc sự kiện j bắt đầu

Theo các bước tính toán theo phương pháp đường găng tại mỗi bước tính

toán thu được đồ thị của mạng như sau:

Bước 1: Lượt đi tính các giá trị 7Ÿ từ trái sang phải, ta được kết quả sau:

Hình 1.10 Sơ đồ mạng sau khi đã tính các giá trị khởi sớmBước 2 : Lượt về tính từ phải sang trái các giá trị 7" ta có hình vẽ:

Hình 1.11 Sơ đồ mạng sau khi đã tính các giá trị khởi muộn

Bước 3: Xác định đường găng

Hình 1.12 Sơ đồ mạng sau khi đã xác định đường găng

1.2.4 Phương pháp ước lượng đánh giá - PERT

1.2.4.1 Khái niệm cơ bản về phương pháp PERT

PERT có nghĩa là “kỹ thuật ước lượng và đánh giá" (Program Evaluation

and Review Technical), nhưng PERT được coi như đồng nghĩa với sơ đồ mạng.Trên thực tế, PERT và CPM ra đời gần như đồng thời và PERT cũng chỉ là mộttrong các phương pháp sơ đồ mạng PERT là một mô hình mạng cho phép có sựngẫu nhiên trong việc linh động về thời gian hoàn thành của dự án PERT được pháttriển vào những năm 1950 trong dự án của một người Mỹ Navy’s Polaris với hànhnghìn thầu khoán Nó giúp giảm thời gian và chỉ phí để hoàn thánh dự án

Khác với phương pháp CPM là phương pháp coi thời gian là một hằng số.Nhưng trong thực tế thường gặp rất nhiều yếu tố ngẫu nhiên tác động đến dự án(điều kiện thời tiết, việc cung cấp nhân công, thiết bị ) nên thời hạn hoàn thành dự

án nhiều khi không cố định Vấn đề đặt ra là phải xử lý tình trạng không ổn định vềthời gian đó như thế nào để rút ra những kết luận đáng tin cậy và có thé sử dụngđược trong thi công Muốn giải quyết vấn đề này cần vận dụng các phương phápcủa lý thuyết thống kê PERT đã đưa vào kế hoạch của dự án yếu tố ngẫu nhiên va

đó cũng chính là ưu điểm nổi bật của phương pháp Nó đặc biệt phù hợp với nhữngtrường hợp lần đầu thực hiện công việc hoặc mới sử dụng các kỹ thuật mới khi mànhững số liệu ban đầu đưa vào chưa có định mức sẵn

PERT được xây dựng dựa trên lý thuyết đồ thị nhưng khi sử dụng nó ta cẦnđến những kiến thức cơ bản của lý thuyết thông kê như: hàm phân phối xác suất, giátrị trung bìmh, Mode, biên độ, phương sai, độ lệch tiêu chuẩn

1.2.4.2 Uớc lượng thời gian hoàn thành công việc

Khi lập kế hoạch thi công người ta dựa trên kinh nghiệm để ước lượng thờigian hoàn thành công việc Vì vậy, thời gian đó không xác định, ta phải lấy thờigian trung bình mong muốn ¿ (tức kỳ vọng) kém theo độ lệch tiêu chuẩn o hoặcphương sai V của thời gian.

Thời gian trung bình mong muốn ¿ là thời gian ước lượng với 50% khả năngthực hiện sớm và 50% thực hiện chậm Vì thế, để xác định số liệu của mỗi côngviệc cần sử dụng hàm phân bố của thời gian thực hiện công việc Nhưng có một vấn

đề khác là ta không hề có thông tin về sự phân bố xác suất của thời gian thực hiệncông việc (vì nó phụ thuộc vào những biến động kéo dài ngẫu nhiên), do đó phải giảthiết 1 hàm phân bố xác xuất phù hợp cho từng hoàn cảnh của từng trường hợp cụthể Có 3 ước lượng thời gian được đặt ra và được nằm trong đường cong lý thuyết:

1) Thời gian lạc quan („) là thời gian ước lượng it nhất để hoàn thành công.việc trong những điều kiện thuận lợi nhất

2) Thời gian bi quan (¢,) là thời gian ước lượng lớn nhất dé hoàn thành côngviệc trong những điều kiện khó khăn nhất

3) Thời gian thực hiện (z„) là thời gian ước lượng dé hoàn thành công việc cónhiều khả năng xảy ra nhất, tức là có xác suất lớn nhất, còn gọi là Mode của

công việc.

Do phải ước lượng 3 thời gian này, buộc người lập kế hoạch phải quan tâmđến các khó khăn của từng công việc Các ước lượng có xu hướng loại bỏ ảnhhưởng của các số liệu đã định sẵn của người lập kế hoạch Chúng trở thành cácđiểm dé thiết lập đường cong phân bố xác suất cho thời gian thực hiện

Giả thiết thời gian hoàn thành công việc là một đại lượng ngẫu nhiên tuântheo luật phân phối với hàm mật độ xác suất có dạng hàm B

wy _ J€ứ=4)“(b=0)”,t3a,ø,y >-1

cla hang số được chuẩn hoá xác định từ điều kiện : ef (Œ—4)Œ—b)7 đi =1

Dinh Mode của

thi cnn

Khoảng các công việc ¬

dự kiến hoàn thành Trung độ thời gian trung,

bình mong muốn.

>

ty lạt h Thời gian

Hình 1.13 Hàm phân bố xác suất B của thời gian sự kiện

Khi có thời gian phân phối B thì kỳ vọng thời gian được tính bằng công thức

thực nghiệm sau (xem [5]):

1=(t, +4xt,, +t,)/6

Giả thiết, độ lệch tiêu chuẩn ơ, là giá trị đo độ tản mạn của đường cong xácsuất xung quanh giá trị trung bình của nó

o=(, -1,)/6

Phuong sai được tính theo công thức: V =o"

Sở di ta chọn B lam phân bó cho t vì đại lượng ngẫu nhiên có hàm phân bố Bchỉ phụ thuộc vào các nhân 16 có tác động rất nhỏ và rất lớn

Từ công thức tính t và dựa vào dé thị của hàm f thì nhìn chung giá trị trungbình 7 luôn sai khác giá trị thời gian có xác suất cao nhất ¿„ Ta cũng có thể thấyrằng z„ và t, có xác suất xảy ra rất nhỏ, chúng chỉ có tác dụng xác định một cáchgần đúng phạm vi của phân bố thời gian có thể của công việc Người ta cũng có thểdùng công thức:

xác không khác nhau nhiều Vì vậy trong những tính toán dưới đây ta sẽ dùng công

thức:

;.14Xt +t,

6

với độ lệch tiêu chuẩn (hay sai số): o=(t, -t,)/6

1.2.4.3 Các thông số thời gian trong so đồ mang PERT

Giá trị ước lượng trung bình ¿ và phương sai V của thời han hoàn thành côngviệc được sử dụng để đánh giá các thời điểm hoàn thành sự kiện

Trong PERT, thời gian sớm của sự kiện được tính như sau:

7520

Tỷ =max{` +t}, với mọi i là sự kiện trước của sự kiện j

Tuy nhiên mỗi thời gian trong phương pháp PERT có thêm độ lệch tiêu

chuẩn hay phương sai của nó, dé do sai số khi ta dùng kỳ vọng ¢ làm ước lượng

cho thời gian Vi vậy đi đôi với việc tính 7Ÿ của sự kiện, phải tính thêm phương sai

sớm của sự kiện ây:

Hài = min{T" —ø} „ với mọi ¡ là sự kiện trước của sự kiện j

Phương sai muộn được tính như sau:

vi" =0

MyM

Ve =Vj +,Việc xác định đường găng của PERT cũng giống như phương pháp CPM ta

đã trình bày ở trên.

Thời gian thực hiện dự án T; chính là thời gian trung bình mong muốn của

các công việc nằm trên đường găng Với dự án có thời gian thực hiện là T, thìphương sai V, là tổng các phương sai riêng của các công việc nằm trên đường găng

đó.

V.=šV

Trong các trường hợp có nhiều đường găng thì phương sai thực hiện dự án sẽ

là phương sai lớn nhất của các dự án đó

1.2.4.4 Tính xác suất hoàn thành công việc

Thực tế, quản lý dự án theo phương pháp PERT, vấn đề đặt ra là cần phảitính được xác suất hoàn thành theo thời hạn kế hoạch đã định Tị Theo lý thuyếtxác suất, nếu thời gian trung bình mong muốn của một sự kiện và độ lệch tiêu chuẩncủa nó đã xác định ta có thể tính được xác suất hoàn thành dự án theo kế hoạch.Thời gian thực hiện sự kiện được xem như một đại lượng phân bố ngẫu nhiên cóhàm phân bố chuẩn mà kỳ vọng chính là T, , độ lệch tiêu chuân là 6, _ Mặt khác,thời gian hoàn thành công việc là đại lượng có phân bố chuẩn ƒ Điều này chi đúngtrong việc cộng một số lượng đủ lớn các đường cong ñ (khoảng hơn 100 đường)

Hình 1.14 mô tả một đường cong chuân :

y=f@) Đường cong chuẩn

t >

0 Ta Tk Thời gian (t)

Hình 1.14 Đường cong chuẩn

Xác suất để hoàn thành theo thời hạn kế hoạch Pạy là:

Diệntích phần gạch chéo N

P(0<t<T,)} -( )%

\ Diện tích phân bên đưới đường cong ;

Trong đó, t - đại lượng ngẫu nhiên biểu thị thời gian hoàn thành dự án.

Mặt khác, ở đây có phân bố chuẩn với kỳ vọng Tạ và phương sai ơạˆ Khi đó,

Ta đánh giá được sai số của các ước lượng thời gian:

Trong khoảng 7, +o, có P = 68% không hoàn thành kế hoạch

Trong khoảng 7, +2o,, tương đương với k = 2 có P = 95% là không hoàn

thành đúng kế hoạch

Trong khoảng thời gian 7, +3ơ„ có P = 99% không hoàn thành kế hoanh

Từ giá trị của hàm phân phối chuẩn ø theo x, ta lập được bảng xác xuất của

P theo giá trị z và sẽ đánh giá được khả năng hoàn thành dự án theo kế hoạch

Ví dụ :

Thời hạn kế hoạch là 7, =17 ngày

Thời hạn trung bình là 7, =13,5 ngày

Độ lệch tiêu chuẩn là 2 ngày khi do: z=-*—ˆ* = 1,8

Tra bảng phân phối chuẩn ta thu được P = 0,964

Như vậy là công trình có nhiều khả năng hoàn thành kế hoạch trước thời gian

đã định Theo phương pháp CPM, nếu phải rút bớt thời gian kế hoạch thì phải bằngmột cách nào đó, chăng hạn tăng thêm nhân lực, thêm máy móc thiết bị cho cáccông việc găng cần rút ngắn thời gian Nhưng trong phương pháp PERT thì rút ngắn3,5 ngày có thê đạt được mà không cần phải rút ngắn thời gian các công việc găng

vì các thời gian trong PERT là ước lượng và thời gian trung bình vẫn có thể rútngắn được trong những điều kiện thuận lợi Như vậy trong phương pháp PERT tachấp nhận cả những tác động của các yếu tố khách quan Thời gian theo kế hoạchđược dự kiến hoàn thành theo một xác suất nào đó Đây chính là một quy luật củathế giới ngẫu nhiên trong PERT và cũng là ưu điểm lớn nhất của phương pháp này

1.3 Ứng dụng sơ đồ mạng trong quản lí tiến độ dự án

1.3 1 Sơ đồ mạng trên trục thời gian

Nếu trên sơ đồ mạng thì chúng ta thấy được mối quan hệ trước sau, ràngbuộc giữa các công việc nhưng không thể biết rõ tỷ lệ thời gian Một yêu cầu kếtxuất của các chương trình có sơ đồ mạng là phải thể hiện mối liên hệ giữa các côngviệc theo tỉ lệ thời gian Kết quả này hỗ trợ cho người quản lý dự án có một cái nhìntổng quan về toàn bộ thời lượng của dự án Hơn nữa, tại mỗi thời điểm, người quản

lý cũng có thể xác định được những công việc đã hoàn thành, những công việc đangthực hiện và những công việc nào chuẩn bị thực hiện

1.3 2 Đưa sơ đồ mạng lên trục thời gian

Phương pháp đưa sơ đồ mạng lên trục thời gian rất đơn giản Ta có thể làmnhư sau:

- Trước hết xác định một trục thời gian tính theo ngày (tuần).

- Kéo căng các đường găng lên trục thời gian trước Nếu có nhiều đườnggăng thì sẽ biểu diễn bằng các đường song song với trục thời gian Đường

găng sẽ được kí hiệu phân biệt với các đường không găng.

- Sắp xếp các công việc không găng thành những đường cũng song song với

trục thời gian nhưng phân biệt với các đường găng bởi một ký hiệu nào đó.

Ta có thể chuyền sơ đồ mạng lên trục thời gian theo 2 cách Cách 1 làm chocác công việc đều khởi sớm, cách 2 làm cho các công việc đều khởi muộn Nhưngcách 1 hay được dùng vì khi đó các dự trữ sẽ dồn về sau, điều đó có lợi cho việcđiều chỉnh tiến độ

Vi dụ: Cho sơ đồ mạng như hình vẽ dưới đây :

Hình 1.15 Ví dụ minh họa - Sơ đồ mạng ban đầu

Các phương án chuyên sơ đồ mạng lên trục thời gian sẽ như sau:

1.3.3 Chuyển sơ đồ mạng sang sơ dé ngang

Một cách khác dé nhận biết rõ hơn 1 công việc được làm từ ngày nào đếnngày nào và tại mỗi thời điểm xác định công việc nào đang tiến hành là sử dụng sơ

dé ngang Tuy sơ đồ ngang không có nhiều ưu điểm bằng sơ đồ mạng nhưng sơ đồngang lại có thé giải quyết tốt van đề này Như vậy, nếu có một cách chuyển từ so

đồ mạng sang sơ đồ ngang thì ta sẽ tận dụng được ưu điểm của cả 2 loại sơ đồ này.Chính vì vậy mà người ta đã nghĩ ra cách chuyền sơ đồ mạng sang sơ đồ ngang tạo

ra 1 loại sơ đồ mới, gọi là sơ đồ mạng ngang Việc chuyển đổi tiền hành như sau:

Bước I: Vẽ hệ toạ độ với trục hoành là trục thời gian còn trục tung là trục công

việc.

Bước 2: Biéu diễn các công việc:

- Mỗi công việc được biểu thị bằng 1 đoạn thẳng song song với trục thờigian Độ dài đoạn thăng chính là thời gian của công việc (1, )

- Các công việc ảo được biéu diễn thành 1 điểm

- Trên đoạn thang biểu diễn công việc, đầu mút trái biểu diễn sự kiện bắtđầu, đầu mút phải biéu diễn sự kiện kết thúc

- Các công việc găng sẽ được đánh dấu bằng 1 giá trị riêng trong trường dấu.Bước 3: Các công việc được biểu diễn lần lượt theo quy tắc sau:

- Các công việc biểu dién từ dưới lên theo chiều dương của trục tung (trục

công việc).

- Thứ tự của công việc tăng dần về độ lớn của sự kiện kết thúc Nếu các congviệc có cùng sự kiện kết thúc thì công việc nao có sự kiện đầu nhỏ hơn sẽ xếp trước.Nếu có nhiều công việc cùng kết thúc ở sự kiện ¡ thì các công việc i-j sẽ bắt đầu ởchỉ số ¡ có hoành độ lớn nhất

Ví dụ trong hình 1.17 dưới đây: công việc C7 kí hiệu 4-6 có sự kiện đầu là sựkiện kết thúc của các công việc C3 (2-4) và C5 (3-4) Do đó công việc C7 bắt đầu ở