Luận văn Thạc sĩ Khoa học Máy tính: Bài toán lập, điều khiển tiến độ công việc trong quản lí dự án và ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:84

Thêm vào BST

Báo xấu

23
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của đề tài là nghiên cứu những nền tảng lý thuyết cần thiết về sơ đồ mạng, lý thuyết đồ thị,… làm cơ sở cho việc phân tích và đưa ra thuật toán để giải các bài toán trong quản dự án gồm: Bài toán lập và điều khiển tiến độ; Bài toán phân phối tài nguyên; Bài toán cân đối chi 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. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học Máy tính: Bài toán lập, điều khiển tiến độ công việc trong quản lí dự án và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN XUÂN VIỆT BÀI TOÁN LẬP, ĐIỀU KHIỂN TIẾN ĐỘ CÔNG VIỆC TRONG QUẢN LÍ DỰ ÁN VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2016
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN XUÂN VIỆT BÀI TOÁN LẬP, ĐIỀU KHIỂN TIẾN ĐỘ CÔNG VIỆC TRONG QUẢN LÍ DỰ ÁN VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS. Nguyễn Thị Hồng Minh THÁI NGUYÊN - 2016
i LỜI CAM ĐOAN Tôi xin cam đoan luận văn này do chính tôi thực hiện, dưới sự hướng dẫn khoa học của TS. Nguyễn Thị Hồng Minh, số liệu và kết quả nghiên cứu trong luận văn này hoàn toàn trung thực và chưa sử dụng để bảo vệ một công trình khoa học nào, các thông tin, tài liệu trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Mọi sự giúp đỡ cho việc hoàn thành luận văn đều đã được cảm ơn. Nếu sai tôi hoàn toàn chịu trách nhiệm. Thái Nguyên, tháng năm 2016 Học viên Nguyễn Xuân Việt
ii LỜI CẢM ƠN Trước hết em xin trân trọng cảm ơn các thầy giáo, cô giáo trường đại học công nghệ thông tin đã giảng dạy em trong quá trình học tập chương trình sau đại học. Dù rằng, trong quá trình học tập có nhiều khó khăn trong việc tiếp thu kiến thức cũng như sưu tầm tài liệu học tập, nhưng với sự nhiệt tình và tâm huyết của thầy cô cộng với những nỗ lực của bản thân đã giúp em vượt qua được những trở ngại đó. Em xin bày tỏ lòng biết ơn sâu sắc tới Cô giáo TS.Nguyễn Thị Hồng Minh người hướng dẫn khoa học, đã tận tình hướng dẫn em trong suốt quá trình làm luận văn. Xin chân thành cảm ơn các bạn bè, đồng nghiệp, các bạn học viên lớp cao học CK13B, những người thân trong gia đình đã động viên, chia sẻ, tạo điều kiện giúp đỡ trong suốt quá trình học tập và làm luận văn. Một lần nữa em xin chân thành cảm ơn. Thái Nguyên, tháng năm 2016 Học viên Nguyễn Xuân Việt
iii MỤC LỤC LỜI CAM ĐOAN ........................................................................................................ i LỜI CẢM ƠN .............................................................................................................ii MỤC LỤC ................................................................................................................. iii DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT .............................................. v DANH MỤC CÁC BẢNG......................................................................................... vi DANH MỤC CÁC HÌNH .........................................................................................vii MỞ ĐẦU .................................................................................................................... 1 CHƯƠNG 1. CƠ SỞ LÝ THUYẾT ......................................................................... 2 1.1. Phương pháp sơ đồ mạng ................................................................................. 2 1.1.1. Khái niệm về sơ đồ mạng.......................................................................... 2 1.1.2. Phương pháp đường găng CPM. ............................................................. 10 1.1.2.1. Giới thiệu chung về phương pháp đường găng ................................ 10 1.1.2.2. Các bước tính toán trong phương pháp CPM .................................. 10 1.1.3. Phương pháp sơ đồ mạng PERT ............................................................. 13 1.1.3.1. Khái niệm cơ bản về phương pháp PERT........................................ 13 1.1.3.2. Ước lượng thời gian hoàn thành công việc ...................................... 15 1.1.3.3. Các thông số thời gian trong sơ đồ mạng PERT .............................. 17 1.1.3.4. Tính xác suất hoàn thành công việc ................................................. 18 1.2. Ứng dụng sơ đồ mạng trong quản lí tiến độ dự án......................................... 20 1.2.1. Sơ đồ mạng trên trục thời gian ................................................................ 20 1.2.2. Đưa sơ đồ mạng lên trục thời gian .......................................................... 21 1.2.3. Chuyển sơ đồ mạng sang sơ đồ ngang .................................................... 23 1.2.4. Quy tắc lập sơ đồ mạng sự kiện .............................................................. 25 1.3. Tổng quan về quản lí dự án ............................................................................ 26 1.3.1. Mục tiêu của quản lý dự án ..................................................................... 26 1.3.2. Tác dụng của quản lý dự án .................................................................... 27 1.3.3. Các giai đoạn của dự án và vòng đời dự án ............................................ 28
iv CHƯƠNG 2. ỨNG DỤNG SƠ ĐỒ MẠNG VÀO LẬP VÀ QUẢN LÍ TIẾN ĐỘ TRONG DỰ ÁN ............................................................................................... 31 2.1. Bài toán quản lí tiến độ .................................................................................. 31 2.1.1. Sơ đồ mạng biểu diễn tiến độ dự án ........................................................ 31 2.1.2. Thuật toán cho bài toán lập và điều khiển tiến độ .................................. 31 2.2. Bài toán quản lí tài nguyên ............................................................................ 38 2.2.1. Giới thiệu chung ...................................................................................... 38 2.2.2. Biểu đồ tài nguyên và các quy tắc ưu tiên .............................................. 41 2.2.3. Các phương pháp phân phối tài nguyên ................................................. 44 2.2.4. Cân đối tài nguyên .................................................................................. 48 2.3. Bài toán tối ưu chi phí và giá thành ............................................................... 53 2.3.1. Giới thiệu chung ...................................................................................... 53 2.3.2. Thời gian và giá thành............................................................................. 53 2.3.3. Chi phí trực tiếp, chi phí gián tiếp .......................................................... 55 2.3.3.1. Chi phí gián tiếp ............................................................................... 55 2.3.3.2. Chi phí trực tiếp ............................................................................... 56 2.3.3.3. Giá thành toàn bộ dự án ................................................................... 57 2.3.4. Cân đối giá thành ................................................................................... 58 2.3.5. Thuật toán tối ưu chi phí và giá thành .................................................... 61 CHƯƠNG 3. ÁP DỤNG XÂY DỰNG CHO CÁC DỰ ÁN XÂY DỰNG .......... 64 3.1. Phân tích cấu trúc, thuật toán của chương trình ............................................. 64 3.2. Xây dựng phần mềm ...................................................................................... 68 3.2.1. Lưu đồ thuật toán phần mềm .................................................................. 68 3.2.2. Xây dựng thư viện kết nối từ phần mềm tới CSDL ................................ 69 3.3. Các form giao diện ......................................................................................... 70 KẾT LUẬN .............................................................................................................. 73 TÀI LIỆU THAM KHẢO ...................................................................................... 74
v DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT 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á CSDL: Cơ Sở Dữ Liệu
vi DANH MỤC CÁC BẢNG Bảng 2.1. Các công việc của một dự án .................................................................... 32 Bảng 2.2. Bảng các công việc và thông số về thời gian và chi phí ........................... 58 Bảng 3.1. Danh mục công việc ................................................................................. 69 Bảng 3.2. Thứ tự thực hiện các công việc ................................................................. 69 Bảng 3.3. Các công việc cần thực hiện ..................................................................... 70
vii DANH MỤC CÁC HÌNH Hình 1.1. Tiến độ lắp ghép nhà 1 tầng ....................................................................... 3 Hình 1.2. Tiến độ lắp ghép khung nhà sau khi thêm các mũi tên và vòng tròn. ........ 3 Hình 1.3. Sơ đồ mạng thể hiện tiến độ lắp ghép khung nhà. ...................................... 4 Hình 1.4. Sơ đồ mạng ban đầu ................................................................................. 12 Hình 1.5. Sơ đồ mạng sau khi đã tính các giá trị khởi sớm ..................................... 12 Hình 1.6. Sơ đồ mạng sau khi đã tính các giá trị khởi muộn ................................... 13 Hình 1.7. Sơ đồ mạng sau khi đã xác định đường găng .......................................... 13 Hình 1.8. Hàm phân bố xác suất  của thời gian sự kiệ ........................................... 16 Hình 1.9. Đường cong chuẩn. ................................................................................... 18 Hình 1.10. Ví dụ minh họa - Sơ đồ mạng ban đầu.................................................... 22 Hình 1.11. Sơ đồ mạng sau khi chuyển lên trục thời gian ........................................ 23 Hình 1.12. Sơ đồ mạng trước khi chuyển sang dạng sơ đồ mạng ngang .................. 24 Hình 1.13. Sơ đồ mạng sau khi đã chuyển thành dạng sơ đồ ngang (PERT-GANTT) .... 25 Hình 2.1(a). Biểu đồ sử dụng tài nguyên tốt ............................................................. 39 Hình 2.1(b). Biểu đồ sử dụng tài nguyên chấp nhận được........................................ 39 Hình 2.1(c). Biểu đồ sử dụng tài nguyên không tốt .................................................. 40 Hình 2.2. Biểu đồ tài nguyên .................................................................................... 43 Hình 2.3(a). SĐM ban đầu theo thời gian sớm nhất và biểu đồ nhân lực ban đầu ... 46 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 ....................................................................... 47 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 ............................................................................ 48 Hình 2.4. Đồ thị biểu diễn mối quan hệ giữa chi phí thời gian và giá thành ............ 54 Hình 2.5. Đồ thị chi phí gián tiếp .............................................................................. 56 Hình 2.6. Đồ thị chi phí trực tiếp .............................................................................. 56 Hình 2.7. Rút ngắn thời gian bằng phương pháp sơ đồ mạng .................................. 59 Hình 2.8. Sơ đồ mạng sau khi rút ngắn công việc E. ................................................ 59 Hình 3.1. Lưu đồ thuật toán phần mềm .................................................................... 68 Hình 3.2. form nhập số liệu ....................................................................................... 70
viii Hình 3.3. form xử lý số liệu ...................................................................................... 71 Hình 3.4. form biểu đồ kết quả ................................................................................. 71 Hình 3.5. form giới thiệu chương trình ứng dụng ..................................................... 72 Hình 3.6. In biểu đồ công việc .................................................................................. 72
1 MỞ ĐẦU Để thực hiện nhiều việc chúng ta phải thự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ản xuất; các công đoạn để hoàn thành một công trình xây dựng, một công trình khoa học hay một chiến dịch quảng bá sản phẩm…., những việc lớn như vậy được gọi chung là dự á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 để đả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ời gian để vẫn đảm bảo kế hoạch? - Những công việc nào 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 để đảm bảo sự tối ưu giữa chi phí và giá thành? Khi chưa có những phần mềm chuyên dụng cho quản lý dự án thì những người quản lý dự á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. Quản lý dự án là một trong những khâu được đánh giá là có vai trò quan trọng quyết định sự thành công của một dự án. Việc nghiên cứu để đưa ra các thuật toán giúp xây dựng một phần mềm hỗ trợ những tính toán một cách tự động các bài toán liên quan trong bài toán quản lý dự án tổng thể sẽ tạo thuận lợi trong việc quản lý dự án, giúp quá trình quản lý được mềm dẻo, linh hoạt và đạt hiệu quả cao. Đề tài 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 tảng lý thuyết cần thiết về sơ đồ mạng, lý thuyết đồ thị,… làm cơ sở cho việc phân tích và đưa ra thuật toán để giải các bài toán trong quản dự án gồm: Bài toán lập và điều khiển tiến độ; Bài toán phân phối tài nguyên; Bài toán cân đối chi 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.
2 CHƯƠNG 1. CƠ SỞ LÝ THUYẾT 1.1. Phương pháp sơ đồ mạng 1.1.1. Khái niệm về sơ đồ mạng Sơ đồ mạng dựa trên hai yếu tố cơ bản là công việc (task) và sự kiện (event). Trong sơ đồ mạng các công việc biểu hiện cụ thể và sinh động, không chỉ thấy tên công việc mà còn cho thấy mối quan hệ với các công việc khác. Để lập được sơ đồ mạng cần phân tích trình tự các công việc; những mối liên hệ về công nghệ hoặc logic về tổ chức. Nó là một mô hình toán học động, thể hiện dự án thành một thể thông nhất, chặt chẻtrong đó thấy rỏ vị trí cuả từng công việc với mục tiêu chung và ảnh hưởng qua lại giữa các công việc. Ưu điểm của sơ đồ mạng là: - Dễ nhận biết mối quan hệ giữa các công việc, quá trình công nghệ, sự phát triển logic của lịch trình - Phát hiện đường đi dài nhất (đường găng) từ khi khởi đầu đến khi kết thúc - Thuận tiện khi sử dụng các công cụ toán học khác như quy hoạch tuyến tính, các phần mềm có sẳn như MS Project, CA project ...; lý thuyết xác suất.. Hai dạng lý thuyết sơ đồ mạng phổ biến là: PP đường găng CPM (Critical Path Method) và PP kỹ thuật đành giá và kiểm tra PERT (Program Evaluation and Review Technique). Hai phương pháp này được sử dụng vào năm 1958-1960 trong dự án chế tạo tên lửa Polaris của hải quân Mỹ. Về hình thức sử dụng mạng là một mô hình mạng lưới gồm những đường và nút thể hiệm mối quan hệ giữa các công việc với nhau Để 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 tầng, ta có các công việc chính sau: 1. Làm móng mất 5 ngày. 2. Vận chuyển cần trục về mất 1 ngày. 3. Lắp dựng cần trục tháp mất 3 ngày. 4. Vận chuyển cấu kiện mất 4 ngày. 5. Lắp ghép khung nhà mất 7 ngày.
3 Ta sử dụng sơ đồ ngang (là một hệ toạ độ vuông góc, trục tung thể hiện tên công việc, trục hoành thể hiện thời gian) để lập tiến độ lắp ghép khung nhà này. Thời gian TT Tên công việc 1 2 3 4 5 6 7 8 9 10 11 12 1 Làm móng nhà 2 Vận chuyển cần trục 3 Lắp dựng cần trục 4 Vận chuyển cấu kiện 5 Lắp ghép khung nhà Hình 1.1. Tiến độ lắp ghép nhà 1 tầng Ta dùng các vòng tròn để đánh dấu thời điểm bắt đầu hay kết thúc một công việc, còn mỗi công việc được ký hiệu bằng một mũi tên nối thời điểm bắt đầu và kết thúc công việc đó. Theo tiến độ trên, công việc làm móng, vận chuyển cần trục và vận chuyển cấu kiện có thể tiến hành đồng thời và không phụ thuộc lẫn nhau. Còn công việ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ông trườ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 để nối các công việc có liên quan đến nhau, được sơ đồ mới: Hình 1.2. Tiến độ lắp ghép khung nhà sau khi thêm các mũi tên và vòng tròn.
4 Tiếp tục đơn giản sơ đồ trên hình 1.2, bằng cách đánh số thứ tự các vòng trò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 đầu, ta được một sơ đồ gọi là sơ đồ mạng như sau: Làm móng 3 Vc cần trục Lắp cần trục Lắp khung 1 2 6 5 Vc cấu kiện 4 Hình 1.3. Sơ đồ mạng thể hiện tiến độ lắp ghép khung nhà. Định nghĩa sơ đồ mạng : Là một hệ thống các công việc được sắp xếp theo mộ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ạo nê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 tất 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 ảnh củ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. 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 ta gọ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ện củ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ử dụng,…Giải pháp trong trường hợp này là sử dụng đồ thị có hướng với các nút biể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. Ví 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:
5 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ề mất 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à mất 7 ngày với 15 nhân công. Biểu diễn các công việc ở các đỉnh 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 Làm móng 5 10 0 Vận chuyển Lắp dựng cần trục Lắp ghép cần trục 1 3 khung nhà 3 5 0 7 15 2 1, 3, 4 Vận chuyển cấu kiện 4 7 0 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 (Task) Danh từ công việc ở đâ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: Đổ bê tông 5 4 4 ngày
6 Công việc thực: là công việc cần sự chi phí về thời gian và tài nguyên hoặc chỉ 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 bằng một nét liền. Cô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ói 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ông việc ảo không đòi hỏi sự chi phí về tài nguyên cũng như thời gian, nó được thể hiện bằng một nét đứt. Đào móng Lắp ghép móng 1 2 3 4 5 ngày 2 ngày 2. Sự kiện (Event) Sự kiện là mốc đánh dấu sự bắt đầu hay kết thúc của một hoặc nhiều công việc. Sự kiện còn được gọi là mốc chính. Sự kiện được thể hiện bằng vòng tròn, gọi là vòng tròn sự kiện hoặc một hình tuỳ ý. Trong sơ đồ mạng sự kiện, mỗi sự kiện là một đỉnh của đồ thị. Sự kiện được ký hiệu bằng một số hoặc chữ cái. 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 (Resource) Trong sơ đồ mạng, tài nguyên được hiểu là thời gian và vật chất cầ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à tij là khoảng thời gian để hoàn thành công việc theo ước lượng, ấn định trước hoặc tính toán, coi đó là trọng số mỗi cung trong đồ thị sự kiện. 5. Đường (Path), đường găng Đường là một chuỗi các công việc được sắp xếp sao cho sự kiện cuối củ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 được tính theo thời gian, bằng tổng thời gian các công việc nằm trên đường.
7 Độ dài của một đường trong sơ đồ mạng là tổng trị số độ dài các cung của nó, ký hiệu là L() 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. L() = t(u) u Đường găng 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 Dij = 0 hoặc, dij = 0. 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ữ Di =0. 6. Thời gian của các sự kiện Thời gian sớm của sự kiện i TSi: là thời điểm sớm nhất của một hoặc nhiều công việc bắt đầu bằng sự kiện i có thể khởi công. Để thiết lập công thức ta ký hiệu tron một nút sự kiện như sau: Trong đó: j g i k T T S i M i h l h i :sự kiện đang xét. TSi:Thời gian sớm của sự kiện đang xét. TMi:Thời gian muộn của sự kiện đang xét. tij:Thời gian của công việc i-j. h :Sự kiện đi đến i có đường dài nhất. 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 : TS1 = 0 TSj = max TSi  tij :  i là sự kiện trước đi tới j (j>1) 
8 Thời gian muộn của các sự kiện i (TMi) : là thời điểm muộn nhất của một hoặc nhiều công việc bắt đầu bằng sự kiện i 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 i với điều kiện : TMn = TSn TMi = min  TMj -tij :  j là sự kiện kết thúc của công việc i-j (i
9 Và kết muộn nếu nó kết thúc ở thời điểm muộn của sự kiện sau: Tk.mij = TMj 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: Tk.mij = Tkh.mij tij 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 : TSij , TMij , TKh..sij , Tk.sij , tuy nhiên chỉ cần tính được thời gian sớm, muộn của sự kiện là có thể suy ra thời gian sớm, muộn của công việc mà tuỳ theo vị trí của sự kiện là đầu hay cuố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 (Dij ) : 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ó để thay đổi các thời điểm khởi-kết sớm, khởi-kết muộn hoặc kéo dài thời gian công việc tij thì chỉ làm ảnh hưởng đến các công việc trướ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: Dij = TMj - TSi - tij Dự trữ bé nhất (dij) : còn gọi là dự trữ độc lập, dự trữ riêng. Khi sử dụng sẽ không làm ảnh hưởng đến các công việc trước và sau nó. Người ta gọi là dự trự trữ độc lập vì dự trữ này không bị công việc nào chi phối. dij = TSj - TMi - tij Trong thực tế, dự trữ lớn nhất được sử dụng nhiều hơn trong các trường hợp: điều chỉnh biểu đồ nhân lực, kéo dài thời gian của các công việc, điều hoà tài nguyên. Trên đây là một số khái niệm cơ bản có liên quan đến sơ đồ mạng. Như chúng ta đã biết, có rất nhiều phương pháp sơ đồ mạng sau đây là hai phương pháp sơ đồ mạng sự kiện để giải quyết một số bài toán trên thực tế.
10 1.1.2. Phương pháp đường găng CPM. 1.1.2.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 được thự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ới cá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 ước lượ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 chịu ảnh hưởng về sự thay đổi thời gian mà có thể ảnh hưởng lớn đến thờ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 và ứng dụng rộng rãi trong bất kỳ lĩnh vực nào. 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ông việc nào quan trọng cần thiết phải hoàn thành đúng thời hạn để 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 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ệc phả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ý do 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.1.2.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 sơ đồ mạng, 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: