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

2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 1 CHƯƠNG 5 KỸ THUẬT MẠNG TRONG QUẢN LÝ 1 TRƯỜNG ĐẠI HỌC NGÂN HÀNG TP.HCM KHOA HỆ THỐNG THÔNG TIN QUẢN LÝ KHOA HỌC QUẢN LÝ ỨNG DỤNG GV. ThS. Huỳnh Đỗ Bảo Châu Nội dung chính PHẦN 1: KỸ THUẬT MẠNG 1. Giới thiệu về kỹ thuật mạng 2. Bài toán tìm đường ngắn nhất 3. Giải bài toán tìm đường ngắn nhất bằ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 6. Giải bài toán tìm luồng cực đại bằng Excel 2 GV. Huỳnh Đỗ Bảo Châu Nội dung chính 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 8. Biểu đồ Gantt 9. CPM / PERT 10.Xác suất thời gian hoạt động 11. Thiết lập sơ đồ mạng bằng MS Project 12. Điều chỉnh sơ đồ mạng theo thời gian 13. Chuyển đổi mô hình mạng CPM/PERT sang Mô hình quy hoạch tuyến tính 3 GV. Huỳnh Đỗ Bảo Châu 1. Giới thiệu về kỹ thuật mạng GV. Huỳnh Đỗ Bảo Châu4 PHẦN 1 KỸ THUẬT MẠNG 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 2 Khái niệm mạng (network) GV. Huỳnh Đỗ Bảo Châu5  Mạng là sự sắp xếp các đường dẫn kết nối tại các điểm khác nhau, thông qua đó các hạng mục (items) được di chuyển.  Ứng dụng mạng rất phổ biến vì chúng cung cấp một bức tranh của hệ thống và hệ thống lớn có thể dễ dàng mô hình hóa như các mạng.  Mô hình dòng chảy mạng (network flow models) mô tả dòng chảy các hạng mục (items) thông qua hệ thống. Các thành phần của mạng GV. Huỳnh Đỗ Bảo Châu6  Nút (nodes): biểu diễn bằng vòng tròn, đại diện cho các điểm giao nhau nối các nhánh.  Nhánh (branches): đại diện là đường thẳng, kết nối các nút và hiển thị dòng chảy từ điểm này đến điểm khác.  Giá trị đại diện cho khoảng cách, độ dài của thời gian, chi phí hoặc được gán cho mỗi nhánh.  Mục đích của mạng là xác định khoảng cách ngắn nhất, độ dài thời gian ngắn nhất, hoặc chi phí thấp nhất giữa các điểm trong mạng. Mạng lưới đường sắt có 4 node, 4 nhánh Nút 1 (atlanta) là nút gốc Đường đi ngắn nhất (shortest route) GV. Huỳnh Đỗ Bảo Châu7  Đường ngắn nhất là khoảng cách ngắn nhất giữa một node gốc (điểm xuất phát) và các điểm đến.  Bài toán tìm đường ngắn nhất được giải quyết bằng cách sử dụng các kỹ thuật giải trình ngắn nhất 2. Bài toán tìm đường ngắn nhất GV. Huỳnh Đỗ Bảo Châu8 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 3 Giải pháp tìm đường ngắn nhất GV. Huỳnh Đỗ Bảo Châu9 1. Chọn nút với đường đi trực tiếp ngắn nhất từ nút gốc. 2. Thiết lập một tập vĩnh viễn với các nút gốc và các nút được chọn ở bước 1. 3. Xác định tất cả các nút được kết nối trực tiếp đến các nút trong tập vĩnh viễn. 4. Chọn nút với các tuyến đường ngắn nhất (nhánh) từ nhóm các nút được nối trực tiếp đến các nút trong tập vĩnh viễn. 5. Lặp lại bước 3 và 4 cho đến khi tất cả các nút đã tham gia vào tập vĩnh viễn. Ví dụ minh họa GV. Huỳnh Đỗ Bảo Châu10 Tìm đường đi nhanh nhất để công ty vận chuyển Stagecoach Shipping đi từ Los Angeles đến sáu thành phố có thời gian di chuyển (giờ) như hình. Xác định tuyến đường đi có thời gian ngắn nhất từ node 1 đến 6 node còn lại Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu11  Xét từ node 1 – nằm trong tập vĩnh viễn  Node 3 đưa vào tập vĩnh viễn  {1,3} Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu12  Xét từ node {1,3} – nằm trong tập vĩnh viễn  Node 2 đưa vào tập vĩnh viễn  {1,2,3} 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 4 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu13  Xét từ node {1,2,3} – nằm trong tập vĩnh viễn  Node 4 đưa vào tập vĩnh viễn  {1,2,3,4} Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu14  Xét từ node {1,2,3,4} – nằm trong tập vĩnh viễn  Node 6 đưa vào tập vĩnh viễn  {1,2,3,4,6} Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu15  Xét từ node {1,2,3,4,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} Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu16  Xét từ node {1,2,3,4,5,6} – nằm trong tập vĩnh viễn  Node 7 đưa vào tập vĩnh viễn {1,2,3,4,5,6,7} 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 5 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu17  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 GV. Huỳnh Đỗ Bảo Châu18 Giải pháp trên Excel GV. Huỳnh Đỗ Bảo Châu19  Chuyển đổi bài toán tìm mạng lưới ngắn nhất thành mô hình bài toán lập trình tuyến tính với các số nguyên 0, 1.  Xây dựng mô hình lập trình tuyến tính:  Biến quyết định của từng nhánh trong mạng: ൝ ݔ௜௝ ൌ 0 ݊ếݑ ݄݊á݄݊ ݅ െ ݆ ݄ܿưܽ ݐ݄ݑộܿ ݇ếݐ ݍݑả đườ݊݃ ݊݃ắ݊ ݄݊ấݐ ݔ௜௝ ൌ 1 ݊ếݑ ݄݊á݄݊ ݅ െ ݆ ݐ݄ݑộܿ ݇ếݐ ݍݑả đườ݊݃ ݊݃ắ݊ ݄݊ấݐ  Giả định dòng chảy chỉ đi từ node nhỏ đến node lớn hơn.  Hàm mục tiêu: ܯ݅݊ ܼ ൌ ∑ ܭ௜௝ݔ௜௝ ௝ ௜ (K là giá trị thời gian, khoảng cách, chi phí của nhánh i – j )  Ràng buộc cho mỗi nút: bất cứ node nào cũng phãi có 1 đường ra  bảo tồn dòng chảy.  Sử dụng Solve để giải bài toán QHTT trên  Đọc kết quả dựa trên các giá trị biến xij = 1 Ví dụ minh họa GV. Huỳnh Đỗ Bảo Châu20 Tìm đường đi nhanh nhất để công ty vận chuyển Stagecoach Shipping đi từ Los Angeles đến sáu thành phố có thời gian di chuyển (giờ) như hình. Xác định tuyến đường đi có thời gian ngắn nhất từ node 1 đến 6 node còn lại 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 6 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu21  Biến quyết định ݔ௜௝ với ݅, ݆ ∈ 1,7  Hàm mục tiêu: ܯ݅݊ ܼ ൌ 16ݔଵଶ ൅ 9ݔଵଷ ൅ 35ݔଵସ ൅ 12ݔଶସ ൅ 25ݔଶହ ൅ 15ݔଷସ ൅ 22ݔଷ଺ ൅ 14ݔସହ ൅ 17ݔସ଺ ൅ 19ݔସ଻ ൅ 8ݔହ଻ ൅ 14ݔ଺଻  Ràng buộc:  Ở node 1 bắt buộc phải có 1 hướng ra (1-2, 1-3, 1-4): ݔଵଶ ൅ ݔଵଷ ൅ ݔଵସ ൌ 1  Ở node 2, xe phải qua nhánh 1-2 và đi theo 2-4, hay 2-5: ݔଵଶ ൌ ݔଶସ ൅ ݔଶହ → ݔଵଶ െ ݔଶସ െ ݔଶହ ൌ 0  Thực hiện tương tự ràng buộc cho các nút 3,4,5,6, 7 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu22  Mô hình hoàn chỉnh bài toán:  Hàm mục tiêu: ܯ݅݊ ܼ ൌ 16ݔଵଶ ൅ 9ݔଵଷ ൅ 35ݔଵସ ൅ 12ݔଶସ ൅ 25ݔଶହ ൅ 15ݔଷସ ൅ 22ݔଷ଺ ൅ 14ݔସହ ൅ 17ݔସ଺ ൅ 19ݔସ଻ ൅ 8ݔହ଻ ൅ 14ݔ଺଻  Ràng buộc: ݔଵଶ ൅ ݔଵଷ ൅ ݔଵସ ൌ 1 ݔଵଶ െ ݔଶସ െ ݔଶହ ൌ 0 ݔଵଷ െ ݔଷସ െ ݔଷ଺ ൌ 0 ݔଵସ ൅ ݔଶସ ൅ ݔଷସ െ ݔସହ െ ݔସ଺ െ ݔସ଻ ൌ 0 ݔଶହ ൅ ݔସହ െ ݔହ଻ ൌ 0 ݔଷ଺ ൅ ݔସ଺ െ ݔ଺଻ ൌ 0 ݔସ଻ ൅ ݔହ଻ ൅ ݔ଺଻ ൌ 1 ݔ௜௝ ൌ 0 ݋ݎ 1 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu23  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) GV. Huỳnh Đỗ Bảo Châu24 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 7 Cây bao trùm tối thiểu GV. Huỳnh Đỗ Bảo Châu25  Vấn đề cây bao trùm tối thiểu là kết nối tất cả các nút trong mạng để tổng chiều dài nhánh được giảm thiểu.  Kết quả bài toán sẽ cho đường dẫn mạng (Kết nối) tất cả các điểm trong mạng là đường đi ngắn nhất (hoặc chiều dài ngắn nhất). Giải pháp tìm cây bao trùm tối thiểu GV. Huỳnh Đỗ Bảo Châu26 1. Chọn bất kỳ nút bắt đầu (thông thường, nút 1 được chọn). 2. Chọn nút gần nhất với nút bắt đầu tham gia vào cây bao trùm. 3. Chọn nút gần nhất chưa tham gia trong cây bao trùm. 4. Lặp lại bước 3 cho đến khi tất cả các nút đã tham gia cây bao trùm. Ví dụ minh họa GV. Huỳnh Đỗ Bảo Châu27  Công ty truyền hình cáp Metro cài đặt 1 hệ thống cáp truyền hình trong cộng đồng gồm 8 khu vực ngoại ô.  Mỗi nhà trong 8 vùng ngoại ô phải được kết nối với hệ thống cáp chính.  Công ty muốn tìm một giải pháp lắp đặt đường trục cáp chính đi đến 8 vùng để tổng chiều dài của dây cáp sử dụng là ngắn nhất.  Khoảng cách giữa các vùng được mô tả trong hình sau: Nhánh từ vùng 1 đến vùng 2 cần 16.000 m dây cáp Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu28 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 8 5. Bài toán luồng cực đại (The Maximal Flow Problem) GV. Huỳnh Đỗ Bảo Châu29 Luồng cực đại GV. Huỳnh Đỗ Bảo Châu30  Vấn đề luồng cực đại là 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 áp dụng trong các vấn đề thực tế như:  dòng chảy của nước, khí đốt, hoặc dầu thông qua mạng lượng các đường ống;  dòng chảy của giấy tờ trong cơ quan chính phủ;  dòng chảy của lượng lưu thông trong mạng lưới giao thông;  dòng chảy sản phẩm trong hệ thống dây chuyền sản xuất. Giải pháp tìm luồng cực đại GV. Huỳnh Đỗ Bảo Châu31 1. Tự ý chọn con đường nào trong mạng từ gốc đến đích. 2. Điều chỉnh công suất tại mỗi nút bằng cách trừ đi dòng chảy tối đa cho các con đường đã chọn ở bước 1. 3. Thêm dòng chảy tối đa trên con đường theo hướng ngược lại tại mỗi nút. 4. Lặp lại các bước 1, 2, và 3 cho đến khi không có đường nào có công suất lưu lượng cao hơn lưu lượng có sẵn. Ví dụ minh họa GV. Huỳnh Đỗ Bảo Châu32  Hệ thống đường sắt giữa Omaha và Louis thể hiện trong hình bên dưới. Công ty Scott cần chuyển các bộ phận của xe lửa từ Omaha về Louis bằng đường sắt. Tuy nhiên, hợp đồng giới hạn số toan xe lửa công ty có thể sử dụng trên từng nhánh trong 1 tuầ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) 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 9 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu33  Chọn 1 đường đi ngẫu nhiên là : 1-2-5-6  Sử dụng 4 xe Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu34  Chọn 1 đường đi ngẫu nhiên là : 1-4-6  Sử dụng 4 xe  Tổng lưu lượng xe qua mạng là 8 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu35  Chọn 1 đường đi ngẫu nhiên là : 1-3-6  Sử dụng 6 xe  Tổng lưu lượng xe qua mạng là 14 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu36  Chỉ còn 1 đường đi là : 1-3-4-6  Sử dụng được thêm 1 xe  Tổng lưu lượng xe qua mạng là 15 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 10 GV. Huỳnh Đỗ Bảo Châu37 6. Giải bài toán tìm luồng cực đại bằng Excel GV. Huỳnh Đỗ Bảo Châu38 Giải pháp trên Excel GV. Huỳnh Đỗ Bảo Châu39  Chuyển đổi bài toán thành mô hình bài toán lập trình tuyến tính và giải bằng Solve.  Xây dựng mô hình lập trình tuyến tính:  Biến quyết định đại diện cho dòng chảy trong các nhánh mạng: ݔ௜௝  Để giảm kích thước và độ phức tạp của việc xây dựng mô hình, loại bỏ dòng chảy trên cùng một nhánh theo hướng ngược lại.  Điều chỉnh mạng để quy về bài toán tuyến tính: tạo thêm 1 nhánh từ nút cuối về nút đầu có giá trị tên dòng chảy bằng tổng giá trị dòng chảy từ nút đầu thông qua mạng đến nút cuối (mục đích để tối đa hóa số lượng dòng chảy từ nút cuối về nút đầu) Giải pháp trên Excel (tt) GV. Huỳnh Đỗ Bảo Châu40  Xây dựng mô hình lập trình tuyến tính (tt):  Hàm mục tiêu: ܯܽݔ ܼ ൌ ݔ௡ú௧ ௖௨ố௜ ି௡ú௧ đầ௨  Ràng buộc cho mỗi nút: bất cứ node nào cũng phãi có 1 đường ra  bảo tồn dòng chảy. (tương tự bài toán tìm đường ngắn nhất)  Sử dụng Solve để giải bài toán QHTT trên. 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 11 Ví dụ minh họa GV. Huỳnh Đỗ Bảo Châu41  Hệ thống đường sắt giữa Omaha và Louis thể hiện trong hình bên dưới. Công ty Scott cần chuyển các bộ phận của xe lửa từ Omaha về Louis bằng đường sắt. Tuy nhiên, hợp đồng giới hạn số toan xe lửa công ty có thể sử dụng trên từng nhánh trong 1 tuầ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) Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu42  Biến quyết định ݔ௜௝ với ݅, ݆ ∈ 1,6  Hàm mục tiêu: ܯܽݔ ܼ ൌ ݔ଺ଵ  Ràng buộc:  Lưu lượng dòng chảy 6-1 chảy vào node 1 bắt buộc phải có 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ực hiện tương tự ràng buộc cho các nút 3,4,5,6  Các ràng buộc lượng tối đa của từng nháng dòng chảy. Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu43  Hàm mục tiêu: ܯܽݔ ܼ ൌ ݔ଺ଵ  Ràng buộc: Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu44 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 12 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu45  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) 7. Các thành phần của quản lý dự án GV. Huỳnh Đỗ Bảo Châu52 PHẦN 2 KỸ THUẬT MẠNG TRONG QUẢN LÝ DỰ ÁN Khái niệm GV. Huỳnh Đỗ Bảo Châu53  (1) Quản lý dự án là việc lập kế hoạch, tổ chức và kiểm soát của một quá trình hoặc hoạt động liên tục, phản ánh sự cam kết về sử dụng nguồn tài nguyên và con người cho các hoạt động với một khung thời gian nhất định.  (2) Quản lý dự án (PM) là một nguyên tắc của lập kế hoạch, tổ chức, bảo vệ và quản lý các nguồn lực để mang về thành công của mục tiêu dự án.  Bao gồm ba chính quy trình lập kế hoạch, lịch trình, và kiểm soát Quy trình quản lý dự án GV. Huỳnh Đỗ Bảo Châu54 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 13 Kế hoạch dự án GV. Huỳnh Đỗ Bảo Châu55  Bao gồm các phần:  Mục tiêu (objectives)  Phạm vi / quy mô dự án (scope)  Yêu cầu (contract requirements)  Lịch trình (schedules)  Tài nguyên (resources)  Cá nhân (personnel)  Điều khiển (control)  Vấn đề tiềm ẩn và rủi do (risk & problem) Cấu trúc phân chia công việc (WBS) GV. Huỳnh Đỗ Bảo Châu59  Cấu trúc phân chia công việc là một sơ đồ tổ chức phân rã dự án thành các module (công việc con) để lập kế hoạch.  Các công việc được chia chi tiết thành các hoạt động, nhiệm vụ cá nhân  tạo nên 1 cấu trúc phân cấp.  WBS giúp QLDA xác định:  Các nhiệm vụ cá nhân  Khối lượng công việc của dự án  Các nguồn lực cần thiết  Mối quan hệ giữa các module và các hoạt động  Tránh trùng lặp không cần thiết các hoạt động  Cơ sở cho phát triển kế hoạch quản lý tiến độ dự án Cấu trúc phân chia công việc (WBS) GV. Huỳnh Đỗ Bảo Châu60  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. WBS GV. Huỳnh Đỗ Bảo Châu61 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 14 Lịch trình dự án (project schedule) GV. Huỳnh Đỗ Bảo Châu63  Tập hợp các hoạt động của dự án  Xác định công việc đòi hỏi các công việc khác thực hiện trước khi nó bắt đầu (quan hệ ưu tiên)  Xác định các yếu tố ảnh hưởng đến thời gian hoàn thành dự án:  Tài nguyên)  Mức độ chi tiết của các mục tiêu dự án  Đảm bảo yếu tố thành công quan trọng nhất của dự án là “đúng thời gian” Lịch trình dự án (project schedule) GV. Huỳnh Đỗ Bảo Châu64  Các bước phát triển lịch trình dự án:  Xác định các hoạt động phải được thực hiện để hoàn thành dự án.  Xác định trình tự các hoạt động theo thứ tự hoàn thành.  Ướ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à thời gian của các hoạt động.  Các phương pháp định lượng thời gian trong lịch trình:  Biểu đồ Gantt  CPM/PERT 8. Biểu đồ Gantt GV. Huỳnh Đỗ Bảo Châu67 Biển đồ Gantt GV. Huỳnh Đỗ Bảo Châu68  Được phát triển bởi Henry Gantt, một người tiên phong trong lĩnh vực kỹ thuật công nghiệp vào năm 1914.  Là một kỹ thuật quản lý dự án truyền thống để lập kế hoạchcác dự án nhỏ có tương đối ít các hoạt động và các mối quan hệ ưu tiên.  Là một đồ thị dạng thanh với mỗi thanh đại diện cho 1 hoạt động của dự án và chiều dài thanh tương ứng thời gian thực hiện hoạt động đó.  Các hoạt động được phép chậm trễ sẽ có 1 giá trị slack.  Slack là lượng thời gian mà một hoạt động có thể bị trì hoãn mà không ảnh hưởng bất kỳ hoạt động nào sau nó, và toàn bộ dự án. 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 15 Biển đồ Gantt (tt) GV. Huỳnh Đỗ Bảo Châu69 9. CPM/PERT GV. Huỳnh Đỗ Bảo Châu70 CPM/PERT GV. Huỳnh Đỗ Bảo Châu71  Cả 2 phương pháp đều dẫn xuất từ Biểu đồ Gantt  Ưu điểm: sử dụng một mạng lưới (thay vì một đồ thị) để hiển thị các mối quan hệ giữa các hoạt động ưu tiên CPM (critical path method) PERT (project evaluation and review technique) sử dụng ước tính 1 giá trị thời gian hoạt động cho từng hoạt động trong mạng, hoạt động là các nút (node) sử dụng ước tính nhiều giá trị thời gian hoạt động phản ánh sự thay đổi cho từng hoạt động trong mạng, hoạt động là đường giữa các nút (node) thời gian hoạt động được xem như là chắc chắn. thời gian hoạt động được xem như là 1 xác suất hoạt động được đại diện bởi các nút, và các mũi tên cho thấy mối quan hệ ưu tiên (tức là, hoạt động nào đến trước khác). hoạt động được đại diện là vòng cung, hoặc đường dây với các mũi tên, vòng tròn được gọi là nút Sơ đồ mạng AON Sơ đồ mạng AOA CPM/PERT GV. Huỳnh Đỗ Bảo Châu72  AON  AOA 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 16 Quy tắc lập sơ đồ mạng GV. Huỳnh Đỗ Bảo Châu73 1. Sự kiện được đánh số từ nhỏ đến lớn theo hướng từ trái qua phải, từ trên xuống dưới. 2. Mỗi sự kiện phải có hoạt động đến và hoạt động đi (ngoại trừ sự kiện bắt đầu và sự kiện cuối cùng). 3. Tất cả hoạt động trong sơ đồ mạng phải hướng từ trái sang phải, không được quay trở lại sự kiện mà chúng xuấ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 được ký hiệu bởi cùng 1 số (không được cùng sự kiện bắt đầu & sự kiện kết thúc) 5. Sơ đồ mạng cần có dạng đơn giản nhất, không nên có quá nhiều hoạt động giao cắt nhau. 6. Sơ đồ mạng phải phản ánh đúng trình tự và mối quan hệ giữa các hoạt động. Phương pháp mạng AOA (activity on arrow) GV. Huỳnh Đỗ Bảo Châu74  Nút tròn: được đánh số thứ tự, đại diện cho các sự kiện (kết thúc 1, 1 số công việc để công việc tiếp theo bắt đầu)  Đường mũi tên (nằm giữa 2 nút): đại diện cho hoạt động gồm tên hoạt động, thời gian thực hiện. Phương pháp mạng AOA (activity on arrow) GV. Huỳnh Đỗ Bảo Châu75  Có 3 loại hoạt động:  Hoạt động thực: là hoạt động cần nguồn lực và thời gian, biểu diễn bằng mũi tên nét liền  Hoạt động giả danh (dummy): một hoạt động giả để đảm bảo các mối quan hệ ưu tiên nhưng không có nguồn lực và thời gian thực hiện, biểu diễn bằng mũi tên nét đứt  Hoạt động chờ đợi: là hoạt động không cần nguồn lực mà chỉ cần thời gian, biểu diễn bằng mũi tên nét liền. Phương pháp mạng AON (activity on arrow) GV. Huỳnh Đỗ Bảo Châu76  Nút tròn: đại diện cho hoạt động  Đường mũi tên (nằm giữa 2 nút): diễn đạt mối quan hệ giữa 2 hoạt động.  Không cần các hoạt động giả danh.  Được hỗ trợ xây dựng trong phần mềm MS Project. 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 17 Đường tới hạn (critical path) GV. Huỳnh Đỗ Bảo Châu77  Đường tới hạn là đường dài nhất trong mạng; đó là thời gian tối thiểu để tất cả hoạt động trong mạng có thể được hoàn thành. Đường tới hạn (critical path) GV. Huỳnh Đỗ Bảo Châu78 Lịch trình hoạt động (activity schedule) GV. Huỳnh Đỗ Bảo Châu79  AON: 1 nút hoạt động được phát triển để chứa các giá 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ễ. Lịch trình hoạt động (activity schedule) GV. Huỳnh Đỗ Bảo Châu80  Chiều đi (forward pass): Tính các giá trị thời gian sớm. 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 18 Lịch trình hoạt động (activity schedule) GV. Huỳnh Đỗ Bảo Châu81  Chiều quay về (backward pass): Tính các giá trị thời gian trễ. Hoạt động trễ (activity slack) GV. Huỳnh Đỗ Bảo Châu82  Là những hoạt động không phải đường tới hạn, thời gian sớm nhất bắt đầu (hoặc kết thúc) và trễ nhất bắt đầu (hoặc kết thúc) không bằng nhau tồn tại thời gian trễ.  Slack là lượng thời gian mà hoạt động có thể bị trì hoãn không ảnh hưởng đến thời gian tổng thể của dự án.  Trong thực tế, đó là thời gian thêm (có sẵn) để hoàn thành một hoạt động. Hoạt động trễ (activity slack) GV. Huỳnh Đỗ Bảo Châu83  Chia sẽ độ trễ (Shared slack): là tổng thời gian trễ được tổng hợp và chia sẽ giữa các hoạt động được phép trễ (chuỗi hoạt động không trên đường tới hạn) 10. Xác suất thời gian hoạt động (Probabilistic Activity Times) GV. Huỳnh Đỗ Bảo Châu84 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 19 Xác suất thời gian ước tính (Probabilistic Times Estimates) GV. Huỳnh Đỗ Bảo Châu85  Thời gian được ước lượng cho 1 công việc là một phân phối xác suất beta có hình dạng dựa trên 3 dạng thời gian ước tính.  3 giá trị thời gian cho từng hoạt động là: thời gian thường xuyên, lạc quan, và bi quan  cung cấp một ước tính giá trị trung bình và phương sai theo phân phối beta.  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 ଶ Xác suất thời gian ước tính (Probabilistic Times Estimates) GV. Huỳnh Đỗ Bảo Châu86 Ví dụ minh họa GV. Huỳnh Đỗ Bảo Châu87  Cho dự án có bảng ước tính thời gian như sau: Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu88  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 9 ൌ 6.9 ݐݑầ݊ 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 20 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu89  Sơ đồ mạng thời gian hoạt động của dự án Phân tích xác suất của dự án GV. Huỳnh Đỗ Bảo Châu90  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. Ví dụ minh họa (tt ví dụ trên) GV. Huỳnh Đỗ Bảo Châu91  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 ൌ ߪଶ  ߪ ൌ 6.9 ൌ 2.63  ܼ ൌ ଷ଴ିଶହ ଶ.଺ଷ ൌ 1.90  Tra bảng ta có Xác suất P = 97.13% 11. Thiết lập sơ đồ mạng bằng MS Project GV. Huỳnh Đỗ Bảo Châu93 Sinh viên tự đọc tài liệu đính kèm 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 21 12. Điều chỉnh sơ đồ mạng theo thời gian (Crash Scheduling) GV. Huỳnh Đỗ Bảo Châu94 Vấn đề điều chỉnh GV. Huỳnh Đỗ Bảo Châu95  Việc rút ngắn thời gian dự án, giảm thời gian sẽ làm ảnh hưởng đến chi phí của dự án.  Nhu cầu thực tế có thể đòi hỏi dự án phải hoàn thành (D) ít hơn thời gian tối ưu được tính theo đường tới hạn (S).  Các biện pháp rút ngắn thời gian S:  Bố trí thực hiện các hoạt động song song thay vì nối tiếp như trong sơ đồ mạng  Phân phối lại tài nguyên: tăng nhân công, tăng giờ lao động, tăng công suất máy móc, thiết bị, .  Thay đổi biện pháp kỹ thuật.  Hầu hết các biện pháp sẽ làm tăng chi phí Các bước thực hiện GV. Huỳnh Đỗ Bảo Châu96 1. Tìm đường tới hạn dự án, tính thời gian, chi phí, tổng chi phí dự án trong điều kiện bình thường theo sơ đồ mạng. 2. Dọc theo đường tới hạn, tìm cách giảm 1 đơn vị thời gian của 1 trong các hoạt động trên đó sao cho chi phí phát sinh là nhỏ nhất.  Lưu ý: Mỗi hoạt động khi rút ngắn 1 đơn vị thời gian đều sẽ kèm theo 1 lượng chi phí tăng lên.  Để rút ngắn từ S  D, giả sử cần thực hiện nhiều lần, mỗi lần rút 1 đơn vị thời gian. 3. Sau khi rút ngắn 1 đơn vị thời gian, sơ đồ mạng được điều chỉnh, tìm lại đường tới hạn, chi phí, tổng thời gian, tổng chi phí dự án. 4. Nếu cần rút ngắn thời gian tiếp tục, ta thực hiện lại bước 2,3 đến khi đạt mục tiêu. 5. Lập biểu đồ tương quan giữa thời gian S và chi phí dự án. Ví dụ minh họa GV. Huỳnh Đỗ Bảo Châu97  Cho dự án có sơ đồ mạng như sau, tìm chi phí phát sinh nếu muốn rút ngắn thời gian thực hiện dự án là 30 tuần. 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 22 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu98  Dự án có chi phí thực hiện từng hoạt động, thời gian muốn rút ngắn, và chi phí phát sinh như sau: Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu99  Hoạt động 1 cần rút ngắn 5 tuần, phát sinh $2000 Rút ngắn 1 tuần phát sinh $400 Ta có đồ thi mối tương quan chi phí khi rút ngắn thời gian của hoạt động 1 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu100  Dữ liệu dự án khi rút ngắn 1 đơn vị thời gian Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu101  Sơ đồ mạng với chi phí của 1 đơn vị thời gian 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 23 Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu102  Sơ đồ mạng sau khi rút thời gian hoạt động 1 Biểu đồ quan hệ giữa thời gian và chi phí GV. Huỳnh Đỗ Bảo Châu103 Tổng thời gian dự án 36 35 34 33 32 31 30 Tổng chi phí 75000 75400 75800 76200 76600 77000 77500 73500 74000 74500 75000 75500 76000 76500 77000 77500 78000 36 35 34 33 32 31 30 dự án Tổng chi phí 13. Chuyển đổi mô hình mạng CPM/PERT sang Mô hình quy hoạch tuyến tính GV. Huỳnh Đỗ Bảo Châu104 Mô hình bài toán GV. Huỳnh Đỗ Bảo Châu105 2/12/2017 GV. ThS. Huỳnh Đỗ Bảo Châu 24 Ví dụ minh họa GV. Huỳnh Đỗ Bảo Châu106  Cho dự án có sơ đồ mạng với sự kiện thời gian sớm nhất như sau: Ví dụ minh họa (tt) GV. Huỳnh Đỗ Bảo Châu107  Mô hình bài toán HẾT CHƯƠNG 5 108 GV. Huỳnh Đỗ Bảo Châu