Phương Pháp Sơ đồ Mạng Lưới (pert) - Tài Liệu Text - 123doc

Tải bản đầy đủ (.pdf) (50 trang)

1. Trang chủ
>>
2. Kinh Tế - Quản Lý
>>
3. Quản lý dự án

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

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (617.9 KB, 50 trang )

PHƯƠNG PHÁP SƠ ĐỒ MẠNG LƯỚIKỹ thuật đánh giá và kiểm tra dự án PERT (Program Evatuationand Review Technique).Mục tiêu chính của phương pháp: đánh giá khả năng hoàn thànhdự á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ệcnà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 chotoà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 saocho 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ớitoàn bộ dự án.Định nghĩa và quy tắc lập sơ đồ mạng lướiDefinitionMột tập hợp các điểm (ta gọi là các đỉnh, kí hiệu A) và tập hợpcá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ạimỗ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ấtkỳ, đi theo chiều các mũi tên, không bao giờ quay về điểmxuấ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ởicông và có một đỉnh chỉ toàn các cung đi vào được gọi là đỉnhkhá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ướiijFigure: Đây là gì?Các quy tắc thực hành lập sơ đồ mạng lướiQuy tắc 1: Nếu một nhóm nhiều công việc cùng bắt đầu từ mộtsự kiện i và cùng kết thúc tại một sự kiện j thì không được biểudiễ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ônglà tách rời nhau ra được thì gộp chúng lại thành một cung duynhấ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à kcung (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.abij2aCác quy tắc thực hành lập sơ đồ mạng lướiQuy tắc 2: Nếu một nhóm các công việc lập thà nh một mạng controng một sơ đồ mạng lưới (các công việc và các sự kiện của nhómnày không phụ thuộc gì vào và không ảnh hưởng đến các công việccủa nhóm khác của sơ đồ mạng lưới trừ sự kiện đầu tiên và sự kiệncuối cùng của nhóm này) thì ta có thể gộp mạng con đó lại thànhmột cung duy nhất nếu việc gộp đó không làm cho sơ đồ mạng lướitrở nên quá thô (Hình 3a) chuyển sang Hình 3b. Cung (2, 4) trongHình 3b mô tả cả 3 công việc a, b, c trong sơ đồ mạng lưới 3a.154323aCác quy tắc thực hành lập sơ đồ mạng lướiQuy tắc 3: Nếu một nhóm các công việc liên hệ với nhau theotrậ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 4avà Hình 4b đều sai, mà phải biểu diễn như Hình 4c.abcdeabedcCác quy tắc thực hành lập sơ đồ mạng lướiQuy tắc 4: Nếu một nhóm công việc liên hệ với nha u theo trật tự:Việc a sau việc bViệc c sau việc dViệc e sau việc b, dThì biểu diễn như Hình 5dabecFigure:Các quy tắc thực hành lập sơ đồ mạng lướiQuy 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 6bmới đúng.ijxabcd6aCác quy tắc thực hành lập sơ đồ mạng lướiQuy tắc 6:a) Nếu có một đỉnh không phải đỉnh khởi công mà chỉ toàn nhữngcung đ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.134521345227a7bQuy tắc đánh số các sự kiện1Cho sự kiện khởi công toàn bộ mang số 1 và xếp nó vào lớpthứ nhất.2Xó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 3Xóa tượng trưng các sự kiện của lớp thứ i cùng các cung rakhỏi các sự kiện thuộc lớp i, nhặt ra các sự kiện chỉ toànnhữ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 ớpthứ 1; các đỉnh thuộ c cùng một lớp được đánh số tùy ý. Đỉnhkhở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ướiKí hiệu thời điểm sớm xuất hiện sự kiện j là Tsj∀ j ∈ A, được địnhnghĩa như sau: Ta biết rằng sự kiện j là xuất hiện nếu mọi côngviệc ứng với các cung đi tới sự kiện j đã hoàn thành. Vì vậy đối vớisự kiện 1 là s ự kiện khởi công toàn bộ, trước đó chưa có công việcnào hoàn thành nên Ts1= 0.Ts1= 0;Tsj= max{Tsi+ tij∀ (i, j) ∈ U−j}trong đó U−jlà tập hợpcá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àythi công sớm nhất có thể được thứ tự là 19 và 16 cũng xét nhưvậy ta được:Tsj= 27 = max{Tsj+ tij| ∀ (i, j) ∈ U−j} (1)Tsj= 18 (2)Thời điểm sớm xuất hiện sự kiệni1i2i3jti1j= 6ti2j= 8ti3j= 10TSj=?Figure:trong đó U−j= {(i1, j), (i2, j), (i3, j)}- tập hợp các công việc ứngvớ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 Tsjlà độ dàiThời điểm muộn xuất hiện sự kiệnKí 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ếusự kiện i xuất hiện muộn hơn thời điểm Tmithì thời gian hoànthành toàn bộ công trình bị kéo dài. Ta có định nghĩa:DefinitionTmn= Tsn; (4)Tmi= minj{Tmj− tij| ∀ (i, j) ∈ U+j} (5)trong đó U+jlà 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 ớicác cung ra khỏi i mới bắt đầu được.i1Tmj1=Thời điểm muộn xuất hiện sự kiệnMộ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 a1làm trong 6hbắt đầu ngay.Công việc a2làm trong 4hsau a1hoàn thành.Công việc a3làm trong 5hbắt đầu ngay.Công việc a4làm trong 7hbắt đầu ngay.Công việc a5làm trong 6hsau a1hoàn thành.Công việc a6làm trong 8hsau a4hoàn thành.Công việc a7làm trong 6hsau a4hoàn thành.Công việc a8làm trong 9hsau a3, a6, a7hoàn thành.Công việc a9làm trong 7hsau a3, a6hoàn thành.Công việc a10làm trong 9hsau a2, a5hoàn thành.Công việc a11làm trong 5hsau a2hoàn thành được 5hvà sau a9hoàn thành.Công việc a12làm trong 5hsau a7hoàn thành.Công việc a13làm trong 8hsau a8, a12hoàn thành.Ví dụ2714536910118a1a3a4a6a2a500a8a12a1150a10a13a9Figure:Ví dụGiải:Ts1= 0Ts2= max{Ts1+ t1,2} = 0 + 6h= 6hTs3= max{Ts1+ t1,3} = 0 + 7h= 7hTs4= max{Ts2+ t2,4} = 6h+ 4h= 10hTs5= max{Ts1+ t1,4, Ts3+ t3,5}= max{0h+ 5h, 7h+ 8h} = 15h.Ts6= max{Ts3+ t3,6} = 7h+ 6h= 13hTs7= max{Ts2+ t2,7, Ts4+ t4,7}= max{6h+ 6h, 10h+ 0h} = 12h.Ts8= max{Ts4+ t4,8, Ts5+ t5,8}= max{10h+ 5h, 15h+ 7h} = 22h.Ts9= max{Ts5+ t5,9, Ts6+ 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= Ts11= 32h.Tm10= min{Tm11− t10,11= 32h− 8h= 24h}.Tm9= min{Tm10− t9,10} = 24h− 9h= 15h.Tm8= min{Tm11− t8,11} = 32h− 5h= 27h.Tm7= min{Tm11− t7,11} = 32h− 9h= 23h.Tm6= min{Tm10− t6,10, Tm9− t6,9}= min{24h− 5h, 15h− 0h} = 15h.Tm5= min{Tm9− t5,9, Tm8− t5,8}= min{15h+ 0h, 27h− 7h} = 15h.Tm4= min{Tm8− t4,8, Tm7− t4,7}= min{27h− 5h, 23h− 0h} = 22h.Tm3= min{Tm6− t3,6, Tm5− t3,5}h h h h hVí dụ1inl(i)l(γi)TmnDi= Tmn[l(i) + l(Figure:DefinitionSự 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= TsiTrong ví dụ ở tiểu mục 2) các sự kiện 1, 3, 5, 9, 10, 11 là nhữngsự 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ôngviệcKí hiệu Tksijlà 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ôngviệc (i, j) mới bắt đầu được (i < n) nênTksij= Tsi(6)Kí hiệu thời điểm sớm nhất kết thúc công việc (i, j)Thsij∀ (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 thicông tijnên:Thsij= Tksij+ tij∀ (i, j) ∈ U. (7)Tử (6) và (7) ta suy ra:Thsij= Tsi+ tij∀ (i, j) ∈ U. (8)Thời điểm muộn nhất kết thúc công việcKí hiệu thời điểm muộn nhất kết thúc công việc (i, j) làThmij∀ (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) ∈Ujđều đã hoàn thành, vì vậy công việc (i, j) không đượcphép kết thúc muộn hơn Tmj. Do đó :Thmij= Tmjvớ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àTkmij∀ (i, j) ∈ U. Cũng lập luận như việc lập công thức (7) ta có:Tkmij= Thmij− tijvới mọi (i, j) ∈ U. (10)Từ (9) và (10) suy raTkmij= Tmj− tijvới mọi (i, j) ∈ U. (11)Thời gian dự trữ chung của công việcDefinitionThời gian sự trữ chung của công việc (i, j), được kí hiệu và xácđịnh như sau:Dcij= Tkmij− Tksijvới mọi (i, j) ∈ U. (12)Từ (6) và (11) ta có:Dcij= Tmj− tij− Tsivới mọi (i, j) ∈ U. (13)theo (8) và (9) ta có:Dcij= Thmij− Thsijvới mọi (i, j) ∈ U. (14)Từ công thức (14) suy raThmij− Thsij= Tkmij= Dcijvới mọi (i, j) ∈ U.Thay (3) và (??) vào (13) ta đượcDcij= Tmn− [l(i) + tij+ l(γj)] với mọi (i, j) ∈ U. (15)Nhận xét: Tổng l(i+ 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 Dcijlà chênhlệch giữa hai đường đi dài nhất: đường đi dài nhất không điều kiệnvà đường đi dài nhất có điều kiện (qua công vi ệc (i, j)).1inl(γi)Dcij= Tmn− [l(i+ ti,k) + l(γi)]il(i)tijtmnFigure: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ờigian dự trữ chung tức là Dcij= 0.Đường găngDefinitionĐườ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= Tsn.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ệngăng⇔ Di= 0 ⇔ Tmn= l(i) + 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 Tmnthì đườ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ăngTừ đị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 đếnsự 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ểudiễn mỗi sự kiện bởi một vòng tròn chia làm 4 phầniTsiTmiDiFigure: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ũitên kép :ijDCijFigure:Để khảo sát sơ đồ mạng lưới sâu hơn ta phân tích các việc khônggă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ểudiễn sự kiện i găng:iTsiTmi0iTsiTmi0tijDij

Tài liệu liên quan

• Phương pháp sơ đồ đường chéo
  • 4
  • 845
  • 30
• Sử dụng phương pháp sơ đồ đường chéo
  • 15
  • 734
  • 0
• Giải nhanh bài toán hóa học bằng phương pháp “sơ đồ đường chéo”
  • 3
  • 1
  • 9
• Nghiên cứu đề xuất phương pháp tối ưu mạng lưới cấp nước phường thọ quang, thành phố đà nẵng
  • 13
  • 737
  • 1
• ử dụng phương pháp sơ đồ đường chéo để nhẩm nhanh một số bài toán hóa học
  • 3
  • 741
  • 9
• áp dụng phương pháp sơ đồ mạng lưới trong quy trình xuất hàng tại kho b1 công ty xăng dầu phú thọ
  • 96
  • 1
  • 3
• Phương pháp sơ đồ hệ thanh
  • 59
  • 645
  • 1
• điều hành dự án bằng phương pháp sơ đồ mạng lưới (phương pháp pert-cpm)
  • 102
  • 2
  • 1
• phương pháp số đo dường chéo
  • 7
  • 354
  • 0
• phương pháp sơ đồ mạng lưới (pert)
  • 50
  • 14
  • 5

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(617.9 KB - 50 trang) - phương pháp sơ đồ mạng lưới (pert) Tải bản đầy đủ ngay ×