›
›

Bài giảng Khoa học quản lý ứng dụng - Chương 5: Kỹ thuật mạng trong quản lý - Huỳnh Đỗ Bảo Châu

pdf 24 trang ngocly 3860
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Khoa học quản lý ứng dụng - Chương 5: Kỹ thuật mạng trong quản lý - Huỳnh Đỗ Bảo Châu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_khoa_hoc_quan_ly_ung_dung_chuong_5_ky_thuat_mang_t.pdf

Nội dung text: Bài giảng Khoa học quản lý ứng dụng - Chương 5: Kỹ thuật mạng trong quản lý - Huỳnh Đỗ Bảo Châu

  1. 2/12/2017 TRƯỜNG ĐẠI HỌC NGÂN HÀNG TP.HCM Nội dung chính KHOA HỆ THỐNG THÔNG TIN QUẢN LÝ PHẦN1:KỸ THUẬTMẠNG KHOA HỌC QUẢN LÝ ỨNG DỤNG 1. Giới thiệuvề kỹ thuậtmạng 2. Bài toán tìm đường ngắnnhất 3. Giải bài toán tìm đường ngắnnhấtbằng Excel 4. Bài toán cây bao trùm tối thiểu 5. Bài toán luồng cực đại CHƯƠNG 5 6. Giải bài toán tìm luồng cực đạibằng Excel KỸ THUẬT MẠNG TRONG QUẢN LÝ GV. ThS. Huỳnh Đỗ Bảo Châu 1 2GV. Huỳnh Đỗ Bảo Châu Nội dung chính PHẦN2:KỸ THUẬTMẠNG TRONG QUẢNLÝDỰ ÁN 7. Các thành phầncủaquảnlýdự án PHẦN 1 8. Biểu đồ Gantt 9. CPM / PERT KỸ THUẬT MẠNG 10.Xác suấtthờigianhoạt động 11. Thiếtlậpsơđồmạng bằng MS Project 12. Điềuchỉnh sơđồmạng theo thờigian 1. Giới thiệu về kỹ thuật mạng 13. Chuyển đổimôhìnhmạng CPM/PERT sang Mô hình quy hoạch tuyếntính 3GV. Huỳnh Đỗ Bảo Châu 4 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 1
  2. 2/12/2017 Khái niệm mạng (network) Các thành phần của mạng  Mạng là sự sắpxếpcácđường dẫnkếtnốitạicácđiểm  Nút (nodes): biểudiễnbằng vòng tròn, đạidiệnchocácđiểmgiaonhau khác nhau, thông qua đócáchạng mục(items)được nối các nhánh.  Nhánh (branches): đạidiệnlàđường thẳng, kếtnốicácnútvàhiểnthị di chuyển. dòng chảytừđiểmnàyđến điểmkhác.  Ứng dụng mạng rấtphổ biến vì chúng cung cấpmột  Giá trịđạidiệnchokhoảng cách, độ dài củathờigian,chiphíhoặc bứctranhcủahệ thống và hệ thống lớncóthể dễ dàng đượcgánchomỗinhánh. mô hình hóa như các mạng.  Mục đích củamạng là xác định khoảng cách ngắnnhất, độ dài thời gian ngắnnhất, hoặcchiphíthấpnhấtgiữacácđiểmtrongmạng.  Mô hình dòng chảymạng (network flow models) mô tả dòng chảycáchạng mục (items) thông qua hệ thống. Mạng lưới đường sắt có 4 node, 4 nhánh Nút 1 (atlanta) là nút gốc 5 GV. Huỳnh Đỗ Bảo Châu 6 GV. Huỳnh Đỗ Bảo Châu Đường đi ngắn nhất (shortest route)  Đường ngắnnhấtlàkhoảng cách ngắnnhấtgiữamột node gốc(điểmxuấtphát)vàcácđiểm đến.  Bài toán tìm đường ngắnnhất đượcgiảiquyếtbằng cách sử dụng các kỹ thuậtgiải trình ngắnnhất 2. Bài toán tìm đường ngắn nhất 7 GV. Huỳnh Đỗ Bảo Châu 8 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 2
  3. 2/12/2017 Giải pháp tìm đường ngắn nhất Ví dụ minh họa 1. Chọn nút với đường đitrựctiếpngắnnhấttừ nút gốc. Tìm đường đi nhanh nhất để công ty vận chuyểnStagecoach Shipping đitừ Los Angeles đến sáu thành phố có thờigiandi 2. Thiếtlậpmộttậpvĩnh viễnvới các nút gốcvàcác chuyển(giờ)như hình. Xác định tuyến đường đi có thờigianngắnnhấttừ nút đượcchọn ở bước1. node 1 đến6 node cònlại 3. Xác định tấtcả các nút đượckếtnốitrựctiếp đến các nút trong tậpvĩnh viễn. 4. Chọn nút vớicáctuyến đường ngắnnhất(nhánh)từ nhóm các nút đượcnốitrựctiếp đến các nút trong tậpvĩnh viễn. 5. Lặplạibước3và4chođếnkhitấtcả các nút đã tham gia vào tậpvĩnh viễn. 9 GV. Huỳnh Đỗ Bảo Châu 10 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt) Ví dụ minh họa (tt)  Xét từ node 1 – nằm trong tập vĩnh viễn  Xét từ node {1,3} – nằm trong tập vĩnh viễn Node 3 đưa vào tập vĩnh viễn {1,3} Node 2 đưa vào tập vĩnh viễn {1,2,3} 11 GV. Huỳnh Đỗ Bảo Châu 12 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 3
  4. 2/12/2017 Ví dụ minh họa (tt) Ví dụ minh họa (tt)  Xét từ node {1,2,3} – nằm trong tập vĩnh viễn  Xét từ node {1,2,3,4} – nằm trong tập vĩnh viễn Node 4 đưa vào tập vĩnh viễn {1,2,3,4} Node 6 đưa vào tập vĩnh viễn {1,2,3,4,6} 13 GV. Huỳnh Đỗ Bảo Châu 14 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt) Ví dụ minh họa (tt)  Xét từ node {1,2,3,4,6} – nằm trong tập vĩnh viễn  Xét từ node {1,2,3,4,5,6} – nằm trong tập vĩnh viễn Node 5 đưa vào tập vĩnh viễn {1,2,3,4,5,6} Node 7 đưa vào tập vĩnh viễn {1,2,3,4,5,6,7} 15 GV. Huỳnh Đỗ Bảo Châu 16 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 4
  5. 2/12/2017 Ví dụ minh họa (tt)  Kết luận của bài toán: 3. Giải bài toán tìm đường ngắn nhất bằng Excel 17 GV. Huỳnh Đỗ Bảo Châu 18 GV. Huỳnh Đỗ Bảo Châu Giải pháp trên Excel Ví dụ minh họa  Chuyển đổi bài toán tìm mạng lướingắnnhất thành mô Tìm đường đi nhanh nhất để công ty vận chuyểnStagecoach hình bài toán lậptrìnhtuyếntínhvớicácsố nguyên 0, 1. Shipping đitừ Los Angeles đến sáu thành phố có thờigiandi chuyển(giờ)như hình.  Xây dựng mô hình lậptrìnhtuyếntính:  Biếnquyết định củatừng nhánh trong mạng: 0 ế á ư ộ ế ả đườ ắ ấ Xác định tuyến đường đi có thời gian ngắn nhất từ 1 ế á ộ ế ả đườ ắ ấ node 1 đến 6 node còn lại  Giảđịnh dòng chảychỉđitừ node nhỏđếnnodelớnhơn.  Hàm mụctiêu: ∑ (K là giá trị thờigian,khoảng cách, chi phí củanhánhi–j)  Ràng buộcchomỗi nút: bấtcứ node nào cũng phãi có 1 đường ra bảotồndòngchảy.  Sử dụng Solve để giải bài toán QHTT trên  Đọckếtquả dựatrêncácgiátrị biếnxij =1 19 GV. Huỳnh Đỗ Bảo Châu 20 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 5
  6. 2/12/2017 Ví dụ minh họa (tt) Ví dụ minh họa (tt)  Mô hình hoàn chỉnh bài toán:  Biến quyết định với , ∈ 1,7  Hàm mục tiêu:  Hàm mục tiêu: 16 9 35 12 25 15 22 16 9 35 12 25 15 14 17 19 8 14 22 14 17 19 8 14  Ràng buộc:  Ràng buộc: 1 0  Ở node 1 bắt buộc phải có 1 hướng ra (1-2, 1-3, 1-4): 0 1 0  Ở node 2, xe phải qua nhánh 1-2 và đi theo 2-4, hay 2-5: 0 → 0 0 1  Thực hiện tương tự ràng buộc cho các nút 3,4,5,6, 7 0 1 21 GV. Huỳnh Đỗ Bảo Châu 22 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt)  Trong Solve / Options: bỏ chọn “Ignore Integer Constraints” 4. Bài toán cây bao trùm tối thiểu (The Minimal Spanning Tree Problem) 23 GV. Huỳnh Đỗ Bảo Châu 24 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 6
  7. 2/12/2017 Cây bao trùm tối thiểu Giải pháp tìm cây bao trùm tối thiểu  Vấn đề cây bao trùm tốithiểulàkếtnốitấtcả các nút 1. Chọnbấtkỳ nút bắt đầu (thông thường, nút 1 được trong mạng để tổng chiều dài nhánh đượcgiảmthiểu. chọn).  Kếtquả bài toán sẽ cho đường dẫnmạng (Kếtnối) tất 2. Chọn nút gầnnhấtvới nút bắt đầu tham gia vào cây cả các điểmtrongmạng là đường đingắnnhất(hoặc bao trùm. chiềudàingắnnhất). 3. Chọn nút gầnnhấtchưa tham gia trong cây bao trùm. 4. Lặplạibước3chođếnkhitấtcả các nút đãtham gia cây bao trùm. 25 GV. Huỳnh Đỗ Bảo Châu 26 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa Ví dụ minh họa (tt)  Công ty truyền hình cáp Metro cài đặt1hệ thống cáp truyền hình trong cộng đồng gồm8khuvựcngoạiô.  Mỗi nhà trong 8 vùng ngoạiôphải đượckếtnốivớihệ thống cáp chính.  Công ty muốntìmmộtgiảipháplắp đặt đường trụccápchínhđi đến 8 vùng để tổng chiềudàicủadâycápsử dụng là ngắnnhất.  Khoảng cách giữa các vùng đượcmôtả trong hình sau: Nhánh từ vùng 1 đến vùng 2 cần 16.000 m dây cáp 27 GV. Huỳnh Đỗ Bảo Châu 28 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 7
  8. 2/12/2017 Luồng cực đại  Vấn đề luồng cực đạilàtối đa hóa số lượng dòng chảy từ nút gốc đến điểm đến.  Bài toán này có thểđượcápdụng trong các vấn đề thựctế như: 5. Bài toán luồng cực đại  dòng chảycủanước, khí đốt, hoặcdầuthôngquamạng (The Maximal Flow Problem) lượng các đường ống;  dòng chảycủagiấytờ trong cơ quan chính phủ;  dòng chảycủalượng lưuthôngtrongmạng lướigiaothông;  dòng chảysảnphẩmtronghệ thống dây chuyềnsảnxuất. 29 GV. Huỳnh Đỗ Bảo Châu 30 GV. Huỳnh Đỗ Bảo Châu Giải pháp tìm luồng cực đại Ví dụ minh họa 1. Tự ýchọnconđường nào trong mạng từ gốc đến đích.  Hệ thống đường sắtgiữa Omaha và Louis thể hiệntrong 2. Điềuchỉnh công suấttạimỗinútbằng cách trừđidòng hình bên dưới. Công ty Scott cầnchuyểncácbộ phậncủa chảytối đachocácconđường đãchọn ở bước1. xe lửatừ Omaha về Louis bằng đường sắt. Tuy nhiên, hợp đồng giớihạnsố toan xe lửacôngtycóthể sử dụng trên 3. Thêm dòng chảytối đatrênconđường theo hướng ngược lạitạimỗi nút. từng nhánh trong 1 tuần. 4. Lặplạicácbước1,2,và3chođếnkhikhôngcóđường nàocócôngsuấtlưulượng cao hơnlưulượng có sẵn. Từ nút 1 đến 2 có sẵn 6 xe, không có xe cho chiều ngược lại (nhánh có hướng) Từ nút 3 đến 4 có sẳn 2 xe, và 2 xe cho chiều ngược lại (nhánh vô hướng) 31 GV. Huỳnh Đỗ Bảo Châu 32 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 8
  9. 2/12/2017 Ví dụ minh họa (tt) Ví dụ minh họa (tt)  Chọn 1 đường đi ngẫu nhiên là : 1-2-5-6  Chọn 1 đường đi ngẫu nhiên là : 1-4-6  Sử dụng 4 xe  Sử dụng 4 xe Tổng lưu lượng xe qua mạng là 8 33 GV. Huỳnh Đỗ Bảo Châu 34 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt) Ví dụ minh họa (tt)  Chọn 1 đường đi ngẫu nhiên là : 1-3-6  Chỉ còn 1 đường đi là : 1-3-4-6  Sử dụng 6 xe  Sử dụng được thêm 1 xe Tổng lưu lượng xe qua mạng là 14 Tổng lưu lượng xe qua mạng là 15 35 GV. Huỳnh Đỗ Bảo Châu 36 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 9
  10. 2/12/2017 6. Giải bài toán tìm luồng cực đại bằng Excel 37 GV. Huỳnh Đỗ Bảo Châu 38 GV. Huỳnh Đỗ Bảo Châu Giải pháp trên Excel Giải pháp trên Excel (tt)  Chuyển đổi bài toán thành mô hình bài toán lậptrìnhtuyến  Xây dựng mô hình lậptrìnhtuyến tính (tt): tính và giảibằng Solve.  Hàm mụctiêu: ú ố ú đầ  Xây dựng mô hình lậptrìnhtuyếntính:  Ràng buộcchomỗi nút: bấtcứ node nào cũng phãi có 1  Biếnquyết định đạidiệnchodòngchảy trong các nhánh mạng: đường ra bảotồndòngchảy. (tương tự bài toán tìm  Để giảmkíchthướcvàđộ phứctạpcủaviệcxâydựng mô hình, loại đường ngắnnhất) bỏ dòng chảy trên cùng mộtnhánhtheohướng ngượclại.  Sử dụng Solve để giải bài toán QHTT trên.  Điềuchỉnh mạng để quy về bài toán tuyếntính:tạothêm1nhánhtừ nút cuốivề nút đầucógiátrị tên dòng chảybằng tổng giá trị dòng chảytừ nút đầuthôngquamạng đếnnútcuối(mục đích để tối đa hóa số lượng dòng chảytừ nút cuốivề nút đầu) 39 GV. Huỳnh Đỗ Bảo Châu 40 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 10
  11. 2/12/2017 Ví dụ minh họa Ví dụ minh họa (tt)  Hệ thống đường sắtgiữa Omaha và Louis thể hiệntrong  Biếnquyết định với , ∈ 1,6 hình bên dưới. Công ty Scott cầnchuyểncácbộ phậncủa  Hàm mụctiêu: xe lửatừ Omaha về Louis bằng đường sắt. Tuy nhiên, hợp đồng giớihạnsố toan xe lửacôngtycóthể sử dụng trên từng nhánh trong 1 tuần.  Ràng buộc:  Lưulượng dòng chảy6-1 chảyvàonode 1 bắtbuộcphảicó 1 hướng ra (1-2, 1-3, 1-4): → 0  Node 2, dòng chảy qua nhánh 1-2 và đi theo 2-4, hay 2-5: → 0  Thựchiệntương tự ràng buộc cho các nút 3,4,5,6  Các ràng buộclượng tối đacủatừng nháng dòng chảy. Từ nút 1 đến 2 có sẵn 6 xe, không có xe cho chiều ngược lại (nhánh có hướng) Từ nút 3 đến 4 có sẳn 2 xe, và 2 xe cho chiều ngược lại (nhánh vô hướng) 41 GV. Huỳnh Đỗ Bảo Châu 42 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt) Ví dụ minh họa (tt)  Hàm mục tiêu:  Ràng buộc: 43 GV. Huỳnh Đỗ Bảo Châu 44 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 11
  12. 2/12/2017 Ví dụ minh họa (tt)  Kết quả biểu diễn lưu lượng được sử dụng trên các nhánh (cột branch flow) PHẦN 2 KỸ THUẬT MẠNG TRONG QUẢN LÝ DỰ ÁN 7. Các thành phần của quản lý dự án 45 GV. Huỳnh Đỗ Bảo Châu 52 GV. Huỳnh Đỗ Bảo Châu Khái niệm Quy trình quản lý dự án  (1) Quảnlýdự án là việclậpkế hoạch, tổ chứcvàkiểm soát củamộtquátrìnhhoặchoạt động liên tục, phảnánh sự cam kếtvề sử dụng nguồn tài nguyên và con ngườicho các hoạt động vớimột khung thờigiannhất định.  (2) Quảnlýdự án (PM) là mộtnguyêntắccủalậpkế hoạch, tổ chức, bảovệ và quảnlýcácnguồnlực để mang về thành công củamụctiêudự án.  Bao gồm ba chính quy trình lậpkế hoạch, lịch trình, và kiểmsoát 53 GV. Huỳnh Đỗ Bảo Châu 54 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 12
  13. 2/12/2017 Kế hoạch dự án Cấu trúc phân chia công việc (WBS)  Bao gồm các phần:  Cấutrúcphânchiacôngviệclàmộtsơđồtổ chức phân rã  Mục tiêu (objectives) dự án thành các module (công việccon)để lậpkế hoạch.  Phạm vi / quy mô dự án (scope)  Các công việc được chia chi tiết thành các hoạt động,  Yêu cầu (contract requirements) nhiệmvụ cá nhân tạonên1cấu trúc phân cấp.  Lịch trình (schedules)  WBS giúp QLDA xác định:  Tài nguyên (resources)  Các nhiệmvụ cá nhân  Khốilượng công việccủadự án  Cá nhân (personnel)  Các nguồnlựccầnthiết  Điều khiển (control)  Mốiquanhệ giữa các module và các hoạt động  Vấn đề tiềm ẩn và rủi do (risk & problem)  Tránh trùng lặpkhôngcầnthiếtcáchoạt động  Cơ sở cho phát triểnkế hoạch quảnlýtiến độ dự án 55 GV. Huỳnh Đỗ Bảo Châu 59 GV. Huỳnh Đỗ Bảo Châu Cấu trúc phân chia công việc (WBS) WBS  Có 2 cách để phát triển WBS:  Từ trên xuống:  Bắt đầu từ đầu dự án  Câu hỏi “Các hoạt động nào giúp hình thành kết quả mức này ?”  Thực hiện đến mức chi tiết cuối cùng  Suy nghĩ cho toàn bộ dự án:  Suy nghĩ ra toàn bộ công việc của dự án  Sắp xếp chúng vào WBS theo xu hướng:  Cấp trên: các hoạt động tổng kết, hoạt động chính, hoặc chức năng (module) của sản phẩm dự án.  Các cấp thấp hơn: các hoạt động công việc chi tiết trong các hoạt động chính hoặc module. 60 GV. Huỳnh Đỗ Bảo Châu 61 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 13
  14. 2/12/2017 Lịch trình dự án (project schedule) Lịch trình dự án (project schedule)  Tậphợpcáchoạt động củadự án  Các bước phát triển lịch trình dự án:  Xác định công việc đòi hỏicáccôngviệckhácthực  Xác định các hoạt động phải được thực hiện để hoàn thành hiệntrướckhinóbắt đầu(quanhệưutiên) dự án.  Xác định trình tự các hoạt động theo thứ tự hoàn thành.  Xác định các yếutốảnh hưởng đếnthời gian hoàn thành dự án:  Ước tính thời gian cần thiết để hoàn thành mỗi hoạt động.  Phát triển các lịch trình dựa trên các ước tính trình tự và  Tài nguyên) thời gian của các hoạt động.  Mức độ chi tiếtcủacácmụctiêudự án  Các phương pháp định lượng thời gian trong lịch trình:  Đảmbảoyếutố thành công quan trọng nhấtcủadự án  Biểu đồ Gantt là “đúng thờigian”  CPM/PERT 63 GV. Huỳnh Đỗ Bảo Châu 64 GV. Huỳnh Đỗ Bảo Châu Biển đồ Gantt  Được phát triểnbởi Henry Gantt, mộtngườitiênphong trong lĩnh vựckỹ thuậtcôngnghiệpvàonăm 1914.  Là mộtkỹ thuậtquảnlýdự án truyềnthống để lậpkế hoạchcác dự án nhỏ có tương đối ít các hoạt động và các mốiquanhệưutiên. 8. Biểu đồ Gantt  Là một đồ thị dạng thanh vớimỗi thanh đạidiệncho1 hoạt động củadự án và chiều dài thanh tương ứng thời gian thựchiệnhoạt động đó.  Các hoạt động đượcphépchậmtrễ sẽ có 1 giá trị slack.  Slack là lượng thờigianmàmộthoạt động có thể bị trì hoãn mà không ảnh hưởng bấtkỳ hoạt động nào sau nó, và toàn bộ dự án. 67 GV. Huỳnh Đỗ Bảo Châu 68 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 14
  15. 2/12/2017 Biển đồ Gantt (tt) 9. CPM/PERT 69 GV. Huỳnh Đỗ Bảo Châu 70 GV. Huỳnh Đỗ Bảo Châu CPM/PERT CPM/PERT  Cả 2phương pháp đềudẫnxuấttừ Biểu đồ Gantt  AON PERT CPM (project evaluation and review (critical path method) technique) sử dụng ước tính nhiều giá trị thời gian hoạt sử dụng ước tính 1 giá trị thời gian hoạt động phản ánh sự thay đổi cho từng hoạt động cho từng hoạt động trong mạng, hoạt động trong mạng, hoạt động là đường giữa động là các nút (node) các nút (node) thời gian hoạt động được xem như là chắc thời gian hoạt động được xem như là 1 xác  AOA chắn. suất hoạt động được đại diện bởi các nút, và các hoạt động được đại diện là vòng cung, hoặc mũi tên cho thấy mối quan hệ ưu tiên (tức đường dây với các mũi tên, vòng tròn được là, hoạt động nào đến trước khác). gọi là nút Sơđồ mạng AON Sơđồ mạng AOA  Ưu điểm: sử dụng mộtmạng lưới(thayvìmột đồ thị) để hiểnthị các mốiquan hệ giữacáchoạt động ưutiên 71 GV. Huỳnh Đỗ Bảo Châu 72 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 15
  16. 2/12/2017 Quy tắc lập sơ đồ mạng Phương pháp mạng AOA (activity on arrow) 1. Sự kiện được đánh số từ nhỏđếnlớn theo hướng từ trái qua phải, từ trên xuống dưới. 2. Mỗisự kiệnphảicóhoạt động đếnvàhoạt động đi(ngoại trừ sự kiệnbắt đầuvàsự kiệncuối cùng). 3. Tấtcả hoạt động trong sơđồmạng phảihướng từ trái sang phải, không đượcquaytrở lạisự kiệnmàchúngxuất phát (không lập thành vòng kín) 4. Những hoạt động là riêng biệt, không đượckýhiệubởi cùng 1 số (không đượccùngsự kiệnbắt đầu&sự kiện kết thúc)  Nút tròn: được đánh số thứ tự, đạidiệnchocácsự kiện 5. Sơđồmạng cầncódạng đơngiảnnhất, không nên có (kết thúc 1, 1 số công việc để công việctiếp theo bắt đầu) quá nhiềuhoạt động giao cắt nhau.  6. Sơđồmạng phảiphảnánhđúng trình tự và mốiquanhệ Đường mũitên(nằmgiữa 2 nút): đạidiệnchohoạt động giữa các hoạt động. gồmtênhoạt động, thờigianthựchiện. 73 GV. Huỳnh Đỗ Bảo Châu 74 GV. Huỳnh Đỗ Bảo Châu Phương pháp mạng AOA (activity on arrow) Phương pháp mạng AON (activity on arrow)  Có 3 loạihoạt động:  Nút tròn: đạidiện cho hoạt động  Hoạt động thực: là hoạt động cầnnguồnlựcvàthờigian,biểudiễn  Đường mũitên(nằmgiữa2nút):diễn đạtmốiquanhệ giữa2hoạt bằng mũitênnétliền động.  Hoạt động giả danh (dummy): mộthoạt động giảđểđảmbảocác mốiquanhệưutiênnhưng không có nguồnlựcvàthờigianthực hiện, biểudiễnbằng mũitênnétđứt  Không cầncáchoạt động giả danh.  Hoạt động chờđợi: là hoạt động không cầnnguồnlựcmàchỉ cần thờigian,biểudiễnbằng mũitênnétliền.  Đượchỗ trợ xây dựng trong phầnmềm MS Project. 75 GV. Huỳnh Đỗ Bảo Châu 76 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 16
  17. 2/12/2017 Đường tới hạn (critical path) Đường tới hạn (critical path)  Đường tớihạnlàđường dài nhấttrongmạng; đólà thờigiantốithiểu để tấtcả hoạt động trong mạng có thểđược hoàn thành. 77 GV. Huỳnh Đỗ Bảo Châu 78 GV. Huỳnh Đỗ Bảo Châu Lịch trình hoạt động (activity schedule) Lịch trình hoạt động (activity schedule)  AON: 1 nút hoạt động được phát triển để chứa các giá  Chiều đi (forward pass): Tính các giá trị thời gian sớm. trị thời gian của hoạt động  Earliest start (ES): thời gian bắt đầu sớm nhất  Earliest finish (EF): thời gian kết thúc sớm nhất  Latest start (LS): thời gian bắt đầu trễ nhất  Latest finish (LF): thời gian kết thúc trễ nhất  Chiều đi (forward pass): Tính các giá trị thời gian sớm.  Chiều quay về (backward pass): Tính các giá trị thời gian trễ. 79 GV. Huỳnh Đỗ Bảo Châu 80 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 17
  18. 2/12/2017 Lịch trình hoạt động (activity schedule) Hoạt động trễ (activity slack)  Chiều quay về (backward pass): Tính các giá trị thời gian trễ.  Là những hoạt động không phải đường tớihạn, thờigian sớmnhấtbắt đầu(hoặckếtthúc)vàtrễ nhấtbắt đầu(hoặc kết thúc) không bằng nhau tồntạithờigiantrễ.  Slack là lượng thờigianmàhoạt động có thể bị trì hoãn không ảnh hưởng đếnthờigiantổng thể củadự án.  Trong thựctế, đólàthời gian thêm (có sẵn) để hoàn thành mộthoạt động. 81 GV. Huỳnh Đỗ Bảo Châu 82 GV. Huỳnh Đỗ Bảo Châu Hoạt động trễ (activity slack)  Chia sẽđộtrễ (Shared slack): là tổng thờigiantrễđược tổng hợpvàchiasẽ giữa các hoạt động đượcphéptrễ (chuỗihoạt động không trên đường tớihạn) 10. Xác suất thời gian hoạt động (Probabilistic Activity Times) 83 GV. Huỳnh Đỗ Bảo Châu 84 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 18
  19. 2/12/2017 Xác suất thời gian ước tính Xác suất thời gian ước tính (Probabilistic Times Estimates) (Probabilistic Times Estimates)  Thờigianđược ướclượng cho 1 công việclàmộtphânphốixác suấtbetacóhìnhdạng dựatrên3dạng thời gian ướctính.  3giátrị thời gian cho từng hoạt động là: thờigianthường xuyên, lạc quan, và bi quan cung cấpmột ướctínhgiátrị trung bình và phương sai theo phân phốibeta.  b = pessimistic time estimate (bi quan)  m = most likely time estimate (thường xuyên)  a = optimistic time estimate (lạc quan) 4 ờ ỳ ọ ∶ 6 ươ ∶ 6 85 GV. Huỳnh Đỗ Bảo Châu 86 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa Ví dụ minh họa (tt)  Cho dự án có bảng ước tính thời gian như sau:  Dự án có đường tới hạn đi qua các hoạt động 2 5 8 11  Thời gian hoàn thành dự án: 25 ầ  Phương sai của dự án: 62 6.9 ầ 9 87 GV. Huỳnh Đỗ Bảo Châu 88 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 19
  20. 2/12/2017 Ví dụ minh họa (tt) Phân tích xác suất của dự án  Sơ đồ mạng thời gian hoạt động của dự án  Thời gian dự án kỳ vọng được giả định là 1 phân phối chuẩn xác suất.  Sử dụng phân phối bình thường, xác suất có thể được xác định bằng cách tính toán giá trị Z của độ lệch chuẩn. 89 GV. Huỳnh Đỗ Bảo Châu 90 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt ví dụ trên)  Giả sử người quản lý dự án tuyên bố sự án sẽ hoàn thành trong x = 30 tuần ? Xác suất để điều này xảy ra ?  6.9 11. Thiết lập sơ đồ mạng  6.9 2.63 bằng MS Project  1.90 . Sinh viên tự đọc tài liệu đính kèm  Tra bảng ta có Xác suất P = 97.13% 91 GV. Huỳnh Đỗ Bảo Châu 93 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 20
  21. 2/12/2017 Vấn đề điều chỉnh  Việc rút ngắnthờigiandự án, giảmthờigiansẽ làm ảnh hưởng đếnchiphícủadự án.  Nhu cầuthựctế có thểđòi hỏidự án phảihoànthành (D) ít hơnthờigiantối ưu được tính theo đường tớihạn (S). 12. Điều chỉnh sơ đồ mạng theo thời gian  Các biện pháp rút ngắnthờigianS: (Crash Scheduling)  Bố trí thựchiệncáchoạt động song song thay vì nốitiếp như trong sơđồmạng  Phân phốilại tài nguyên: tăng nhân công, tăng giờ lao động, tăng công suấtmáymóc,thiếtbị, .  Thay đổibiệnphápkỹ thuật. Hầuhếtcácbiệnphápsẽ làm tăng chi phí 94 GV. Huỳnh Đỗ Bảo Châu 95 GV. Huỳnh Đỗ Bảo Châu Các bước thực hiện Ví dụ minh họa 1. Tìm đường tớihạndự án, tính thời gian, chi phí, tổng chi phí  dự án trong điềukiệnbìnhthường theo sơđồmạng. Cho dự án có sơ đồ mạng như sau, tìm chi phí phát 2. Dọctheođường tớihạn, tìm cách giảm1đơnvị thời gian của sinh nếu muốn rút ngắn thời gian thực hiện dự án là 1trongcáchoạt động trên đósaochochiphíphátsinhlànhỏ 30 tuần. nhất.  Lưuý:Mỗihoạt động khi rút ngắn1đơnvị thờigianđềusẽ kèm theo 1 lượng chi phí tăng lên.  Để rút ngắntừ S D, giả sử cầnthựchiệnnhiềulần, mỗilầnrút1 đơnvị thờigian. 3. Sau khi rút ngắn1đơnvị thờigian,sơđồmạng được điều chỉnh, tìm lại đường tớihạn, chi phí, tổng thờigian,tổng chi phí dự án. 4. Nếucần rút ngắnthời gian tiếptục, ta thựchiệnlạibước2,3 đếnkhiđạtmụctiêu. 5. Lậpbiểu đồ tương quan giữathời gian S và chi phí dự án. 96 GV. Huỳnh Đỗ Bảo Châu 97 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 21
  22. 2/12/2017 Ví dụ minh họa (tt) Ví dụ minh họa (tt)  Dự án có chi phí thực hiện từng hoạt động, thời gian  Hoạt động 1 cần rút ngắn5tuần, phát sinh $2000 muốn rút ngắn, và chi phí phát sinh như sau: Rút ngắn1tuần phát sinh $400 Ta có đồ thi mốitương quan chi phí khi rút ngắnthờigian củahoạt động 1 98 GV. Huỳnh Đỗ Bảo Châu 99 GV. Huỳnh Đỗ Bảo Châu Ví dụ minh họa (tt) Ví dụ minh họa (tt)  Dữ liệudự án khi rút ngắn1 đơnvị thờigian  Sơ đồ mạng với chi phí của 1 đơn vị thời gian 100 GV. Huỳnh Đỗ Bảo Châu 101 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 22
  23. 2/12/2017 Ví dụ minh họa (tt) Biểu đồ quan hệ giữa thời gian và chi phí  Sơ đồ mạng sau khi rút thời gian hoạt động 1 Tổng thời gian 36 35 34 33 32 31 30 dự án Tổng chi phí 75000 75400 75800 76200 76600 77000 77500 78000 77500 77000 76500 76000 dự án 75500 Tổng chi phí 75000 74500 74000 73500 36 35 34 33 32 31 30 102 GV. Huỳnh Đỗ Bảo Châu 103 GV. Huỳnh Đỗ Bảo Châu Mô hình bài toán 13. Chuyển đổi mô hình mạng CPM/PERT sang Mô hình quy hoạch tuyến tính 104 GV. Huỳnh Đỗ Bảo Châu 105 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 23
  24. 2/12/2017 Ví dụ minh họa Ví dụ minh họa (tt)  Cho dự án có sơđồmạng vớisự kiệnthờigiansớm  Mô hình bài toán nhấtnhư sau: 106 GV. Huỳnh Đỗ Bảo Châu 107 GV. Huỳnh Đỗ Bảo Châu HẾT CHƯƠNG 5 108 GV. Huỳnh Đỗ Bảo Châu GV. ThS. Huỳnh Đỗ Bảo Châu 24