Chia sẻ 1,000 VNĐ
Tài liệu Phương pháp sơ đồ mạng lưới (PERT)
Tài liệu này có phí 1,000 VNĐ

bạn cần mua tài liệu để được xem đầy đủ nội dung

Tài liệu này có thể xem trước 1 trang

/50 trang
Thành viên idoc2012

Phương pháp sơ đồ mạng lưới (PERT)

- 12 tháng trước
12,164
Báo lỗi

Kỹ thuật đánh giá và kiểm tra dự án PERT (Program Evatuation and Review Technique). Mục tiêu chính của phương pháp: đánh giá khả năng hoàn thành dự án trong thời hạn định trước.-) Trình tự thực hiện các công việc: việc nào có thể làm ngay, việc nào làm sau việc việc nào. Thời gian cần thiết ể hoàn thành mỗi việc.

Nội dung

PHƯƠNG PHÁP SƠ ĐỒ MẠNG LƯỚI

Kỹ thuật đánh giá và kiểm tra dự án PERT (Program Evatuation and Review Technique). Mục tiêu chính của phương pháp: đánh giá khả năng hoàn thành dự án trong thời hạn định trước. Cho biết: -) Trình tự thực hiện các công việc: việc nào có thể làm ngay, việc nào làm sau việc việc nào. -) Thời gian cần thiết để hoàn thành mỗi việc. Phải làm: a) Thời hạn sớm nhất để hoàn thành toàn bộ dự án. b) Thời hạn bắt đầu sớm nhất và muộn nhất của mỗi việc sao cho toàn bộ dự án được hoàn thành đúng kế hoạch. c) Thời điểm kết thúc sớm nhất và muộn nhất của mỗi việc sao cho toàn bộ dự án được hoàn thành đúng kế hoạch. d) Thời gian dự trữ cho mỗi việc, nghĩa là khoảng thời gian mà có thể bắt đầu muộn hoặc kết thúc muộn mà không ảnh hưởng tới toàn bộ dự án.

Định nghĩa và quy tắc lập sơ đồ mạng lưới

Definition

Một tập hợp các điểm (ta gọi là các đỉnh, kí hiệu A) và tập hợp các mũi tên (ta gọi là các cung, kí hiệu là U) được gọi là một sơ đồ mạng lưới nếu chúng thỏa mãn các điều kiện sau :

Giữa hai đỉnh có không quá một cung nối liền và ngược lại mỗi cung liên kết 2 đỉnh nào đó với nhau. Cung nối từ đỉnh i đến đỉnh j kí hiệu là (i, j) trong đó i là điểm gốc của cung, và j là điểm ngọn của cung.

Trong sơ đồ không chứa vòng kín, nghĩa là, từ một đỉnh bất kỳ, đi theo chiều các mũi tên, không bao giờ quay về điểm xuất phát. Một dãy các cung nối tiếp nhau được gọi là một đường đi.

Giữa 2 đỉnh tùy ý bao giờ cũng có một dãy các cung nối liền.

Có một đỉnh chỉ toàn các cung đi ra được gọi là đỉnh khởi công và có một đỉnh chỉ toàn các cung đi vào được gọi là đỉnh khánh thành. Các đỉnh còn lại có cả cung đi ra và cung đi vào.

Định nghĩa và quy tắc lập sơ đồ mạng lưới

i j

Figure: Đây là gì?

Các quy tắc thực hành lập sơ đồ mạng lưới

Quy tắc 1: Nếu một nhóm nhiều công việc cùng bắt đầu từ một sự kiện i và cùng kết thúc tại một sự kiện j thì không được biểu diễn như Hình 2a, tùy thuộc vào tính chất của các việc mà ta có thể có những xử lý sau: a) Nếu tính chất của các việc như nhau hoặc trong thực tế không là tách rời nhau ra được thì gộp chúng lại thành một cung duy nhất Hình 2b. b) Nếu tính chất các việc khác nhau mà không thể gộp chung lại được thì ta phải thêm đỉnh mới và cung giả Hình 2c. Đỉnh mới là k cung (k, j) gọi là các cung giả, biểu diễn bằng nét đứt. Chú ý việc giả có thời gian hoàn thành bằng không, nếu nó chỉ phản ánh trật tự giữa các việc; nó có thời gian khác không, nếu nó phản ánh sự chờ đợi.

a

b i j 2a

Các quy tắc thực hành lập sơ đồ mạng lưới

Quy tắc 2: Nếu một nhóm các công việc lập thành một mạng con trong một sơ đồ mạng lưới (các công việc và các sự kiện của nhóm này không phụ thuộc gì vào và không ảnh hưởng đến các công việc của nhóm khác của sơ đồ mạng lưới trừ sự kiện đầu tiên và sự kiện cuối cùng của nhóm này) thì ta có thể gộp mạng con đó lại thành một cung duy nhất nếu việc gộp đó không làm cho sơ đồ mạng lưới trở nên quá thô (Hình 3a) chuyển sang Hình 3b. Cung (2, 4) trong Hình 3b mô tả cả 3 công việc a, b, c trong sơ đồ mạng lưới 3a.

