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. Phương pháp sơ đồ mạng 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. 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. Vận chuyển cần trục về mất 1 ngày. Lắp dựng cần trục tháp mất 3 ngày. Vận chuyển cấu kiện mất 4 ngày.
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. 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.
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. 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. Vận chuyển cần trục về mất 1 ngày với 3 nhân công.
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. Vận chuyển cấu kiện mất 4 ngày với 7 nhân công. 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 khung nhà 1 3 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. 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ị,. 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.