1 54

3

2

3a

Các quy tắc thực hành lập sơ đồ mạng lưới

Quy tắc 3: Nếu một nhóm các công việc liên hệ với nhau theo trật tự: a ) Việc d sau việc a, b, c. Việc e sau việc a, b thì biểu diễn như Hình 4a là sai mà phải biểu diễn như Hình 4b. b)Việc d sau việc a,c. Việc e sau việc a,b thì biểu diễn như Hình 4a và Hình 4b đều sai, mà phải biểu diễn như Hình 4c.

a

b

c

d

e

a

b

e

dc

Các quy tắc thực hành lập sơ đồ mạng lưới

Quy tắc 4: Nếu một nhóm công việc liên hệ với nhau theo trật tự: Việc a sau việc b Việc c sau việc d Việc e sau việc b, d Thì biểu diễn như Hình 5

d

ab

e

c

Figure:

Các quy tắc thực hành lập sơ đồ mạng lưới

Quy tắc 5:

Nếu việc a bắt đầu khi hoàn thành được 1/5 công việc x. Việc b bắt đầu khi hoàn thành được 1/2 công việc x. Việc c bắt đầu khi hoàn thành được 4/5 công việc x. Việc d bắt đầu khi hoàn thành toàn bộ công việc x. Thì biểu diễn như Hình 6a là sai mà phải biểu diễn như Hình 6b mới đúng.

i j x

a

b

c

d

6a

Các quy tắc thực hành lập sơ đồ mạng lưới

Quy tắc 6:

a) Nếu có một đỉnh không phải đỉnh khởi công mà chỉ toàn những cung đi ra thì ta phải thêm một cung giả nối từ đỉnh khởi công với đỉnh đó: Hình 7 a sang Hình 7 b.

1

3

4

52

1

3

4

52

2

7a

7b

Quy tắc đánh số các sự kiện

1 Cho sự kiện khởi công toàn bộ mang số 1 và xếp nó vào lớp thứ nhất.

2 Xóa tượng trưng sự kiện số 1 cùng với các cung đi ra khỏi sự kiện số 1, nhặt ra các sự kiện chỉ toàn những cung đi ra và xếp nó vào lớp thứ 2...

3 Xóa tượng trưng các sự kiện của lớp thứ i cùng các cung ra khỏi các sự kiện thuộc lớp i, nhặt ra các sự kiện chỉ toàn những cung đi ra và xếp chúng vào lớp thứ i + 1.

4 Đánh số các đỉnh từ 1 đến n theo từng lớp, bắt đầu từ lớp thứ 1; các đỉnh thuộc cùng một lớp được đánh số tùy ý. Đỉnh khởi công thuộc lớp i = 1, được đánh số 1, đỉnh khánh thành được đánh số lớn nhất n.

Các chỉ tiêu thời gian của sơ đồ mạng lưới

Kí hiệu thời điểm sớm xuất hiện sự kiện j là T sj ∀ j ∈ A, được định nghĩa như sau: Ta biết rằng sự kiện j là xuất hiện nếu mọi công việc ứng với các cung đi tới sự kiện j đã hoàn thành. Vì vậy đối với sự kiện 1 là sự kiện khởi công toàn bộ, trước đó chưa có công việc nào hoàn thành nên T s

1 = 0.{

T s 1

= 0; T sj = max{T

s i + tij ∀ (i , j) ∈ U

j } trong đó U−j là tập hợp

các cung đi tới đỉnh j . Đối với sự kiện j tùy ý, như hình vẽ thì đến thời điểm 24 , mới có việc (i1, j) hoàn thành nếu việc này thi công sớm nhất vào thời điểm 18, việc (i2, j) và (i3, j) chưa hoàn thành, dù cho 2 việc này thi công sớm nhất có thể được thứ tự là 19 và 16 cũng xét như vậy ta được:

T sj = 27 = max{T s j + tij | ∀ (i , j) ∈ U

j } (1)

T sj = 18 (2)

Thời điểm sớm xuất hiện sự kiện

i1

i2

i3

j

ti1j = 6

ti2j = 8

ti3j = 10

T Sj =?

Figure:

trong đó U−j = {(i1, j), (i2, j), (i3, j)}- tập hợp các công việc ứng với với các cung đi tới sự kiện j . Từ định nghĩa xuất hiện một sự kiện ta đi suy ra T sj là độ dài

Thời điểm muộn xuất hiện sự kiện

Kí hiệu thời điểm muộn xuất hiện sự kiện i (mà không ảnh hưởng đến thời gian hoàn thành toàn bộ công trình) là Tmi ∀ i ∈ A. Nếu sự kiện i xuất hiện muộn hơn thời điểm Tmi thì thời gian hoàn thành toàn bộ công trình bị kéo dài. Ta có định nghĩa:

Definition

Tmn = T s n ; (4)

Tmi = min j {Tmj − tij | ∀ (i , j) ∈ U

+

j } (5)

trong đó U+j là tập hợp các công việc ứng với các cung ra khỏi sự kiện i.

Giả sử biết thời điểm muộn nhất xuất hiện các sự kiện kề sau sự kiện i . Ta biết rằng sự kiện i có xuất hiện thì các công việc ứng với các cung ra khỏi i mới bắt đầu được.

i1 T m j1

=

Thời điểm muộn xuất hiện sự kiện

Một quy trình công nghệ gồm một số các công việc chính sau đây. Công việc a1 làm trong 6h bắt đầu ngay. Công việc a2 làm trong 4h sau a1 hoàn thành. Công việc a3 làm trong 5h bắt đầu ngay. Công việc a4 làm trong 7h bắt đầu ngay. Công việc a5 làm trong 6h sau a1hoàn thành. Công việc a6 làm trong 8h sau a4 hoàn thành. Công việc a7 làm trong 6h sau a4 hoàn thành. Công việc a8 làm trong 9h sau a3, a6, a7 hoàn thành. Công việc a9 làm trong 7h sau a3, a6 hoàn thành. Công việc a10 làm trong 9h sau a2, a5 hoàn thành. Công việc a11 làm trong 5h sau a2 hoàn thành được 5h và sau a9 hoàn thành. Công việc a12 làm trong 5h sau a7 hoàn thành. Công việc a13 làm trong 8h sau a8, a12 hoàn thành.

Ví dụ

2 7

1

4

5

3 6

9

10

118a1

a3

a4 a6

a2

a5

0

0 a8

a12

a11 5

0

a10

a13

a9

Figure:

Ví dụ

Giải:

T s1 = 0

T s2 = max{T s 1 + t1,2} = 0 + 6

h = 6h

T s3 = max{T s 1 + t1,3} = 0 + 7

h = 7h

T s4 = max{T s 2 + t2,4} = 6

h + 4h = 10h

T s5 = max{T s 1 + t1,4,T

s 3 + t3,5}

= max{0h + 5h, 7h + 8h} = 15h.

T s6 = max{T s 3 + t3,6} = 7

h + 6h = 13h

T s7 = max{T s 2 + t2,7,T

s 4 + t4,7}

= max{6h + 6h, 10h + 0h} = 12h.

T s8 = max{T s 4 + t4,8,T

s 5 + t5,8}

= max{10h + 5h, 15h + 7h} = 22h.

T s9 = max{T s 5 + t5,9,T

s 6 + t6,9}

= max{15h + 0h, 13h + 0h} = 15h.

Ví dụ

+) Tính thời điểm muộn nhất để hoành thành các sự kiện.

Tm11 = T s 11 = 32

h .

Tm10 = min{T m 11 − t10,11 = 32

h − 8h = 24h}.

Tm9 = min{T m 10 − t9,10} = 24

h − 9h = 15h.

Tm8 = min{T m 11 − t8,11} = 32

h − 5h = 27h.

Tm7 = min{T m 11 − t7,11} = 32

h − 9h = 23h.

Tm6 = min{T m 10 − t6,10,T

m 9 − t6,9}

= min{24h − 5h, 15h − 0h} = 15h.

Tm5 = min{T m 9 − t5,9,T

m 8 − t5,8}

= min{15h + 0h, 27h − 7h} = 15h.

Tm4 = min{T m 8 − t4,8,T

m 7 − t4,7}

= min{27h − 5h, 23h − 0h} = 22h.

Tm3 = min{T m 6 − t3,6,T

m 5 − t3,5}

h h h h h

Ví dụ

1

i

n

l(4i ) l(γi )

Tmn

Di = Tmn [l(4i ) + l(

Figure:

Definition

Sự kiện i được gọi là sự kiện găng nếu thời gian dự trữ của nó bằng không, tức là Di = 0⇔ Tmi = T

s i

Trong ví dụ ở tiểu mục 2) các sự kiện 1, 3, 5, 9, 10, 11 là những sự kiện găng.

Thời điểm sớm nhất bắt đầu và sớm nhất kết thúc công việc

Kí hiệu T ksij là thời điểm sớm nhất bắt đầu công việc (i , j) ∀l ; (i , j) ∈ U. Ta biết rằng sự kiện i có xuất hiện thì công việc (i, j) mới bắt đầu được (i < n) nên

T ksij = T s i (6)

Kí hiệu thời điểm sớm nhất kết thúc công việc (i, j) T hsij ∀ (i , j) ∈ U. Ta biết rằng, giữa thời điểm kết thúc sớm nhất và thời điểm bắt đầu (sớm nhất) công việc (i, j ) chênh nhau khoảng thời gian thi công tij nên:

T hsij = T ks ij + tij ∀ (i , j) ∈ U. (7)

Tử (6) và (7) ta suy ra:

T hsij = T s i + tij ∀ (i , j) ∈ U. (8)

Thời điểm muộn nhất kết thúc công việc

Kí hiệu thời điểm muộn nhất kết thúc công việc (i , j) là T hmij ∀ (i , j) ∈ U. Ta biết rằng sự kiện j được coi là xuất hiện nếu mọi công việc (i , j) ∈ U j đều đã hoàn thành, vì vậy công việc (i, j) không được phép kết thúc muộn hơn Tmj . Do đó :

T hmij = T m j với mọi (i , j) ∈ U (9)

Kí hiệu thời điểm muộn nhất bắt đầu công việc (i, j) là T kmij ∀ (i , j) ∈ U. Cũng lập luận như việc lập công thức (7) ta có:

T kmij = T hm ij − tij với mọi (i , j) ∈ U. (10)

Từ (9) và (10) suy ra

T kmij = T m j − tij với mọi (i , j) ∈ U. (11)

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

Definition

Thời gian sự trữ chung của công việc (i, j), được kí hiệu và xác định như sau:

Dcij = T km ij − T

ks ij với mọi (i , j) ∈ U. (12)

Từ (6) và (11) ta có:

Dcij = T m j − tij − T

s i với mọi (i , j) ∈ U. (13)

theo (8) và (9) ta có:

Dcij = T hm ij − T

hs ij với mọi (i , j) ∈ U. (14)

Từ công thức (14) suy ra

T hmij − T hsij = T kmij = D

c ij với mọi (i , j) ∈ U.

Thay (3) và (??) vào (13) ta được

Dcij = T m n − [l(4i ) + tij + l(γj)] với mọi (i , j) ∈ U. (15)

Nhận xét: Tổng l(4i + tij + l(γj )) là độ dài đường đi dành nhất từ sự kiện 1 qua công việc (i, j) đến sự kiện n. Như vậy Dcij là chênh lệch giữa hai đường đi dài nhất: đường đi dài nhất không điều kiện và đường đi dài nhất có điều kiện (qua công việc (i, j)).

1

i

n

l(γi )

Dcij = T m n − [l(4i + ti ,k) + l(γi )]

il(4i )

tij

tmn

Figure:

Nhận xét: Công việc (i, j) được gọi là công việc găng nếu nó không có thời gian dự trữ chung tức là Dcij = 0.

Đường găng

Definition

Đường đi có độ dài lớn nhất từ sự kiện 1 đến sự kiện n trong sơ đồ mạng lưới được gọi là đường găng.

Nếu kí hiệu đường găng là g thì hiển nhiên l(g) = Tmn = T s n .

Theorem

(Điều kiện cần và đủ để một sự kiện và công việc là găng). 1) Sự kiện i là sự kiện găng khi và chỉ khi i nằm trên đường găng. 2) Công việc (i, j) công việc găng khi và chỉ khi (i, j) nằm trên đường găng.

Chứng minh: 1) Theo định nghĩa ta có sự kiện i là sự kiện găng⇔ Di = 0⇔ Tmn = l(4i) + l(γj). Đẳng thức này có nghĩa là đường đi dài nhất từ sự kiện 1 qua sự kiện i đến sự kiện n là một đường găng (vì đường nào có độ dài bằng Tmn thì đường ấy là đường găng). 2) Công việc (i, j) là công việc găng Dc = 0 theo định nghĩa do đó

Cách xác định đường găng

Từ định lý trên ta suy ra cách xác định đườn găng như sau: Tính thời gian sự trữ chung cho tất cả các công việc. Tách ra các công việc không có thời gian dự trữ chung (những việc găng). Lập những dãy các việc găng nối tiếp nhau từ sự kiện 1 đến sự kiện n. Mỗi dãy như vậy chính là một đường găng.

Chú ý: Để thuận tiện cho việc khảo sát sơ đồ mạng lưới ta biểu diễn mỗi sự kiện bởi một vòng tròn chia làm 4 phần

i T si T

m i

Di

Figure:

Phần trên ghi số thứ tự sự kiện. Phần bên trái ghi thời điểm sớm nhất xuất hiện sự kiện.

Cách xác định đường găng

Để dễ dàng nhận ra đường găng, ta kí hiệu mỗi việc găng bởi mũi tên kép :

i j DCij

Figure:

Để khảo sát sơ đồ mạng lưới sâu hơn ta phân tích các việc không găng làm hai loại: + Việc không găng độc lập là việc không găng mà sự kiện gốc và sự kiện ngọn của việc ấy đều là những sự kiện găng Hình 15 biểu diễn sự kiện i găng:

i

T si Tmi

0

i

T si Tmi

0

tij

Dij

Tmj = T s j

(sự kiện j- găng). tij < Tmj − T

s i ⇔ D

C ij > 0 ( việc (i, j ) không găng).

Công việc không găng độc lập được sử dụng toàn bộ thời gian dự trữ chung của nó mà không làm ảnh hưởng gì đến các việc khác. + Việc không găng liên quan là việc không găng mà ít nhất một trong hai sự kiện gốc hoặc sự kiện ngọn của là sự kiện không găng.

Thời gian sự trữ riêng gốc của việc (i , j) được kí hiệu và xác định như sau:

Dgij = T m ij − tij − T

m i (16)

Hay là Tmi = T

m ij − tij −D

g ij (17)

Từ (16) và (17) suy ra nếu cực tiểu (2) đạt tại việc (i, j) thì việc (i,j) không có thời gian sự trữ riêng gốc (Dgij = 0).

Nếu cực tiểu (2) không đạt tại việc (i, j ) thì Tmi < T

m j − tij ⇔ D

g ij > 0, tức là việc (i, j) có thời gian dự trữ

riêng gốc. Trong trường hợp này thời gian tij hoặc thời gian khởi công của việc (i, j) có thể xê dịch trong phạm vị Dgij mà không làm

ảnh hưởng gì đến thời điểm hoành thành muộn nhất của mọi việc liền kề trước nó.

Thời gian dự trữ riêng ngọn của việc (i, j) được kí hiệu và xác định như sau

Dnij = T s j − tij − T

s i (18a)

⇔ T sj = T s i + tij + D

n ij (18b)

Từ (1) và (18b) nếu cực đại (1) đạt được tại việc (i, j) thì việc (i, j) không có thời gian việc riêng ngọn (Dnij = 0). Nếu cực đại (1) không đạt tại việc (i, j) thì T Sj > T

s i + tij ⇔ D

n ij > 0 tức là việc (i, j) có thời gian dự trữ riêng

ngọn. Trong trường hợp này, thời gian Tij hoặc thời điểm hoàn thành của việc (i, j) có thể thay đổi trong phạm vi của Dnij mà không làm ảnh hưởng gì dến thời điểm sớm nhất hoàn thành sự kiện ngọn tức là không làm ảnh hưởng đến thời điểm khởi công sớm nhất của mọi việc liền kề sau nó.

Thời gian dự trữ riêng

Thời gian dự trữ riêng của công việc (i , j) là khoảng thời gian xê dịch tối đa của công việc (i, j) mà không làm ảnh hưởng đến thời điểm hoàn thành muộn nhất của sự việc gốc và thời điểm hoàn thành muộn nhất hoàn thành các công việc liền kề trước nó và thời điểm sớm nhất khởi công các công việc liền kề sau nó. Kí hiệu thời gian dự trữ riêng của công việc (i , j) là Dij khi đó ta có D rij = min{D

g ij ,D

n ij}.

Chú ý Ta có thể mở rộng các chỉ tiêu Dgij ,D n ij ,Dij cho cả các việc

không găng độc lập: Dgij = D n ij = D

r ij = D

c ij và được kí hiệu chung

là Dij . Ví dụ : Tính các chỉ tiêu Dgij ,D

n ij = D

r ij cho các việc không găng.

Thời gian dự trữ riêng

Dg 12

= 17− 6− 0 = 11; Dn12 = 6− 6− 0 = 0

⇒ D r12 = 0.

Dg 15

= 15− 5− 0 = 10; Dn15 = 15 − 5− 0 = 10

⇒ D r15 = 10.

Dg 24

= 22− 4− 17 = 1; Dn24 = 10 − 4− 6 = 0

⇒ D r24 = 0.

Dg 27

= 23− 6− 17 = 0; Dn12 = 12 − 6− 6 = 0

⇒ D r272 = 0.

Dg 36

= 15− 6− 7 = 2; Dn36 = 13− 6− 7 = 0

⇒ D r36 = 0.

Dg 47

= 23− 0− 22 = 1; Dn47 = 12 − 0− 10 = 2

(19)

⇒ D r47 = 1.

Dg 48

= 27− 5− 22 = 0; Dn48 = 22− 6− 10 = 7

⇒ D r48 = 0.

Dg 58

= 27− 7− 15 = 5; Dn12 = 22− 7− 15 = 0

⇒ D r58 = 0.

Dg 69

= 15− 0− 15 = 0; Dn69 = 15− 0− 13 = 2

⇒ D r69 = 0.

Dg 6,10

= 24− 5− 15 = 4; Dn6,10 = 24− 5− 13 = 6

⇒ D r6,10 = 4.

Dg 7,11

= 32− 9− 23 = 0; Dn7,11 = 32− 9− 12 = 11

⇒ D r7,11 = 0.

Dg 8,11

= 32− 5− 27 = 0; Dn8,11 = 32− 5− 22 = 5

⇒ D r8,11 = 0.

Đường gần găng và hệ số găng

Trong khi chỉ đạo thi công nhằm rút ngắn thời hạn hoàn thành toàn bộ công trình. Có những đường đi mà độ dài của nó chỉ ngắn hơn độ dài đường găng chút ít. Khi tập trung nhân lực, tài nguyên vào những đường găng thì đường găng cũ nhanh chóng mất và đường găng mới nhanh chóng xuất hiện từ những đường gần găng. Do đó người tổ chức thi công phải nhanh chóng thay đổi kế hoạch, tập trung nhân lực, tài nguyên thay vì phải điều chỉnh kế hoạch nhiều lần, người tổ chức thi công lập phương án tập trung nhân lực, tài nguyên cho cả những việc trên đường găng và trên đường gần găng. Cho một số D0 > 0 ( đơn vị thời gian), khi đó việc không găng (i, j) thỏa mãn 0 < Dij ≤ D0 được gọi là việc gần găng với độ lệch không quá D0. Gọi I(i, j) là độ dài đường đi dài nhất từ sự kiện I qua công việc (i, j) đến sự kiện n, kí hiệu đường đi này là µ. i(g) độ dài đường găng. Khi đó việc (i, j) là việc gần găng với độ lệch không qua D0 khi và chỉ khi 0 < I (g)− I (i , j) ≤ D0. Khi đó µ được gọi là việc gần găng với độ lệch không quá D0.

Hệ số găng

Hai việc (i, j) và (k, r) có thời gian dự trữ chung như nhau, mức độ khẩn trương của hai việc này không hẳn đã như nhau. Để đặc trưng cho mức độ khẩn trương của một công việc không găng ta đưa ra khảo sát một chỉ tiêu mới được gọi là hệ số găng. Hệ số găng của một việc (i, j) kí hiệ là hij là tỷ số lớn nhất giữa độ dài của đoạn đường trên đương đi dài nhất từ sự kiện I qua công việc (i, j) đến sự kiện n mà đoạn đó không nằm trên đường găng và độ dài của đoạn đường găng không phụ thuộc vào đường đi dài nhất từ sự kiện i qua công việc (i, j) đến sự kiện n. Vì đường găng dài nhất nên 0 ≤ hij ≤ l với mọi (i , j) ∈ U, hij càng gần l thì mức độ khẩn trương càng lớn. Ví dụ: Xét việc (2, 4) suy ra đường đi dài nhất từ sự kiện I qua công việc (2,4) đến sự kiện 11 là {(1, 2); (2, 4); (4, 8); (8, 11)} đường đi này không có đoạn nào nằm trên đường găng cả độ dài là 20h.

h24 = 20 30

= 0, 625

Ví dụ

h6,10 = t36 + t6,10

t35 + t59 + t9,10 =

11 17

= 0, 647.

h1,2 = t12 + t24 + t48 + t8,11

t13 + t35 + t59 + t9, 10 + t10,11 =

20 32

= 0, 825.

h5,8 = t58 + t8,11

t59 + t9, 10 + t10,11 =

12 17

= 0, 706.

h15 = 5 15 ≈ 0, 333

Ví dụ

Ví dụ: Một công trình xây dựng gồm một số các công việc chính sau : Việc x1 làm trong 40 ngày bắt đầu ngay. Việc x2 làm trong 50 ngày bắt đầu ngay. Việc x3 làm trong 80 ngày sau x2 hoàn thành. Việc x4 làm trong 50 ngày sau x1 hoàn thành. Việc x5 làm trong 60 ngày sau x3 hoàn thành. Việc x6 làm trong 40 ngày sau x2 hoàn thành. Việc x7 làm trong 80 ngày sau x1, x3, x6 hoàn thành. Việc x8 làm trong 40 ngày sau x1, x3, x6 hoàn thành. Việc x9 làm trong 10 ngày sau x7, x4 hoàn thành. Việc x10 làm trong 60 ngày sau x4 hoàn thành. Việc x11 làm trong 50 ngày sau x5, x8 hoàn thành. a) Lập sơ đồ mạng lưới mô tả quá trình thi công các công việc trên. b) Tính các chỉ tiêu thời gian cho các sự kiện và các công việc và xác định, tính độ dài đường găng. Tính hệ số găng cho các việc x4, x6, x8

Ví dụ

Giải: a) Sơ đồ mạng lưới được lập như Hình vẽ 16.

4

12090

0 0 0

0 0

0

0

0

0

0

5050 130130

130 130

13040

1

3 5 190

8

70 190

240 240 9

210210 7

6

2

X1 = 40

X2 = 50

21090 X4 = 50 X10 = 60

X7 = 80 X9 = 10

X8 = 40

X6 = 40

X3 = 80 X5 = 60

X11 = 50

Ví dụ

Đường găng G = {(1, 3); (3, 5); (5, 6); (6, 7); (7, 9)}. Độ dài đường găng l(g) = Tmn = 310. +) Tính hệ số găng của các việc x4, x6, x8.

Việc x4 : h4 = t12 + t24 + t47

t13 + t35 + t56 + t67 =

90 210

= 3 7 ≈ 0, 4286 .

Việc x6 : h36 = t36

t35 + t56 =

40 80

= 0, 5.

Việc x8 : h68 = t68 + t89 t67 + t79

= 90 180

= 0, 5.

Ví dụ

Giải: a) Sơ đồ mạng lưới được lập như Hình vẽ 17. b) Để tính các loại thời gian dự trữ của các việc ta phải có chỉ tiêu thời gian cho các sự kiện.

4

1 0

0 0

2 2

004

6 6

23 17

15 14

29

8

1717 75

15 156 10

3

0 0a1 = 5

a2 = 6

a5 = 8 a6 = 7

a8 = 4

a10 = 7 a12 = 9

a7

a4 = 5

Ví dụ

Tên công việc Dcij D g ij D

n ij D

r ij hij

(i, j)

(1, 2) 4 4 0 0 Dcij = T m j − tij − T

s i

(1, 3) 0 0 0 0

(1, 4) 18 18 1 1 Dgij = T m j − tij − T

m i

(2, 4) 17 13 0 0

(2,5) 4 0 4 0 Dnij = T s j − tij − T

s i

(3, 5) 0 0 0 0

(3, 7) 5 5 5 5 D rij = min{D g ij ,D

n ij}

(3, 8) 6 6 6 6

(4,6) 17 0 3 0

(5, 6) 14 14 0 0

(5, 7) 0 0 0 0

Ví dụ

h12 = h25 = t12 + t25 t13 + t35

= 1 15 ≈ 0, 733.

h14 = t14 + t46 + t69

t13 + t35 + t57 + t78 + t89 =

15 33 ≈ 0, 445.

h24 = h46 t12 + t24 + t46 + t69

t13 + t35 + t57 + t78 + t89 =

16 33 ≈ 0, 4848.

h37 = t37

t35 + t57 =

4 9

=≈ 0, 444.

h38 = t38

t35 + t57 + t78 =

10 16

=≈ 0, 625.

h56 = h69 t36 + t69

t57 + t78 + t89 =

4 18 ≈ 0, 2222.

h79 = t79

t78 + t89 =

8 16

= 0, 5.

Đường đẳng thời

Đường đẳng thời là một đường cong biểu thị thời điểm lấy số liệu theo dõi. Nó chia sơ đồ mạng ra thành hai phần. Phần bên trái gồm những công việc đã hoàn thành, còn phần bên phải là gồm những phần việc chưa làm (tính đến thời điểm này. Sau mỗi lần thực hiện việc lấy số liệu theo dõi, từ thực tế những việc còn lại, người phụ trách thực hiện cần kịp thời tổ chức rút kinh nghiệm và từ đó đề ra những thay đổi phù hợp về thời hạn, cơ cấu của các phần việc chưa làm. Ngoài ra có thể bổ sung những phần việc mới xuất hiện, bỏ đi những phần việc thực tế không cần nữa. Nghĩa là cùng với việc xác định đường đẳng thời thì ta vẽ lại ( phần sau) của sơ đồ mạng lưới cho đúng với yêu cầu mới đề ra. ( Để đỡ nhầm lẫn ta quy ước phần việc đã hoàn thành nằm bên trái đường đẳng thời sẽ được vẽ bằng các cung giả không có độ dài).

Ví dụ

Ví dụ: Một quy trình công nghệ được thể hiện qua sơ đồ mạng lưới sau: Hình vẽ 18

0 0

0 1

3 3

3

8 8

88

8

0 0

0 3030

7

5 2116

4

0

6 1313

5 16 17

1

2

X7 = 7

X8 = 8 X11 = 13

X10 = 9X9 = 8X2 = 7

X3 = 8

X12 = 7

X1 = 3 X4 = 5 X6 = 5 0

0

Ví dụ

_ Với sơ đồ mạng lưới ở Hình vẽ 18: _ Đường găng của sơ đồ có độ dài là 30. _ Các việc găng gồm :x1, x3, x4, x6, x12. Giả sử tại thời điểm t=5 ta lấy số liệu theo dõi và kết quả nhận được như sau: - Việc x1 đã hoàn thành. - Việc x2 đã hoàn thành được một phần, dự tính phần còn lại làm trong 3. -Việc x8 dự tính làm trong 10. Cơ cấu và thời hạn của các việc khác không đổi.

X4 = 5 X6 = 5

X10 = 9

X12 = 7

X1

X9 = 8

X5 = 5

1

2

4

6

7 8

Ví dụ

Tất nhiên ta không nên hiểu rằng đường găng luôn phải được rút ngắn hơn so với độ dài dự kiến ban đầu mà do cả những thay đổi và dự tính chưa sát nên độ dài đường găng có thể dài ra ( so với dự kiến ban đầu). Ta tìm cách rút ngắn cho nó gần sát với đường găng thực tế tối ưu. a) Rút ngắn thời hạn làm việc của các găng. Nhiều yếu tố thực tế ảnh hưởng tới biện pháp này trong đó gồm: Tính chất công việc, việc huy động nhân vật lực, biện pháp tổ chức và áp dụng tiến bộ khoa học kĩ thuật v.v... Tất nhiên việc rút ngắn này cần được tiến hành trong từng giai đoạn cụ thể. Với cùng một thời điểm khởi công sẽ có những việc găng xen kẽ lẫn những việc không găng. Khi tiến hành thực hiện thời hạn của một việc găng nào đó và tới một thời điểm nào đó một việc găng có thể trở thành không găng. Ngược lại có những việc thực tế trước đó dự tính là không găng thì nay lại trở thành găng.

Ví dụ: Ta xét sơ đồ mạng lưới Hình 18. Tại thời điểm xuất phát ban đầu dự tính thì hai việc x1, x3 là găng, việc x2 là không găng sau đó 3 đơn vị thời gian thì việc x4 là găng v.v... Nhờ việc áp dụng các biện pháp kĩ thuật tiên tiến và chỉ đạo thực hiện hiện tốt sau 5 đơn vị thời gian ta nhận được kết quả sau: - Việc x1 đã hoàn thành đúng tiến độ. -Việc x3 đã hoành thành (rút ngắn được 3 đơn vị). -Việc x2 đã hoành thành được một phần và dự tính thời hạn làm phần còn lại là 3 đơn vị thời gian. -Việc x4 đã hoành thành được một phần và dự tính thời hạn làm phần còn lại làm - trong 1 đơn vị thời gian. - Các việc còn lại chưa làm, cơ cấu và thời hạn không thay đổi.

Ví dụ

X7 = 7

X4 = 5 X6 = 5

X10 = 9

X12 = 7

X11 = 13

X2 = 2

X3 = 3

X1

X9 = 8

X8 = 10

X5 = 5

1

2

3

4

5

6

7 8

Figure:

Qua kết quả tính toán trên sơ đồ ta nhận thấy :

Nhận xét: Mặc dù thời hạn làm việc găng x3 đã rút ngắn được 3 đơn vị thời gian, còn thời hạn của hai việc găng x1, x4 rút ngắn được 2 đơn vị thời gian nhưng độ dài đường găng chỉ được rút ngắn so với dự tính ban đầu là 1 đơn vị thời gian. Điều này là theo dự kiến ban đầu Dcx2 = 1. Và ta đã tận dụng hết thời hạn dự trữ chung của x2. Điều này gợi cho ta thấy khi thực hiện việc rút ngắn thời hạn của các việc găng cần lưu ý tới các việc không găng có cùng thời điểm khởi công. Trái lại những việc không găng đó mà tiến hành chậm trễ thì việc rút ngắn thời hạn của việc găng không có ý nghĩa gì nữa. Một điểm cần lưu ý là: Với những sơ đồ có nhiều đường găng thì nếu có thể được các đường găng nên đồng thời được rút ngắn như nhau. Nếu không từ chỗ nhiều đường găng sẽ do việc rút ngắn thời hạn của một vài việc găng nào đó mà số đường găng sẽ ít đi. b) Thay đổi lại cơ cấu của sơ đồ mạng lưới. Nếu sử dụng những biện pháp kĩ thuật tiên tiến ta chủ động thay đổi được cơ cấu của các công việc (thay đổi trình tự tiến hành thì độ dài của đường găng của sơ đồ được rút ngắn mặc dù thời hạn làm của các việc không cần rút ngắn).

Ví dụ

Ví dụ: Từ sơ đồ mạng lưới của Hình 19. Giả sử sau 5 đơn vị thời gian nữa ta lại lấy số liệu theo dõi và kết quả nhận được như sau: - Việc x1, x2.x3, x4, x5 đã hoàn thành. -Việc x7 đã hoàn thành được một phần và dự tính thời hạn làm phần việc còn lại là 3. Dự tính thời hạn làm của hai việc x11 là 10x12 là 18. - Xuất hiện thêm việc mới x13 làm sau x9 và trước x11 có thời hạn làm là 2. Như vậy x11 được làm sau khi các công việc x7, x8, x13 hoàn thành. - Cơ cấu và thời hạn của các việc khác không thay đổi.

Ví dụ

Đường đẳng thời và sơ đồ được vẽ lại như sau:

X7 = 3

X4 X6 = 5

X10

X12 = 18

X11 = 10

X2

X3

x1

X9 = 8

X8 = 10

X5 = 5

1

2

3

4

7

6

5 8

X13 = 2

Ví dụ

Nhằm rút ngắn độ dài đường găng giả sử nhờ biện pháp kỹ thuật nào đó mà khi làm việc x12 ta không cần chờ việc x6 nữa. Thời hạn và cơ cấu của các việc khác còn lại không thay đổi. Khi đó sơ đồ được vẽ lại là:

X4 X6 = 5

X10

X12 = 18

X2

X

x1

X9 = 8

X8 = 10

X5 = 5

1

2

4

6

5 8

X13 = 2

0

Ni dung Ðinh nghıa và quy tc lp s mang li Các quy tc thc hành lp s mang li Các chi tiêu thi gian cua s mang li Thi im sm xut hin s kin Thi im mun xut hin s kin Thi im sm nht bt u công vic Thi im sm nht kt thúc công vic Thi im mun nht kt thúc công vic Thi im mun nht bt u công vic Thi gian d tr chung cua công vic Ðng gang Cách xác inh ng gang Thi gian d tr cua các vic không gang liên quan. Thi gian s tr riêng gc Thi gian d tr riêng ngon Thi gian d tr riêng Ðng gn gang và h s gang Ðng gn gang H s gang Ðng ng thi và bin pháp rút ngn ng gang Khái nim ng ng thi. Các bin pháp rút ngn dài ng gang.

Đơn vị chủ quản: CÔNG TY TNHH THƯƠNG MẠI ĐIỆN TỬ THIÊN THI
Địa chỉ: 41-43 Trần Cao Văn, P6, Q3, HCM
giấy phép MXH: 102/GXN - TTĐT