ĐẠ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
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à
9 10 11 12
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,
Làm móng
3
Lắp khung
Vc cần trục
ta được một sơ đồ gọi là sơ đồ mạng như sau:
6
2
5
Vc cấu kiện
4
Lắp cần trục 1
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.
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 10 5
0
Vận chuyển cần trục 3 1
Lắp dựng cần trục 5 3
Biểu diễn các công việc ở các đỉnh gồm các thông tin :
0
2
1, 3, 4
Vận chuyển cấu kiện 7 4
0
Lắp ghép khung nhà 15 7
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
5
4
hai sự kiện trước và sau. Có loại hai công việc:
Đổ bê tông 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
Đào móng
1
2
3
4
5 ngày
Lắp ghép móng 2 ngày
bằng một nét đứt.
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.
u
L() = t(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 TS
i: 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:
j
g
Trong đó:
k
i TM
i
i
l
h
h
T S
i :sự kiện đang xét.
i:Thời gian sớm của sự kiện đang xét.
TS
i:Thời gian muộn của sự kiện đang xét.
TM
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 :
1 = 0
TS
j = max TS
i tij : i là sự kiện trước đi tới j (j>1)
TS
8
Thời gian muộn của các sự kiện i (TM
i) : 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 :
n = TS n
TM
i = min TM
j -tij : j là sự kiện kết thúc của công việc i-j (i TM Thời gian dự trữ của sự kiện : Là khoảng chênh lệch giữa hai thời điểm thời gian muộn và thời gian sớm của sự kiện. i - TS
i Thời gian dự trữ của sự kiện i : Di = TM Đó là thời gian mà sự kiện có thể làm chậm lại mà không làm ảnh hưởng tới thời hạn hoàn thành dự án. 7. Thời gian của các công việc Thời gian sớm của các công việc: ij) và kết sớm (Tk.s ij). Một công việc i-j có hai thời điểm sớm : khởi sớm (TKh.s Hiển nhiên, một công việc là khởi sớm nếu nó bắt đầu ở thời điểm sớm của sự kiện đầu ij = TS
i TKh.s Và nó sẽ là kết sớm nếu nó kết thúc sớm ở thời điểm sớm của sự kiện sau: ij = TS
j Tk.s Theo tính toán phần 6) ta có : j = Ts i + tij Ts ij = Tkh.s ij tij nên: Tk.s Khi thời gian của công việc không đổi thì công việc được kết thúc sớm nếu nó được khởi sớm. Thời gian muộn của các công việc( TM Tương tự như thời gian sớm của các công việc một công việc là khởi muộn nếu nó bắt đầu ở thời điểm muộn của sự kiện đầu: ij = TM
i Tkh.m 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: ij = TM
j Tk.m 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: ij = Tkh.m ij tij Tk.m 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 ij , TM ij , TKh..s ij , Tk.s ij , tuy việc gồm hai sự kiện đầu và cuối nên có 4 thời gian : TS 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: j - TS i - tij Dij = TM 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. j - TM i - tij dij = TS 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: 11 Trong đó: j :sự kiện đang xét. i :sự kiện đứng trước có đường đi dến dài nhất. Nếu đến j có nhiều đường dài bằng nhau thì phải ghi lại hết các chỉ số sự kiện đó. TS : Thời gian sớm của sự kiện đang xét.
TM :Thời gian muộn của sự kiện đanng xét. Các bước tính toán của phương pháp CPM như sau: Bước1: Lượt đi(tính từ trái sang phải). Tính các thời điểm sớm của sự kiện( TS ). 1 = 0. Bắt đầu từ sự kiện xuất phát TS Sự kiện tiếp theo nếu chỉ có một công việc đi đến, tính theo công thức: j = TS i + tij TS Nếu có nhiều công việc đi đến, thời gian sớm được tính theo công thức j = max TS i + tij; TS h + thj ; ... TS Sự kiện nào đứng trước có đường đi đến sự kiện đang xét bằng đường dài nhất được ghi ở ô bên dưới của sự kiện đang xét. Lặp lại việc tính toán trên theo thứ tự tăng dần của các chỉ số sự kiện cho đến sự kiện hoàn thành thì kết thúc bước 1. Bước 2: Lượt về (tính từ phải sang). Tính thời điểm muộn của sự kiện( TM) n = TS n. Bắt đầu từ sự kiện cuối cùng TM Tính ngược lại sự kiện (n-1), (n-2), ... ta có công thức: i = TM j - tij TM i được tính theo Nếu có nhiều công việc có thể lùi đến sự kiện đang xét i, TM công thức: i = min TM j - tij; TM k - tik ; ... TM Cứ như vậy ta tính lùi đến sự kiện xuất phát số 1 ta kết thúc bước hai. Bước 3: Xác định đường găng Điều kiện cần và đủ của đường găng là đi qua các sự kiện găng và là đường dài nhất. Để xác định đường găng ta chia thành hai giai đoạn: 12 Giai đoạn 1: Đi từ sự kiện đầu đến sự kiện cuối. Đánh dấu tất cả những sự kiện găng( những sự kiện có dự trữ Di = 0). Giai đoạn 2 : Từ các sự kiện cuối cùng, ta lùi về các sự kiện găng bằng các chỉ số ghi ở ô dưới của sự kiện. Làm tương tự như trên cho đến sự kiện xuất phát 1, ta sẽ thu được đường găng. Một dự án có thể có nhiều đường găng . Ví dụ: Cho sơ đồ mạng sự kiện biểu diễn bằng đồ thị sau: 2 4 2 6 1 3 5 Hình 1.4. Sơ đồ mạng ban đầu Trong sơ đồ hình 1.4, có 6 sự kiện được đánh số từ 1 – 6 tại các đỉnh. Trọng số trên cạnh từ i đến j là thời gian thực hiện tij của công việc, thực hiện khi sự kiện i kết thúcđến lúc sự kiện j bắtđầu. Theo các bước tính toán theo phương phápđường găng tại mỗi bước tính toán thu đượcđồ thị của mạng như sau: Bước 1: Lượt đi tính các giá trị TS từ trái sang phải, ta được kết quả sau: Hình 1.5. Sơ đồ mạng sau khi đã tính các giá trị khởi sớm 13 Bước 2 : Lượt về tính từ phải sang trái các giá trị TM ta có hình vẽ: Hình 1.6. Sơ đồ mạng sau khi đã tính các giá trị khởi muộn Bước 3 :Xác định đường găng Hình 1.7. Sơ đồ mạng sau khi đã xác định đường găng 1.1.3. Phương pháp sơ đồ mạng PERT 1.1.3.1. Khái niệm cơ bản về phương pháp PERT Trong các phương pháp sơ đồ mạng thì phương pháp PERT được nhiều người biết đến hơn cả PERT có nghĩa là, ki thuật ước lượng và kiểm tra dự án (Progtam Evaluation and Review Techmque). Nhung PERT được coi nhu đồng nghĩa với phuong phâp sơ đồ mạng lí do sau: - Trước hết là kết quả đáng chú ý khi ở Mĩ người ta sử dụng PERT để điều khiển việc xây dựng hệ thống tên lửa Polaris vào năm 1958 đã rút ngắn thời gian xây dựng từ 5 5 năm xuống còn 3 năm. Sau đó PERT được phổ biến rất nhanh chóng sang các lĩnh vực khác trong nền kinh tế quốc dân Ơ Mĩ. Vì vậy PERT được người ta chú ý và biết đến nhiều hơn với thói quen gọi PERT là phương pháp sơ đồ mạng Thực tế, các phương pháp CPM và PERT được phát triển gần như đồng thời và PERT chỉ là một trong các phương pháp sơ đồ mạng. 14 Ví dụ : Khi cần đóng một hệ thống cọc để gia cố nền của một tòa nhà, người điều khiển thi công dự tính làm trong 1 tháng. Có khi do chuẩn bị các mặt tốt, công tác tiến hành trong thời tiết thuận lợi, nên thời gian chỉ hết 20 ngày. Nhưng khi gặp khó khăn về thời tiết, về dụng cụ. . . thời gian hoàn thành là 35 ngày, mất nhiều thời gian hơn kế hoạch dự tính. Như vậy vấn đề được đặt ra là: Phải xử lí tình trạng không ổn định về thời gian như thể nào để rút ra được những kết luận đáng tin cậy và có thể sử dụng được trong thực tế thi công. Muốn giải quyết vấn đề này có thể vận dụng các phương pháp của lí thuyết xác suất thống kê, để nghiên cứu PERT và đó cũng là một ưu điểm nổi bật trong các ưu điểm của phương pháp PERT. Đối với phương pháp CPM thì sơ đồ mạng là một mô hình xác định. Còn phương pháp PERT lại đưa yếu tố không xác định (hay còn gọi là yếu tố ngẫu nhiên) vào, khi ước lượng thời gian thực hiện các công việc và thời gian hoàn thành dự án ; do đó nó rất phù hợp với những trường hợp, nhũng số liệu ban đầu và các công việc đang được nghiên cứu thực hiện chưa có định mức. Chúng ta sẽ nghiên cứu những điểm khác biệt của phương pháp PERT với CPM, còn những vần đề cơ bản về quy tắc lập mạng, tính toán thời gian... cũng giống như CPM nên không nhắc lại. PERT có nghĩa là kỹ thuật ước lượng và đánh giá (Program Evaluation and Review Technical), nhưng PERT được coi như đồng nghĩa với sơ đồ mạng. Trên thực tế, PERT và CPM ra đời gần như đồng thời và PERT cũng chỉ là một trong các phương pháp sơ đồ mạng. PERT là một mô hình mạng cho phép có sự ngẫu nhiên trong việc linh động về thời gian hoàn thành của dự án. PERT được phát triển vào những năm 1950 trong dự án của một người Mỹ Navy’s Polaris với hành nghìn thầu khoán. Nó giúp giảm thời gian và chi phí để hoàn thánh dự án. Khác với phương pháp CPM là phương pháp coi thời gian là một hằng số. Nhưng trong thực tế thường gặp rất nhiều yếu tố ngẫu nhiên tác động đến dự án (điều kiện thời tiết, việc cung cấp nhân công, thiết bị,...) nên thời hạn hoàn thành dự án nhiều khi không cố định. Vấn đề đặt ra là phải xử lý tình trạng không ổn định về thời gian đó như thế nào để rút ra những kết luận đáng tin cậy và có thể sử dụng được trong thi công. Muốn giải quyết vấn đề này cần vận dụng các phương pháp của lý thuyết thống kê. PERT đã đưa vào kế hoạch của dự án yếu tố ngẫu nhiên và 15 đó cũng chính là ưu điểm nổi bật của phương pháp. Nó đặc biệt phù hợp với những trường hợp lần đầu thực hiện công việc hoặc mới sử dụng các kỹ thuật mới khi mà những số liệu ban đầu đưa vào chưa có định mức sẵn. PERT được xây dựng dựa trên lý thuyết đồ thị nhưng khi sử dụng nó ta cần đến những kiến thức cơ bản của lý thuyết thống kê như : hàm phân phối xác suất, giá trị trung bìmh, Mode, biên độ, phương sai, độ lệch tiêu chuẩn. 1.1.3.2. Ước lượng thời gian hoàn thành công việc Mỗi công việc thường có một định mức thời gian thực hiện dựa trên công nghệ và tài nguyên sử dụng (thiết bị, nguyên liệu, lao động...). Khi lập kế hoạch thi công người ta dựa trên kinh nghiệm để ước lượng thời gian hoàn thành công việc. Vì vậy thời gian đó không xác định, ta phải lấy thời gian trung bình mong muốn (tức kỳ vọng) kèm theo độ lệch tiêu chuẩn hoặc phương sai V của thời gian. Thời gian trung bình mong muốn là thời gian ước lượng với 50 khả năng thực hiện sớm và 50 thực hiện chậm. Vì thế, để xác định số liệu của mỗi công việc cần sử dụng hàm phân bố của thời gian thực hiện công việc. Nhưng có một vấn đề khác là ta không hề có thông tin về sự phân bố xác suất của thời gian thực hiện công việc (vì nó phụ thuộc vào những biến động kéo dài ngẫu nhiên), do đó phải giả thiết 1 hàm phân bố xác xuất phù hợp cho từng hoàn cảnh của từng trường hợp cụ thể. Có 3 ước lượng thời gian được đặt ra và được nằm trong đường cong lý thuyết: 1) Thời gian lạc quan ( ) là thời gian ước lượng ít nhất để hoàn thành công việc trong những điều kiện thuận lợi nhất. 2) Thời gian bi quan ( ) là thời gian ước lượng lớn nhất để hoàn thành công việc trong những điều kiện thuận lợi nhất. 3) Thời gian thực hiện ( ) là thời gian ước lượng để hoàn thành công việc có nhiều khả năng xảy ra nhất, tức là có xác suất lớn nhất, còn gọi là Mode của công việc. Do phải ước lượng 3 thời gian này, buộc người lập kế hoạch phải quan tâm đến các khó khăn của từng công việc. Các ước lượng có xu hướng loại bỏ ảnh hưởng của các số liệu đã định sẵn của người lập kế hoạch. Chúng trở thành các điểm để thiết lập đường cong phân bố xác suất cho thời gian thực hiện. 16 Giả thiết thời gian hoàn thành công việc là một đại lượng ngẫu nhiên tuân theo luật phân phối với hàm mật độ xác suất có dạng hàm . f Đỉnh Mode của thời
gian Khoảng các công việc dự
kiến hoàn thành Trung độ thời gian trung
bình mong muốn Thời gian 0 c là hằng số được chuẩn hoá xác định từ điều kiện : ta tm t tb Hình 1.8. Hàm phân bố xác suất của thời gian sự kiệ Khi có thời gian phân phối thì kỳ vọng thời gian được tính bằng công thức thực nghiệm sau : Giả thiết, độ lệch tiêu chuẩn , là giá trị đo độ tản mạn của đường cong xác suất xung quanh giá trị trung bình của nó. Phương sai được tính theo công thức: Sở dĩ ta chọn làm phân bố cho t vì đại lượng ngẫu nhiên có hàm phân bố chỉ phụ thuộc vào các nhân tố có tác động rất nhỏ và rất lớn. Từ công thức tính t và dựa vào đồ thị của hàm thì nhìn chung giá trị trung bình luôn sai khác giá trị thời gian có có xác suất cao nhất . Ta cũng có thể thấy rằng và có xác suất xảy ra rất nhỏ, chúng chỉ có tác dụng xác định một cách gần đúng phạm vi của phân bố thời gian có thể của công việc. Người ta cũng có thể
dùng công thức: 17 để tính thời gian trung bình mong muốn của công việc, nhưng về cơ bản độ chính xác không khác nhau nhiều. Vì vậy trong những tính toán dưới đây ta sẽ dùng công thức: với độ lệch tiêu chuẩn (hay sai số): 1.1.3.3. Các thông số thời gian trong sơ đồ mạng PERT Giá trị ước lượng trung bình và phương sai V của thời hạn hoàn thành công việc được sử dụng để đánh giá các thời điểm hoàn thành sự kiện. Trong PERT, thời gian sớm của sự kiện được tính như sau: 1 = 0 TS j = max (TS i + TS ) Tuy nhiên mỗi thời gian trong phương pháp PERT có thêm độ lệch tiêu chuẩn hay phương sai của nó, để đo sai số khi ta dùng kỳ vọng t làm ước lượng cho thời gian. Vì vậy đi đôi với việc tính TS của sự kiện, phải tính thêm phương sai sớm của sự kiện ấy: 1 = 0 VS j = VS 1 +Vij VS Thời gian muộn của sự kiện được tính như sau: 1 = TS
n TM j = min (TS i - TM ) Phương sai muộn được tính như sau: 1 = 0 VM j = VM 1+Vij VM Việc xác định đường găng của PERT cũng giống như phương pháp CPM ta đã trình bày ở trên. Thời gian thực hiện dự án Tx chính là thời gian trung bình mong muốn của các công việc nằm trên đường găng. Với dự án có thời gian thực hiện là Tx thì phương sai Vx là tổng các phương sai riêng của các công việc nằm trên đường găng đó. 18 Vx = V Trong các trường hợp có nhiều đường găng thì phương sai thực hiện dự án sẽ là phương sai lớn nhất của các dự án đó. 1.1.3.4. Tính xác suất hoàn thành công việc Thực tế quản lý dự án theo phương pháp PERT, vấn đề đặt ra là cần phải tính được xác suất hoàn thành theo thời hạn kế hoạch đã định Tk . Theo lý thuyết xác suất, thời gian trung bình mong muốn của một sự kiện và độ lệch tiêu chuẩn của nó đã xác định ta có thể tính được xác suất hoàn thành dự án theo kế hoạch. Thời gian thực hiện sự kiện được xem như một đại lượng phân bố ngẫu nhiên có hàm phân bố chuẩn mà kỳ vọng chính là Tx , độ lệch tiêu chuẩn là x . Mặt khác, thời gian hoàn thành công việc là đại lượng có phân bố chuẩn . Điều này chỉ đúng trong việc cộng y = f(x) Đường cong chuẩn một số lượng lớn vô hạn các đường cong (khoảng hơn 100 đường). Tn TkThời gian 0 Hình 1.9. Đường cong chuẩn. Xác suất để hoàn thành theo thời hạn kế hoạch PTk là: Diện tích phần gạch chéo P0STk = Diện tích phần bên dưới đường cong 2 . Khi đó, Trong đó, S-đại lượng ngẫu nhiên biểu thị thời gian hoàn thành dự án. Mặt khác, ở đấycó phân bố chuẩn với kỳ vọng Tn và phương sai n S có hàm mật độ xác suất: 19 Đổi biến: t = 0 thì z = Ta có: t= Tk thì z = Nên Với là các đại lượng ngẫu nhiên có phân phối chuẩn: Theo quy tắc k-sigma: Từ và ta dễ dàng tính được N là số phép thử Ta đánh giá được sai số của các ước lượng thời gian: Trong khoảng có P = 68 không hoàn thành kế hoạch. Trong khoảng tương đương với k = 2 có P = 95 là không hoàn thành đúng kế hoạch. Trong khoảng thời gian có P = 99 không hoàn thành kế hoạnh. 20 Từ giá trị của hàm phân phối chuẩn theo x, ta lập được bảng xác xuất của P theo giá trị z và sẽ đánh giá được khả năng hoàn thành dự án theo kế hoạch. Ví dụ : Thời hạn kế hoạch là =17 ngày Thời hạn trung bình là =13,5 ngày Độ lệch tiêu chuẩn là 2 ngày khi đó : = 1,8 Tra bảng phân phối chuẩn ta thu được P=0,964 Như vậy là công trình có nhiều khả năng hoàn thành kế hoạch trước thời gian đã định. Theo phương pháp CPM nếu phải rút bớt thời gian kế hoạch thì phải bằng một cách nào đó chẳng hạn tăng thêm nhân lực, thêm máy móc thiết bị cho các công việc găng cần rút ngắn thời gian. Nhưng trong phương pháp PERT thì rút ngắn 3,5 ngày có thể đạt được mà không cần phải rút ngắn thời gian các công việc găng vì các thời gian trong PERT là ước lượng và thời gian trung bình vẫn có thể rút ngắn được trong những điều kiện thuận lợi. Như vậy trong phương pháp PERT ta chấp nhận cả những tác động của các yếu tố khách quan. Thời gian theo kế hoạch được dự kiến hoàn thành theo một xác suất nào đấy. Đó chính là một quy luật của thế giới ngẫu nhiên trong PERT và cũng là ưu điểm lớn nhất của phương pháp này. 1.2. Ứng dụng sơ đồ mạng trong quản lí tiến độ dự án 1.2.1. Sơ đồ mạng trên trục thời gian Sơ đồ mạng có nhược điểm là bằng trực giác khó nhận ra, tại một thời điểm nào đó có bao nhiêu công việc đang làm? Công việc nào mới bắt đầu và công việc nào mới kết thúc? Do đó khi tính toán xong Sơ đồ mạng, thường người ta chuyển Sơ đồ mạng lên trục thời gian. Trình tự chuyển sdm lên trục thời gian: - Kẻ trục thời gian - Vẽ đường găng lên trục thời gian trước (đường găng sẽ được tô đậm). Nếu có nhiều đường găng thì vẽ thành những đường song song với trục thời gian - Sắp xếp các công việc không găng thành những đường nhỏ hơn và song song với trục thời gian 21 Nếu sơ đồ mạng chúng ta thấy được mối quan hệ trước sau, ràng buộc giữa các công việc nhưng không thể biết rõ tỷ lệ thời gian. Một yêu cầu kết xuất của các chương trình có sơ đồ mạng là phải thể hiện mối liên hệ giữa các công việc theo tỉ lệ thời gian. Kết quả này hỗ trợ cho người quản lý dự án có một cái nhìn tổng quan về toàn bộ thời lượng của dự án. Hơn nữa, tại mỗi thời điểm, người quản lý cũng có thể xác định được những công việc đã hoàn thành, những công việc đang thực hiện và những công việc nào chuẩn bị thực hiện. 1.2.2. Đưa sơ đồ mạng lên trục thời gian Phương pháp đưa sơ đồ mạng lên trục thời gian rất đơn giản. Ta có thể làm như sau: - Trước hết xác định một trục thời gian tính theo ngày. - Kéo căng các đường găng lên trục thời gian trước. Nếu có nhiều đường găng thì sẽ biểu diễn bằng các đường song song với trục thời gian. Đường găng sẽ được kí hiệu phân biệt với các đường không găng. - Sắp xếp các công việc không găng thành những đường cũng song song với trục thời gian nhưng phân biệt với các đường găng bởi một ký hiệu nào đó. Ta có thể chuyển sơ đồ mạng lên trục thời gian theo 2 cách. Cách 1 làm cho các công việc đều khởi sớm, cách 2 làm cho các công việc đều khởi muộn. Nhưng cách 1 hay được dùng vì khi đó các dự trữ sẽ dồn về sau, điều đó có lợi cho việc điều chỉnh tiến độ. 22 Ví dụ: Cho sơ đồ mạng như hình vẽ dưới đây Hình 1.10. Ví dụ minh họa - Sơ đồ mạng ban đầu Các phương án chuyển sơ đồ mạng lên trục thời gian sẽ như sau: 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 Cách 1: 23 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5 6 7 Cách 2: Hình 1.11. Sơ đồ mạng sau khi chuyển lên trục thời gian 1.2.3. Chuyển sơ đồ mạng sang sơ đồ ngang Do có một số nhược điểm khi tính biểu đồ nhân lực, nên chuyển Sơ đồ mạng sang Sơ đồ mạng ngang, mà ta còn gọi là sơ đồ Pert-Gantt. Sơ đồ mạng ngang kết hợp hai ưu điểm cuả hai Sơ đồ, phục vụ rộng rãi cho nhiều người sử dụng mà không đòi hỏi những kiến thức cao về Sơ đồ mạng. Một cách khác để nhận biết rõ hơn 1 công việc được làm từ ngày nào đến ngày nào và tại mỗi thời điểm xác định công việc nào đang tiến hành là sử dụng sơ đồ ngang. Tuy sơ đồ ngang không có nhiều ưu điểm bằng sơ đồ mạng nhưng sơ đồ ngang lại có thể giải quyết tốt vấn đề này. Như vậy nếu có một cách chuyển từ sơ đồ mạng sang sơ đồ ngang thì ta sẽ tận dụng được ưu điểm của cả 2 loại sơ đồ này. Chính vì vậy mà người ta đã nghĩ ra cách chuyển sơ đồ mạng sang sơ đồ ngang tạo ra 1 loại sơ đồ mới, gọi là sơ đồ mạng ngang. Việc chuyển đổi tiến hành như sau: Bước1: Vẽ hệ toạ độ với trục hoành là trục thời gian còn trục tung là trục công việc. Bước 2: Biểu diễn các công việc: - Mỗi công việc được biểu thị bằng 1 đoạn thẳng song song với trục thời gian. Độ dài đoạn thẳng chính là thời gian của công việc (tij) 24 - Các công việc ảo được biểu diễn thành 1 điểm. - Trên đoạn thẳng biểu diễn công việc, đầu mút trái biểu diễn sự kiện bắt đầu, đầu mút phải biểu diễn sự kiện kết thúc. - Các công việc găng sẽ được đánh dấu bằng 1 giá trị riêng trong trường dấu. Bước 3: Các công việc được biểu diễn lần lượt theo quy tắc sau: - Các công việc biểu diễn từ dưới lên theo chiều dương của trục tung (trục công việc). - Thứ tự của công việc tăng dần về độ lớn của sự kiện kết thúc. Nếu các công việc có cùng sự kiện kết thúc thì công việc nào có sự kiện đầu nhỏ hơn sẽ xếp trước. Nếu có nhiều công việc cùng kết thúc ở sự kiện i thì các công việc i-j sẽ bắt đầu ở chỉ số i có hoành độ lớn nhất. Ví dụ trong hình 1.12 dưới đây: công việc C7 kí hiệu 4-6 có sự kiện đầu là sự kiện kết thúc của các công việc C3 (2-4) và C5 (3-4). Do đó công việc C7 bắt đầu ở hoành độ kết thúc công việc găng C5 (3-4) là hoành độ lớn hơn so với công việc C3 (2-4). Bước 4: Xác định các dự trữ của các công việc. Ta thấy có nhiều công việc kết thúc ở một sự kiện cuối j nhưng nằm ở những vị trí khác nhau so với trục hoành. Đó là do sự chênh lệch về thời gian của các công việc găng và không găng. Sự chênh lệch này chính là dự trữ của các công việc. Để biểu diễn các dự trữ này, ta sẽ kéo dài đoạn thẳng biểu diễn các công việc không găng bằng một nét đứt, sao cho điểm cuối của đoạn thẳng này trùng với điểm cuối của các sự kiện găng có cùng tên gọi j. Ví dụ trong hình 1.12 sau đây: C3
2 C1 6 1 9 C8 3 C4 5 3 C5
5 C C2 9 C6 Hình 1.12. Sơ đồ mạng trước khi chuyển sang dạng sơ đồ mạng ngang 25 C9 C8 6’ 6 C7 C6 C5 C4 C3 C2 2
2 C1 4 3
3
3
3 5 5
4 5
4
5’
4
4’ 6 1
1 2 2’
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 T ngày Hình 1.13. Sơ đồ mạng sau khi đã chuyển thành dạng sơ đồ ngang (PERT-GANTT) Các công việc C3 (2-4) kết thúc ở ngày thứ 4 nhưng công việc găng C5 (3-4) kết thúc ở ngày thứ 14. Ta kéo dài công việc 2-4 thành 2-4-4’ kết thúc ở ngày thứ 14. Ta thấy C5 dự trữ là 10 ngày. Tương tự công việc C1 dự trữ 1 ngày, C6 dự trữ 4 ngày, C9 dự trữ 3 ngày. 1.2.4. Quy tắc lập sơ đồ mạng sự kiện Chỉ có một sự kiện xuất phát và một sự kiện kết thúc. Mỗi sự kiện đều có công việcđến và công việc đi. Riêng sự kiện đầu chỉ có công việc đi và sự kiện kết thúc chỉ có công việcđến. Trong sơ đồ mạng, sự kiện được đánh số từ nhỏ đến lớn theo hướng từ trái sang phải và từ trên xuống dưới. Tất cả các công việc 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, nghĩa là không được lập thành vòng kín. Những công việc riêng biệt không được ký hiệu bởi cùng một số
Sơđồ mạng cần có dạngđơn giản nhất, không nên có quá nhiều công việc giao cắt nhau. 26 Sơ đồ mạng phải phản ảnh được trình độ ký thuật của công việc và quan hệ kỹ thuật
giữa chúng. 1.3. Tổng quan về quản lí dự án Phương pháp quản lý dự án lần đầu được áp dụng trong lĩnh vực quân sự của Mỹ vào những năm 50 của thế kỷ trước. Các lực lượng cơ bản thúc đẩy sự phát triển phương pháp quản lý dự án là: - Nhu cầu thực tế cho thấy khách hàng ngày càng “khắt khe, khó tính” với các hàng hoá, dịch vụ, dẫn tới sự gia tăng độ phức tạp trong quy trình tổ chức, quản lý sản xuất và chất lượng sản phẩm, dịch vụ. - Kiến thức của con người không ngừng phát triển về tự nhiên, xã hội, kinh tế, kỹ thuật … Quản lý dự án là “ứng dụng kiến thức, kỹ năng, công cụ và kỹ thuật vào các hoạt động dự án để thỏa mãn các yêu cầu của dự án.” (PMI2, Project Management Body of Knowledge (PMBOK® Guide), 2000, p.6). Quản lý dự án là một quá trình hoạch định (Planning), tổchức (Organizing), lãnh đạo (Leading/Directing) và kiểm tra (Controlling) các công việc và nguồn lực để hoàn thành các mục tiêu đã định. Môt dự án được quản lý tốt, tức là khi kết thúc phải thoả mãn được chủ đầu tư về các mặt: thời hạn, chi phí và chất lượng kết quả. Xét theo khía cạnh khác, quản lý dự án là một quá trình lập kế hoạch, điều phối thời gian, nguồn lực và giám sát quá trình phát triển của dự án nhằm đảm bảo cho dự án hoàn thành đúng thời hạn, trong phạm vi ngân sách được duyệt và đạt được các yêu cầu đã định về kỹ thuật, chất lượng của sản phẩm, dịch vụ, bằng các phương pháp và điều kiện tốt nhất cho phép. 1.3.1. Mục tiêu của quản lý dự án Mục tiêu cơ bản của quản lý dự án nói chung là hoàn thành các công việc dự án theo đúng yêu cầu kỹ thuật và chất lượng, trong phạm vi ngân sách được duyệt và theo đúng tiến độ thời gian cho phép. 27 Ba yếu tố: thời gian, nguồn lực (cụ thể là chi phí, nguồn nhân lực …) và chất lượng có quan hệ chặt chẽ với nhau. Tầm quan trọng của từng mục tiêu có thể khác nhau giữa các dự án, giữa các thời kỳ đối với từng dự án, nhưng tựu chung, đạt được tốt đối với mục tiêu này thường phải “hy sinh”, một trong hai mục tiêu kia. Cụ thể, trong quá trình quản lý dự án thường diễn ra các hoạt động đánh đổi mục tiêu. Đánh đổi mục tiêu dự án là việc hy sinh một mục tiêu nào đó để thực hiện tốt hơn các mục tiêu kia trong ràng buộc không gian và thời gian. Nếu công việc dự án diễn ra theo đúng kế hoạch thì không phải đánh đổi mục tiêu. Tuy nhiên, do nhiều nguyên nhân khách quan, cũng như chủ quan công việc dự án thường có nhiều thay đổi nên đánh đổi là một kỹ năng quan trọng của nhà quản lý dự án. 1.3.2. Tác dụng của quản lý dự án Phương pháp quản lý dự án là sự điều phối nỗ lực cá nhân, tập thể; đòi hỏi sự hợp tác chặt chẽ, kết hợp hài hoà giữa các nguồn lực hạn hẹp nên bản chất của nó là: - Liên kết tất cả các hoạt động, các công việc của dự án - Tạo điều kiện thuận lợi cho việc liên hệ thường xuyên, gắn bó giữa các nhóm quản lý dự án với khách hàng và các nhà cung cấp đầu vào cho dự án - Tăng cường sự hợp tác giữa các thành viên và chỉ rõ trách nhiệm của các thành viên tham gia dự án - Tạo điều kiện sớm phát hiện những khó khăn, vướng mắc phát sinh và điều chỉnh kịp thời trước những thay đổi hoặc điều kiện không dự đoán được. Tạo điều kiện cho việc đàm phán giữa các bên liên quan trong việc giải quyết bất đồng cục bộ. - Tạo ra sản phẩm và dịch vụ có chất lượng cao. Tuy nhiên, phương pháp quản lý dự án cũng có mặt hạn chế của nó. Những mâu thuẫn do cùng chia nhau một nguồn lực của đơn vị; quyền lực và trách nhiệm của các nhà quản lý dự án trong một số trường hợp không được thực hiện đầy đủ; vấn đề hậu dự án là những điểm cần được khắc phục với phương pháp quản lý các dự án xây dựng. Thành quả Yêu cầu về
thành quả Mục tiêu Chi phí Thời hạn
quy định Ngân sách
cho phép Thời gian 28 1.3.3. Các giai đoạn của dự án và vòng đời dự án Dự án là một thực thể thống nhất, thời gian thực hiện xác định và có độ bất định nhất định nên các tổ chức, đơn vị thường chia dự án thành một số giai đoạn để quản lý thực hiện. Mỗi gian đoạn được đánh dấu bằng việc thực hiện một hay nhiều công việc. Tổng hợp các giai đoạn này được gọi là chu kỳ hay vòng đời của dự án. Chu kỳ của dự án xác định thời điểm bắt đầu, thời điểm kết thúc và thời gian thực hiện dự án. Chu kỳ dự án xác định những công việc nào sẽ được thực hiện trong từng giai đoạn và ai sẽ tham gia thực hiện. Nó cũng chỉ ra những công việc nào còn lại ở giai đoạn cuối sẽ thuộc về hoặc không thuộc về phạm vi của dự án. Thông qua chu kỳ dự án có thể nhận thấy một số đặc điểm: Vòng đời phát triển dự án (Systems Development Life Cycle - SDLC) là khung làm việc dùng để mô tả các giai đoạn trong quá trình phát triển và duy trì hệ thống. SDLC cơ bản là nhóm các giai đoạn của dự án. Các giai đoạn của dự án thay đổi tùy theo dự án, tổ chức hoặc lãnh vực kinh doanh, thường được chia thành 4 giai đoạn như sau: Giai đoạn xây dựng ý tưởng: Xây dựng ý tưởng là việc xác định bức tranh toàn cảnh về mục tiêu, kết quả cuối cùng của dự án và phương pháp thực hiện dẫn tới kết quả đó. Xây dựng ý tưởng dự án bắt đầu ngay khi hình thành dự án. Khảo sát-tập hợp số liệu, xác định yêu cầu, đánh giá rủi ro, dự tính nguồn lực, so sánh lựa 29 chọn dự án, … là những công việc triển khai và cần được quản lý trong gian đoạn này. Quyết định lựa chọn dự án là những quyết định chiến lược dựa trên mục đích, nhu cầu và các mục tiêu lâu dài của tổ chức, doanh nghiệp. Giai đoạn phát triển: Là giai đoạn chi tiết xem dự án cần được thực hiện như thế nào, nội dung chủ yếu của giai đoạn này tập trung vào công tác thiết kế và lập kế hoạch. Đây là giai đoạn chứa đựng những công việc phức tạp nhất của dự án. Nội dung chủ yếu bao gồm: - Thành lập nhóm dự án, xác định cấu trúc tổ chức. - Lập kế hoạch tổng thể - Phân tích, lập bảng chi tiết công việc - Lập kế hoạch tiến độ thời gian - Lập kế hoạch ngân sách - Lập kế hoạch nguồn lực cần thiết - Lập kế hoạch chi phí - Xin phê chuẩn thực hiện tiếp Giai đoạn thực hiện: Là giai đoạn quản lý tổ chức triển khai các nguồn lực bao gồm các công việc cần thiết như xây dựng phòng ốc, hệ thống, lựa chọn công cụ, mua sắm trang thiết bị, lắp đặt … Đây là giai đoạn chiếm nhiều thời gian và nỗ lực nhất. Những vấn đề cần xem xét trong giai đoạn này là những yêu cầu kỹ thuật cụ thể nhằm so sánh, đánh giá lựa chọn công cụ thiết bị, kỹ thuật lắp ráp, mua thiết bị chính, phát triển hệ thống. Giai đoạn kết thúc: Trong giai đoạn kết thúc của chu kỳ dự án, cần thực hiện những công việc còn lại như hoàn thành sản phẩm, bàn giao hệ thống, công trình và những tài liệu liên quan; đánh giá dự án, giải phóng các nguồn lực. Dưới đây là một số các việc cụ thể: - Hoàn chỉnh và lập kế hoạch lưu trữ hồ sơ liên quan đến dự án o Kiểm tra lại sổ sách kế toán, tiến hành bàn giao và báo cáo - Thanh quyết toán Các dự án thường bao gồm một số quy trình liên kết với nhau. Các quy trình này lặp đi lặp lại và diễn ra trong từng giai đoạn của vòng đời dự án và tác động lẫn 30 nhau. Hình 1-1 mô tả các mối quan hệ giữa các quy trình. Cả 5 quy trình quản lý dự án đều hoạt động tại từng giai đoạn vòng đời dự án, nhưng mỗi quy trình hoạt động có mức độ khác nhau tuỳ theo mỗi giai đoạn. Chẳng hạn như sự lặp lại của quá trình khởi tạo tiến hành ở phần đầu của mỗi gian đoạn nhằm tập trung vào các yêu cầu và mục tiêu nghiệp vụ trong giai đoạn đó. Các quy trình này là: Khởi tạo Lập kế hoạch Thực hiện Kiểm soát Kết thúc - Khởi tạo: Sự cấp phép cho dự án hay giai đoạn nào đó - Lập kế hoạch: Sàng lọc các mục tiêu của dự án và lựa chọn phương án hành động tốt nhất để đạt được các mục tiêu đó - Thực thi kế hoạch: Quản lý, phân bổ các nguồn lực để thực hiện kế hoạch - Kiểm soát: Là giai đoạn giám sát và xem xét mức độ tiến hành trên cơ sở nguyên tắc nhằm xác định những điểm khác biệt so với kế hoạch đã đề ra để thực hiện các hoạt động cần thiết nhằm hiệu chỉnh, đảm bảo dự án đang đi đúng hướng, đáp ứng các mục tiêu của dự án ban đầu. - Kết thúc: Đạt được ký kết hoàn tất từ nhà tài trợ và đưa dự án hoặc giai đoạn đó đến một kết thúc theo thứ tự 31 2.1. Bài toán quản lí tiến độ 2.1.1. Sơ đồ mạng biểu diễn tiến độ dự án Chúng ta sử dụng sơ đồ mạng để biểu diễn tiến độ của dự án. Sơ đồ mạng được biểu diễn trên trục thời gian dễ dàng giúp người quản lý theo dõi tiến độ. Trên đó, ta biết được công việc nào cần hoàn thành đúng thời gian đưa ra và công việc nào có thể trì hoãn, và được phép trì hoãn tối đa trong thời gian bao lâu. Trong khi dữ án đang diễn ra thì không thể không có thay đổi kế hoạch do khách quan hoặc chủ quan, khi đó ta lại thấy rõ tiến trình trên sơ đồ mạng để điều khiển cho hợp lý. 2.1.2. Thuật toán cho bài toán lập và điều khiển tiến độ Sơ đồ mạng diễn tả một dự án bằng mối liên hệ giữa các công việc. Sơ đồ mạng ban đầu chỉ chú ý đến logic giữa các công việc. Quản lý tiến độ một dự án là cần có cái nhìn tổng quan về toàn bộ thời lượng dự án và tại mỗi thời điểm, người quản lý phải xác định được những công việc nào đã hoàn thành, những công việc nào đang thực hiện, những công việc nào chuẩn bị thực hiện. Để giải quuyết vấn đề trên, ta tiến hành đưa sơ đồ mạng lên trục thời gian, chuyển sơ đồ mạng sang sơ đồ mạng ngang. Thuật toán lập và điều khiển tiến độ: Bước 1: Biểu diễn sơ đồ mạng sang sơ đồ ngang. Bước 2: Dựa vào sơ đồ ngang mà người quản lý có thể thay tăng hoặc giảm thời gian hoàn thành công việc của các công việc không nằm trên đường găng. Ta có thể tăng nhiều nhất khoảng thời gian bằng thời gian dự trữ của mỗi công việc mà ta đã tìm ra. Công việc C3 có thời gian dự trữ là đoạn 4-4’, tương ứng với 10 ngày. Như vậy công việc C3 có thể trễ so với kế hoạch tốiđa là 10 ngày. Còn công việc trên đường găng thì phải thực hiện theo đúng kế hoạch. Đồng thời khi có thay đổi gì trong kế hoạch thì người quản lý lại cập nhật được và điều chính cho hợp lý. 32 Để thực hiện được quá trình đưa sơ đồ mạng sang sơ đồ ngang ta triển khai các thuật toán chi tiết như sau: Thuật toán sắp xếp lại các công việc Một dự án lớn bao giờ cũng có nhiều công việc. Rõ ràng là trong dự án có những công việc có thể tiến hành độc lập như công việc làm móng, vận chuyển cần trục về và vận chuyển cấu kiện trong bảng 2.1 bên dưới. Nhưng có những công việc như lắp dựng cần trục thì không thể bắt đầu nếu công việc đưa cần trục về chưa hoàn thành. Như vậy là có một quan hệ “phải hoàn thành trước” giữa công việc đưa cần trục về và công việc lắp dựng cần trục. Quan hệ trong toán học gọi là quan hệ thứ tự bộ phận. Người quản lý dự án, với kinh nghiệm chuyên môn xây dựng, có thể dễ dàng xác định được quan hệ “phải hoàn thành trước” đối với từng công việc. Bảng 2.1. Các công việc của một dự án Số thứ tự của Các công việc phải thực Tên công việc hiện trước công việc 1 Lắp cần trục 5 2 Chuyển cấu kiện 0 3 Làm móng 0 4 Lắp khung 1,2,3,5 5 Chuyển cần trục về 0 ... Vấn dề của chương trình là phải làm sao sắp xếp được các công việc theo một trình tự tuyến tính để khi tiến hành một công việc thì tất cả các công việc phải hoàn thành trước nó đã thực hiện xong rồi. Chẳng hạn với bảng 2.1 thì ta có thể sắp xếp theo trình tự: làm móng, vận chuyển cần trục, vận chuyển cấu kiện, lắp cần trục, lắp khung. Việc này những ngưòi quản lý dự án vẫn thường thực hiện dựa trên cảm tính, và kinh nghiệm, nhưng nếu số lượng công việc lớn thì có thể sẽ bị thiếu chính xác. 33 Áp dụng thuật toán sắp xếp tôpô để thu được trình tự của các công việc. Thuật toán sắp xếp tôpô có ý tưởng như sau: trong đồ thị biểu diễn mối quan hệ giữa các công việc ban đầu, lấy ra một đỉnh không có cung nào đi vào nó (không có đỉnh nào trước nó), còn gọi là đỉnh trọc. Đỉnh này cùng với các cung xuất phát từ đỉnh này được đưa ra khỏi đồ thị. Nếu cùng một lúc có nhiều đỉnh trọc thì ta sẽ thực hiện chọn lần lượt. Tiếp tục cho đến khi lấy được hết các đỉnh. Trong thuật toán sử dụng mảng intOrder[] để lưu thứ tự các công việc sau Order[i] = j, nghĩa là công việc i có thứ tự tôpô bằngj. khi đã sắp xếp tôpô. Mảng T1[] để lưu tạm mảng công việc ban đầu để tạo lại mảng các công việc trước của từng công việc. Mảng intKT[] để cho biết công việc i đã được xét hay chưa. Thuật toán sắp xếp lại các công việc theo thứ tự topo: Input: mảng T với nT công việc, ma trận A biểu diễn quan hệ giữa các công việc ban đầu có cỡ nT x nT. Quan hệ giữa các công việc phải không có chu trình. Output: ma trận A biểu diễn quan hệ giữa các công việc theo trật tự tôpô, mảng Order lưu thứ tự các công việc sau khi đã sắp xếp tôpô. Void Topo; { //tạo mảng Order với thứ tự các công việc theo trật tự topo. k=0; //số đỉnh trọc trong một lần xét. do { d=0; for (i=1;i<=nT; i++) if (cột(A,i)&&(KT[i]==0)) { k=k+1; d=d+1; Order[k]=i; KT[i]=1; 34 } if (d==0) break; //lỗi sắp topo có chu trình for (i=d-k+1; i=k;i++) Xoahang(A,i); //xoá hàng i,cột i trong A. } while (k==nT); if (d==0) cout<<”lỗi sắp topo có chu trình”; //xác định lại bảng công việc T theo thứ tự Order T1=T; //lưu mảng T for (i=1;i<=nT;i++) { T[i]=T1[Order[i]]; for (j=1; j<=T[i].truoc[0];j++) for (k=1;k<=i-1;k++) if(T[i].truoc[j]==Order[k]) T[i].truoc[j]=k; T[i].tt=i; for (j=1; j<=(T[j].truoc[0]-1);j++) for (k=1; k<=T[i].truoc[0];k++) if(T[i].truoc[i]>T[i].truoc[k]) Đổichỗ(T[i].truoc[i],T[i].truoc[k]); } //Tạo lại ma trận A từ bảng công việc T mới } Để sử dụng phương pháp biểu diễn sơđồ mạng dựa trên sự kiện, ta cần xácđịnh các sự kiệnđánh dấu sự bắtđầu hay kết thúc một hay một số công việc. Vì vậy, bài toáncần giải quyết việc chuyển từ ma trận biểu diễn công việc sang ma trận biểu diễn sự kiện, được thực hiện theo thuật toánđược trình bày sau đây : 35 Thuật toán chuyển đồ thị biểu diễn công việc sang đồ thị biểu diễn sự kiện Input : ma trận biểu diễn quan hệ công việc A Output: ma trận biểu diễn sự kiện B của sơ đồ mạng Trong thuật toán có sử dụng các hàm : int ladinhket(i,A):Hàm nhận giá trị 1 nếu đỉnh i không có cung đi ra trong đồ thị công việc biểu diễn bằng ma trận A và nhận giá trị 0 nếu ngược lại. int khongcodinhvao(A,i): Hàm nhận giá trị 1 nếu đỉnh i không có cung đi vào trong đồ thị công việc biểu diễn bằng ma trận A và nhận giá trị 0 nếu ngược lại. void chuyen() { Khởi tạo mang B=0; sMax=1; //số sự kiện for (i=1; I<=nT; I++ ) {if (ladinhket(I,A)==0) tăng thêm 1 đỉnh cho nS; if (ladinhket(I,A)==1)) { tăng_thêm_một_đỉnh_cho_nS; } if (khongcodinhvao(A,i)==0) B[1][nS] = i; co1dinhvao(A,i,&cout1,&thu1); //tính toán số cung đi vào đỉnh i //trả vào cout1, thu1 lưu giá trị của hàng có 1 phần tử đầu tiên. if (cout1==1) //chỉ có một cung vào đỉnh i {for (hang=1; hang<=nS; hang++) for (cot=1;cot<=nS; cot++) {/*Tìm nút sự kiện kết thúc công việc trước. Nối nút sự kiện vừa thêm băng công việc đang xét*/ if(B[hang][cot]==thư1) B[cot][nS] 36 =i; } } else //cout1 >1 có nhiều cung vào { Chọn cung có thứ tự bé nhất; Xác định công việc trước của cung này trong ma trận A; Tìm_sự kiện kết thúc công việc này trong đồ thị biểu diễn bằng ma trận B; Nối nút này với sự kiện mới thêm; Đánh số cung này là sự kiện đang xét; //Các bước trên thực hiện tương tự như trường hợp cout=1 Duyệt tất cả các cung còn lại, tạo một công việc ảo đến sự kiện đã chọn; } } //end of for Nếu có nhiều đỉnh kết, ta chọn một trong các đỉnh đó làm đỉnh kết, nối các đỉnh kia với đỉnh được chọn bằng một công việc ảo. }//end of chuyen Trong sơ đồ mạng, để thể hiện rõ các công việc mà ta phải thực hiện đúng thời gian theo kế hoạch, nếu không sẽ làm thay đổi thời gian hoàn thành cho toàn bộ dự án. Khi lập sơ đồ mạng cho dự án ta cần chỉ ra các công việc găng. Thuật toán tìm đường găng sau đây sẽ giải quyết bài toán này. Thuật toán tìm đường găng Input: Ma trận B[][], mảng sự kiện s[], mảng công việc T[] Output: các công việc găng ghi trong mảng G[][] 37 Void Criticalpath; { // Tính thời gian sớm của mỗi sự kiện s[1].tgs=0; s[1].before[0]=1; s1.before1=0; for (i=2; i<=sMax; i++) { d=0; for (j=1; j<=i-1; j++) Tìm sự kiện có cung tới i với tổng s[i].tgs+T[B[i][j]].tgian lớn nhất; Ghi các sự kiện có tổng s[j].tgs+T[B[i][j]].tgian đạt max vào trường trường before } //end of i //tính thời gian muộn của mỗi sự kiện s[nS].tgm=s[nS].tgs; for (i=nS-1; i>=1; i++) { for(j=nS; j>=i+1;j++ ) Tìm tgmin=min{ s[j].tgm-T[B[i][j].tgian }của sự kiện j có cung đến i; s[i].tgm=tgmin; } //end of i //tính thời gian dự trữ của từng sự kiện for (i=1; i<=nS; i++) D[i]=s[i].tgm-s[i].tgs; //Tìm đường găng Duyệt các sự kiện có dự trữ D[i]=0 theo các chỉ số ghi trong trường before của từng sự kiện; Khi được 1 sự kiện thì tăng i; if ((s[i].before[0]=1) &&(s[i].before[1]=0)) Ghi tất cả các sự kiện đó vào mảng G; } // end of Criticalpath 38 2.2. Bài toán quản lí tài nguyên 2.2.1. Giới thiệu chung Tài nguyên bao gồm những khả năng hiện có về lao động, đối tượng lao động và công cụ lao động (nhân lực, máy móc, thiết bị, vật liêu, …). Trong thực tế thường gặp trường hợp tài nguyên phân bố không đều theo thời gian, có lúc dư thừa có lúc lại vượt quá khả năng cung cấp. Vấn đề đặt ra là phải nghiên cứu cách phân bố tài nguyên như thế nào để có thể điều hoà cân đối giữa khả năng cung cấp và nhu cầu đòi hỏi. Tổng quát, có hai bài toán dưới đây: Bài toán 1: Thời gian hoàn thành dự án đã định trước, cần điều hoà tài nguyên một cách tốt nhất. Bài toán 2: Mức độ cung cấp tài nguyên có một giới hạn nhất định cần sắp xếp các công việc để hoàn thành dự án trong thời hạn ngắn nhất. Cần chú ý rằng, hai bài toán trên được giải quyết với hai giả thiết: 1. Kế hoạch xây dựng được lập trên sơ đồ mạng đã tính các chỉ tiêu thời gian và đã biểu diễn trên trục thời gian hoặc sơ đồ mạng ngang. 2. Mọi công việc đều cần 1 loại tài nguyên. Một dự án có thể cần nhiều loại tài nguyên, cần phải phân biệt và nắm vững những đặc điểm của tài nguyên. * Có những tài nguyên có thể lưu lại một thời điểm khác nếu chưa dùng, nhưng có những loại tài nguyên sẽ mất đi nếu không sử dụng đúng thời điểm của nó. Ví dụ vật liệu, thiết bị, lao động. * Một số tài nguyên khi được giải phóng để dùng sang việc khác nhưng có những tài nguyên đã sử dụng hoặc qua thời gian sử dụng thì coi như mất hẳn. Ví dụ nhân công. Trong phạm vi nội dung luận văn quan tâm đến tài nguyên cụ thể là nhân lực. Đây là một dạng tài nguyên đặc biệt và quan trọng nhất trong dự án. Mục đích của luận văn là đưa ra được phương án phân phối tài nguyên sao cho có được phương án tối ưu nhất. Kết quả phải được minh hoạ bằng biểu đồ tài nguyên. 39 Trong trường hợp kế hoạch xây dựng được lập trên sơ đồ mạng đã tính các chỉ tiêu thời gian và đã biểu diễn trên trục thời gian hoặc sơ đồ mạng ngang, cần tìm mọi cách sắp sếp các công việc (theo một quy tắc nào đó) sao cho vẫnđảm bảo các yêu cầu cần thiết và nhu cầu tài nguyên trong suốt thời gian thực hiện mang tính điều hoà: có nghĩa là việc sử dụng tài nguyên không có những thờiđiểm lên cao hoặc xuống thấp quá bất thường. Điều này đặc biệt có ý nghĩa với tài nguyên là nhân công, rất khó cho người quản lý thi công. Hôm nay thuê rất nhiều nhân công lao động để mai lại sa thải không sử dụng và ngày hôm sau lại tiếp tục thuê tiếp. Các hình vẽ sau đây minh hoạ một số biểu đồ tài nguyên: R Thời gian Nhu cầu tài nguyên T’ T’’ T’’’ Hình 2.1(a). Biểu đồ sử dụng tài nguyên tốt Nhu cầu tài nguyên Thời gian Hình 2.1(b). Biểu đồ sử dụng tài nguyên chấp nhận được 40 Nhu cầu tài nguyên Thời gian Hình 2.1(c). Biểu đồ sử dụng tài nguyên không tốt Bài toán đặt ra cho việc phân phối tài nguyên nhân lực là sắp xếp các công việc theo trình tự và trong giới hạn có thể để đảm bảo quy trình thực hiện và có được biểu đến ứng dụng tài nguyên ở mức tốt hoặc chấp nhận được. Để thực hiện yêu cầu này, dùng bình phương nhu cầu tài nguyên ([5]) trong mỗi khoảng thời gian, làm thước đo sự chênh lệch về nhu cầu tài nguyên. Trên sơ đồ mạng, xuất phát từ giải pháp ban đầu, ta chuyển dịch thời hạn bắt đầu, của các công việc không găng sao cho tổng bình phương của nhu cầu tài nguyên luôn đạt tối thiểu. Kết quả này có được dựa trên bất đẳng thức Cauchy ([5]). Trong thực tế tài nguyên thường bị giới hạn ở một mức nào đó, tức là ở dạng bài toán 2. Trường hợp này ta dùng phương pháp “giới hạn tài nguyên”. Theo phương pháp này mức tài nguyên được xác định trước. Các công việc được sắp xếp sao cho không vượt quá mức giới hạn tài nguyên đó. Trong thực tế, đây là một bài toán rất phức tạp. Giả sử ta có một mạng có rất nhiều các công việc đòi hỏi những tài nguyên khác nhau mà ta chỉ có một số lượng giới hạn các tài nguyên đó. Như vậy việc sắp xếp các công việc không những phụ thuộc vào logic của mạng mà còn tuỳ thuộc vào mức giới hạn tài nguyên sẵn có. Muốn vậy ta phải chọn phương pháp và quyết định một số tài nguyên sắp xếp, trong đó quan trọng nhất là: Quy tắc ưu tiên. 41 Chương trình máy tính sẽ căn cứ vào quyết định đó mà tìm lời giải. Lời giải này có thể không tối ưu, nhưng chắc chắn là rất gần với giải pháp tối ưu. Trong phương pháp phân phối tài nguyên, các vấn đề chính cần nghiên cứu là: * Loại tài nguyên. * Quy tắc ưu tiên. * Phương pháp sắp xếp. * Tài nguyên cố định hay thời gian cố định 2.2.2. Biểu đồ tài nguyên và các quy tắc ưu tiên Biểu đồ tài nguyên Sau khi chuyển sơ đồ mạng lên trục thời gian hoặc sơ đồ mạng ngang ta tiến hành vẽ biểu đồ tài nguyên theo phương pháp mặt cắt. Trục thời gian cắt những mặt cắt vuông góc với trục hoành, mặt cắt này cắt qua các công việc đang tiến hành. Tổng số tài nguyên của các công việc đang tiến hành cho biết lượng tài nguyên đang sử dụng. Như vậy ta vẽ được biểu đồ tài nguyên của dự án ngay phía dưới sơ đồ mạng. Từ biểu đồ tài nguyên ta dễ dàng có được sự phân phối tài nguyên một cách hợp lý trong bài toán phân phối tài nguyên dưới đây. Để đánh giá chất lượng một biểu đồ tài nguyên, ta hãy xét các đặc điểm sau: 1. Diện tích biểu đồ tài nguyên chính là tổng số công lao động cần sử dụng 2. Nếu mức độ dao động về tài nguyên vượt quá mức giới hạn cung cấp thì phải điều chỉnh lại tiến độ bằng cách sử dụng các dự trữ của công việc để thay đổi thời điểm khởi sớm hay kéo dài thời gian (tij) của công việc trên sơ đồ mạng. Đây chính là hình thức tối ưu hoá sơ đồ mạng. 3. Biểu đồ tài nguyên không được có chỗ cao ngắn hạn và những chỗ quá thấp dài hạn. * Nếu quá cao ngắn hạn tức là trong một thời gian ngắn sử dụng một số lượng tài nguyên quá lớn so với số lượng tài nguyên trung bình. Điều này gặp khó khăn cho việc điều động tài nguyên mà nếu làm được thì các phụ phí sẽ tăng lên. 42 * Nếu biểu đồ tài nguyên có những chỗ quá thấp dài hạn thì gây nên dư thừa tài nguyên. Điều này gây bất lợi cho việc sử dụng và điều động tài nguyên hoặc làm tăng các phụ phí. Để đánh giá hoặc so sánh các biểu đồ tài nguyên, ta dùng hai hệ số sau: a) Hệ số sử dụng điều hoà nhân lực ( ): Trong đó: : Số tài nguyên lúc cao nhất : Số tài nguyên trung bình của biểu đồ nhân lực, được tính bằng tổng tài nguyên sử dụng chia cho thời gian tiến độ. : Tổng số tài nguyên sử dụng : Thời gian hoàn thành tiến độ Hệ số 1 thì phương án phân phối nhân lực theo biểu đồ đó là tốt. b) Hệ số không ổn định về sử dụng tài nguyên ( ) Trong đó: : Số tài nguyên không ổn định, xác định bằng diện tích biểu đồ tài nguyên, giới hạn bởi đường bao phía trên và đường tài nguyên trung bình. : Tổng tài nguyên sử dụng, xác định bằng diện tích biểu đồ tài nguyên. Hệ số 0 thì phương án phân phối nhân lực theo biểu đồ tài nguyên đó là tốt. Ví dụ minh hoạ biểu đồ tài nguyên. 2 2
(4) 1
(5) 3
(1) 1 3 43 5
(5) 9
(7) 6
(3) 5 3
(5) 5
(3) 10
5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 T 4 6 Hình 2.2. Biểu đồ tài nguyên Các quy tắc ưu tiên Trong phương pháp phân phối tài nguyên, quy tắc thứ tự ưu tiên đóng một vai trò rất quan trọng. Ta sẽ khảo sát quy tắc này qua ví dụ sau: Ví dụ: Giả sử từ 1 sự kiện i, có 4 công việc: A, B, C, D; mỗi công việc cần một số lượng công nhân là: A 4CN A = 4, B = 2, C = 2, D = 4 B 2CN i C 2CN D 4CN Giả thiết tại thời điểm i bắt đầu các công việc, mức giới hạn tài nguyên là 8 người. Có 3 phương án là: 1. A, D bắt đầu; B, C lùi lại 2. A, B, C bắt đầu; D lùi lại 3. B, C, D bắt đầu; A lùi lại 44 Cả 3 phương án đều thoả mãn mức giới hạn tài nguyên, nhưng phương án nào sẽ được chọn. Để giải quyết vấn đề này cần đề ra một số quy tắc ưu tiên, để theo đó ta có thể biết được công việc nào được làm trước hoặc quyết định phương án nào được chọn. Quy tắc ưu tiên đóng vai trò quan trọng trong bài toán phân phối tài nguyên. Dựa vào các quy tắc này để quyết định những công việc nào được xếp trước. Trước khi quyết định chọn một quy tắc ưu tiên nào đó để sắp xếp các công việc, thì chưa chắc phương án đó đã tối ưu, song vẫn có thể chấp nhận như là kết quả gần tối ưu. Một số quy tắc ưu tiên sau đây thường được áp dụng: - Ưu tiên những công việc găng - Ưu tiên những công việc có dự trữ nhỏ nhất - Ưu tiên những công việc có thời gian thực hiện nhỏ nhất - Ưu tiên những công việc có thời hạn bắt đầu hoặc kết thúc muộn nhất - Ưu tiên những công việc thực tế đòi hỏi phải hoàn thành trước - Ưu tiên những công việc những công việc theo ý muốn chủ quan hoặc ý nghĩa chính trị của con người. 2.2.3. Các phương pháp phân phối tài nguyên Phương pháp 1 (Phương pháp nối tiếp) Giả sử có một dự án nào đó, ta chia dự án thành các thời kỳ, mỗi thời kỳ có lập một bảng kê khai các công việc. Các công việc này được sắp xếp theo một thứ tự ưu tiên nào đó như: ưu tiên những công việc găng, ưu tiên về dự trữ nhỏ nhất, ưu tiên những công việc có thời gian thực hiện nhỏ nhất, ưu tiên các công việc có thời hạn bắt đầu hay kết thúc muộn nhất, các công việc được lấy ra xét từng công việc một, mục đích là xây dựng thời gian sớm nhất để công việc có thể bắt đầu. Thời hạn này không sớm hơn thời hạn khởi sớm đã tính toán khi phân tích sơ đồ mạng theo thời gian và ít nhất phải có đủ tài nguyên cho công việc trong suốt thời gian thực hiện nó. Khi một công việc bị đẩy lùi, thì các thời hạn bắt đầu sớm nhất của các công việc tiếp theo cũng phải lùi lại tương ứng và những công việc sắp xếp rồi phải sắp xếp lại. 45 Những công việc có thể sắp xếp trong thời kỳ này đã đủ thì những công việc không sắp xếp được phải lùi lại thời gian sau và quá trình lựa chọn sắp xếp theo mức giới hạn về tài nguyên cho phép được sắp xếp lại. Trong quá trình tính toán, toàn bộ dự án được coi như một thời kỳ và tất cả các công việc trong dự án đều nằm ở bảng kê khai ban đầu với thứ tự ưu tiên phân phối tài nguyên của nó và thứ tự này sẽ không thay đổi trong suốt toàn bộ dự án. Phương pháp 2 (Phương pháp song song) Về lý thuyết, phương pháp song song được thực hiện từ thời điểm bắt đầu tiến hành dự án đến thời điểm cuối cùng. Lần lượt dừng lại ở thời điểm hoàn thành từng công việc trên sơ đồ mạng. Nếu làm như vậy số lượng tính toán sẽ rất lớn, vì thế ta chỉ chọn một số điểm đặc biệt trên sơ đồ mạng ở thời điểm có một số công việc kết thúc, một số công việc đang tiếp tục và một số công việc sẽ bắt đầu.ở thời điểm ấy ta phải xét hai nhóm công việc: đang tiếp tục, sẽ bắt đầu. Tiến hành lập bảng danh sách tất cả các công việc có thời hạn bắt đầu sớm nhất vào lúc đó hay công việc bị đẩy lùi từ thời điểm trước và xếp thứ tự theo một quy tắc ưu tiên nào đó. Ta lấy ra từng công việc theo một thứ tự và sắp xếp sao cho đảm bảo mức giới hạn tài nguyên. Những công việc còn lại không đủ tài nguyên sẽ bị đẩy lùi và được đưa vào bảng để xếp thứ tự lại. Tại thời điểm tiếp theo, qua trình trên được lập lại cho đến khi kết thúc dự án. Như vậy sự khác nhau cơ bản giữa hai phương pháp trên là: Phương pháp nối tiếp cố gắng phân phối tài nguyên, trong toàn bộ dự án một lần, các công việc được xếp theo thứ tự ưu tiên chỉ làm một lần, được kê trong bảng ban đầu. Trong quá trình sắp xếp, thứ tự ưu tiên không đổi. Phương pháp song song kiên trì nghiên cứu từng thời điểm, tiến hành sắp xếp dần trong suốt thời gian của dự án. Trong quá trình phân phối nó không phải xét lại quyết định đã có trước (tức là công việc bị đẩy lùi phải sắp xếp lại theo quy tắc ưu tiên). 46 Tuy chưa có khẳng định gì, nhưng theo các kết quả đã công bố của nhiều tác giả, phương pháp song song có vẻ tốt hơn. Ví dụ về phân phối tài nguyên. 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 Trong sơ đồ mạng trên, các công việc được bắt đầu ở thời điểm sớm nhất, chữ số ghi trên là thời gian hoàn thành công việc, chữ số ghi ở dưới trong dấu ngoặc là yêu cầu về tài nguyên. Thời gian hoàn thành dự án là T = 22 ngày, mức giới hạn tài nguyên R = 20. Ta sử dụng phương pháp song song để phân phối tài nguyên với quy tắc ưu tiên dự trữ nhỏ nhất. Bắt đầu từ sự kiện 0, có hai công việc (0-1) và (0-2). Công việc (0-1) là găng nên được ưu tiên trước. Đến (0-2) thì không đủ tài nguyên 15+8=23>20 nên bị đẩy lùi đến thời điểm kết thúc (0-1). Tiếp đến sự kiện 1, có 3 công việc (1-2), (1-3) và công việc bị đẩy lùi (0-2). Ta thấy (1-2) là công việc găng nên ưu tiên số 1, (0-2) có dự trữ là 1 nên ưu tiên số 2, (1-3) có dự trữ 3 nên ưu tiên xếp cuối cùng. Ta xếp (1-2) rồi đến (0-2) thì vừa đủ tài nguyên 12+8=20, nên (1-3) bị đẩy lùi đến thời điểm kết thúc (0-2) mới được phép bắt đầu. 47 Đến sự kiện 2, có hai công việc (1-3) đang tiếp tục và công việc găng (2-3). (2-3) được ưu tiên xếp trước rồi đến (1-3). Cứ tiếp tục như vậy cho đến khi kết thúc dự án ta thu được Hình 2.5b với T=22 và R 20. 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. Nếu áp dụng phương pháp nối tiếp và vẫn sử dụng quy tắc ưu tiên dự trữ nhỏ nhất: - Ở thời điểm sự kiện 0, có hai công việc (0-1), (0-2) thì (0-1) là găng nên ưu tiên trước rồi đến (0-2). Vì 15+8 = 23>20 nên (0-2) bị đẩy lùi đến thời điểm sau. - Đến sự kiện 1, (0-2) được xếp trước, xong đến (1-2) thì đủ tài nguyên, (1-3) bị đẩy lùi đến thời điểm (0-2) kết thúc. - Tiếp đến sự kiện2, (1-3) đang tiếp tục xếp trước rồi đến (2-3). - Xét sự kiện3, (3-4) xếp trước, rồi đến (3-5) bắt đầu sau khi (3-4) kết thúc. - Tiếp đến sự kiện 4,(3-5) vẫn đang tiếp tục nên xếp trước rồi đến (4-7) thì đủ tài nguyên. - Đến sự kiện 5, (4-7) đang tiếp tục nên xếp trước, sau đó đến (5-6) thì vừa đủ tài nguyên, (5-9) bị đẩy lùi đến khi (5-6) kết thúc. - Đến sự kiện 6, (5-9) xếp trước rồi đến (6-8) nhưng không đủ tài nguyên nên (6-8) bị đẩy lùi đến khi kết thúc (5-9). 48 - Đến sự kiện 7, ta xếp (7-8) nhưng (7-8) xếp sau (6-8) nên phải kéo dài thêm 1 ngày cho đúng với (6-8) kết thúc. - Cuối cùng còn sự kiện 8, chỉ còn lại (8-9). Như vậy cho đến sự kiện hoàn thành, ta thu được biểu đồ phân phối tài nguyên Hình 2.3c với R 20 và T=23 ngày. 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 2.2.4. Cân đối tài nguyên Tương ứng với biểu đồ công việc, ta dễ dàng tính được số lượng tài nguyên nhân lực trong từng khoảng thời gian, giúp người quản lý theo dõi được tiến độ, đồng thời biết số mức nhân lực yêu cầu. Mục sau đây trình bày thuật toán đưa ra mức tài nguyên ban đầu. Thuật toán đưa ra mức tài nguyên ban đầu Input: Mảng công việc T[], mảng sự kiện s[], ma trận B[][] của đồ thị sự kiện. Output: Mảng Rs[] lưu mức sử dụng tài nguyên trong từng thời điểm và mảng Tg[] lưu thời gian tương ứng với Rs[], mảngc[] lưu mốc thời gian đánh dấu thời điểm có ít nhất một công việc bắt đầu hay kết thúc Trong thuật toán này ta sử dụng mảng T1[]làm trung gian để xét các công việc có cùng thời gian khởi sớm. 49 { int d1=0; //số phần tử của mảng T1[] . int d=1; //số phần tử của mảng Tg[] và Rs[]. int khs[50]; //mảng lưu thời gian khởi sớm của mỗi công việc. Khởi tạo T1[]=0; Tính các giá trị thời gian khởi sớm khs[] cho từng công việc; i=1; T1[1]=T[1]; c[1]=0; xét { Chép từ T[] vào T1[] những côngviệc có cùng thời gian khởi sớm khs[i] và lưu lại chỉ số của công việc lần cuối cùng được chép từ T[] sang T1[] vào biến luu; Đặt một mốc c[j] = khs[i], với mỗi công thời điểm kết thúc một công việc, ta tạo thêm một mốc c[k] = khs[i] + T[k].tgian } d1=1; i=luu+1; T1[1]=T[i]; i++; //Sang công việc tiếp theo } Sắp xếp các mốc c[] theo chiều tăng dần. Giữ lại các mốc khác nhau trong mảng c[], ta được m mốc Tổng thời gian thực hiện là Tgd = c[m], số khoảng phân biệt là m- 1. J=1 While (j { Tg[j]= c[j+1] - c[j] Tính tổng tài nguyên các công việc đang được thực hiện trong đoạn (c[j], c[j+1]), đưa vào Rs[j] } } 50 Thuật toán cân đối tài nguyên Ta dùng phương pháp song song để cân đối tài nguyên. Giả thiết: mỗi công việc được tiến hành liên tục, tức là một công việc khi đã bắt đầu sẽ được làm cho tới khi hoàn thành, không bị dừng lại nửa chừng. Để cân đối tài nguyên, ta chia thành hai giai đoạn: Giai đoạn 1: Đưa mức yêu cầu tài nguyên xuống dưới mức cung cấp, tiến hành từ trái sang phải bằng cách làm chậm một số công việc và theo quy tắc sau đây: 1.Các công việc đã được tiến hành trong khoảng thời gian trước vẫn được tiến hành trong khoảng thời gian đang xét. 2. Đẩy lùi thời điểm bắt đầu sang khoảng thời gian sau của công việc có dư trữ lớn nhất, tức là ưu tiên các công việc có dự trữ nhỏ nhất được tiến hành trước. 3. Nếu nhiếu công việc có cùng dự trữ thời gian thì đẩy lùi công việc không găng độc lập trước và lựa chọn đẩy lùi số công việc là ít nhất mà giảm mức tài nguyên là lớn nhất. Giai đoạn 2 : Nâng mức yêu cầu tài nguyên gần mức cung cấp nhằm thu ngắn nhất thời gian thực hiện dự án. Sau giai đoạn 1, nếu thời gian xây dựng dự án không bị kéo dài hơn so với trước thì phương án sau giai đoạn 1 là tốt nhất. Nhưng thường thì thời gian thực hiện dự án sẽ bị kéo dài thêm. Vì vậy phải cố gắng thu ngắn thời gian trở lại dự án ban đầu theo hai lần: Lần thứ nhất : Xét các khoản thời gian từ phải sang trái, khoảng nào có thể tăng mức yêu cầu tài nguyên trong phạm vi mức cung cấp thì dịch chuyển các công việc kế cận gần nhất. Sau lần 1, nếu thời gian toàn bộ không rút ngắn được, ta kết luận không thể rút ngắn được nữa. trái lại thì ta phải tiến hành lần thứ 2. 51 Lần thứ 2: Xét các khoảng thời gian từ phải sang trái, tăng mức yêu cầu tài nguyên trong phạm vi mức cung cấp. Tiếp tục làm như lần thứ nhất cho đến khi xuất hiện hai tình huống: 1. Không rút ngắn được thời gian hoàn thành dự án. 2. Thời gian hoàn thành dự án bằng hoặc nhỏ hơn thời gian hoàn thành phương án đầu. Ta dừng lại, đó chính là phương án tối ưu. Sau khi đưa ra mức tài nguyên ban đầu nếu mức yêu cầu của dự án vượt quá mức cung cấp thì ta tiến hành cân đối tài nguyên sao cho mảng Rs[] không có giá trị nào lớn hơn mức giới hạn tài nguyên Rmax. Xét trường hợp tổng quát, người quản lý có thể cân đối tài nguyên bắtđầu từ một thờiđiểm nàođó trong quá trình dữánđang diễn ra. Nếu cần cân đối tài nguyên cho toàn bộ dựa án thì mốc cân đối là thờiđiểm dựán bắtđầu: mốc = 0. Thuật toán: Cân đối tài nguyên In put: Mảng công việc T[], mức tài nguyên cung cấpRmax, mảng lưu thờiđiểm khởi sớm của các công việcKhs[], mốc thời gian cần cân đối Moccd, hai mảng lưu khoảng thời gian và tài nguyên tương ứng trước khi thực hiện cân đối làTg[] vàRs[] Output: Hai mảng lưu khoảng thời gian và tài nguyên tương ứngTg[] vàRs[], thời gian hoàn thành dự ánTgd. Trong thuật toán này sử dụng: mảngSt[] lưu trạng thái mỗi công việc. 1 nếu công việc i chưa được thực hiện. St[i] = 0 nếu công việc i đang tiến hành. -1 nếu công việc i đã kết thúc. Mảng DT[] lưu thời gian dự trữ của mỗi công việc, mảng Tgcon[] lưu khoảng thời gian chưa được xét của mỗi công việc. 52 {Lưu giữ lại các đoạn Tg[i], Rs[i] không thực hiện cân đối tài nguyên. Khi đó: Nếu công việc k có Kh[k]+T[k].Tgian < Moccd thì Tgcon[k]=0 Ngược lại: Tgcon[i]=Khs[i]+T[i].tgian - Moccd Moc1=Mocd /*T1: Lưu các công việc đang thực được làm tại bước đó T2: Lưu các công việc có cùng khởi sớm tại bước đang xét. T3: Lưu các công việc bắt đầu sau mốc đang xét nhưng cùng đang diễn ra với các công việc đang được xét*/ Lặp đến khi hoàn thành dự án { danglam=0, d1=0, d2=0, d3=0 ,R1=0:số lượng phần tử của T1, T2, T3 - Đưa công việc đang làm vào T1[], tính tổng tài nguyên của các công việc đang làm R1 - Đưa các công việc có khởi sớm = Moccd vào T2[], - Sắp xếp trong T2[] theo thời gian dự trữ tăng dần - Với mỗi công việc k trong T2: nếu R1+ T[T2[k].tt].tn<=Rmax thì R1=R1+T[T2[k].tt]tn St[T2[k].tt]=0 Đưa công việc k này vào T1 - Tìm khoảng thời gian Tgcon[k] nhỏ nhất trong T1[]: Tgmin - Đưa các công việc bắtđầu sau Moccd nhưng trước Moccd +Tgmin vào T3, và tính tổng tài nguyên của chúng R2. - Sắp xếp các công việc trong T3 theo khởi sớm tăng dần - Nếu T[T[3k].tt].Tgian + R1 <=Rmax thì Bổ sung công việc này vàođoạnđang xét, Ngược lại, đẩy lùi công việc này *) Xét xem công việc nào đã làm xong trong đoạn này. - Trong T1[]: Nếu Tgcon(T1[k].tt) = Tgmin thì công việc nàyđã kết thúc nễu Tgcon[T1[k].tt]>Tgmin thì Tgcon[T1[k].tt]=Tgcon[T1[k].tt]- Tgmin - Xét xem trong T2[], nếu công việc chưa làm [St[T2[k].tt]=1 ] trong đoạn này thì đẩy lùi chúng một khoảng Tgmin: } }//Can_coi_tai_nguyen 53 2.3. Bài toán tối ưu chi phí và giá thành 2.3.1. Giới thiệu chung Đối với người tổ chức, quản lý xây dựng, muốn rút ngắn thời gian xây dựng cần phải quan tâm tới toàn bộ các vấn đề về kinh tế - kỹ thuật của công trình, trong đó hai yếu tố quan trọng và gắn bó với nhau là thời gian và giá thành. Mối quan hệ gắn bó này cần được chú ý đặc biệt trong quá trình lập kế hoạch và chỉ đạo xây dựng. Vấn đề thường được quan tâm là rút ngắn thời gian xây dựng công trình, song nó chỉ có ý nghĩ khi gắn liền với yêu cầu: Làm thế nào để sự tăng chi phí do rút ngắn thời gian là nhỏ nhất. Để rút ngắn thời gian của một công việc chúng ta có thể thực hiện bằng cách: - Tăng thêm công nhân - Tăng thêm thiết bị - Tăng thêm giờ, thêm ca. Tất nhiên, các biện pháp trên sẽ kéo theo sự tăng thêm chi phí. Mỗi công việc có tầm quan trọng khác nhau trong dự án, vậy chúng ta phải trả lời câu hỏi: Rút ngắn bao nhiêu, rút ngắn công việc nào, để đạt được thời hạn quy định mà chi phí tăng thêm là ít nhất? Chúng ta sẽ nghiên cứu mối quan hệ giữa thời gian và giá thành và lần lượt tìm hiểu một số phương pháp giải bài toán này. 2.3.2. Thời gian và giá thành Mối quan hệ giữa thời gian và giá thành của một công việc (i-j) có thể biểu diễn theo đồ thị sau: 54 Hình 2.4. Đồ thị biểu diễn mối quan hệ giữa chi phí thời gian và giá thành Từ đồ thị trên ta nhận xét thấy: Nếu công việc thực hiện trong điều kiện bình thường (điểm B) thì giá thành là nhỏ nhất. Nếu rút ngắn thời gian sẽ phải tăng thêm chi phí nhưng đến một mức độ giới hạn (điểm A) thì dù có tăng thêm chi phí vẫn không rút ngắn thêm được thời gian nữa vì điều kiện kỹ thuật. Nếu quá điểm bình thường B thì sự kéo dài thời gian cũng làm tăng thêm chi phí. Trong phương pháp sơ đồ mạng, chúng ta đã giả thiết thời gian thực hiện mỗi công việc (i-j) là một số xác định ( ). Thời gian này sẽ thay đổi khi thực hiện rút ngắn công việc (i-j) nhưng luôn nằm trong giới hạn cho phép: Trong đó: : thời gian tối thiểu thực hiện công việc (i-j) : thời gian tối đa thực hiện công việc (i-j), còn gọi là thời gian bình thường thực hiện công việc (i-j). Với thời gian này, công việc được tiến hành trong những điều kiện bình thường và chi phí nhỏ nhất. Hệ số giá thành Khi giảm thời gian thì chi phí và giá thành sẽ tăng thêm “sự tăng giá thành khi giảm một đơn vị thời gian của công việc được gọi là hệ số giá thành” Từ hình 2.4 ta có thể xác định được Rij 55 (đồng/thời gian) Rij= Trong đó: Rij: Hệ số giá thành của công việc i-j : Chi phí giới hạn : Chi phí bình thường : Thời gian giới hạn : Thời gian bình thường Hệ số giá thành biểu thị cái “giá” mà ta phải trả khi rút ngắn thời gian thực hiện công việc. Giá trị của hệ số này có tầm quan trọng đặc biệt trong việc lựa chọn công việc nào được rút ngắn thời gian mà chi phí giá thành “rẻ nhất”. 2.3.3. Chi phí trực tiếp, chi phí gián tiếp Bất kỳ một công trình dân dụng hay công nghiệp nào, giá thành tổng cộng của công trình cũng bao gồm hai phần: 1. Chi phí trực tiếp 2. Chi phí gián tiếp Xác định giá thành dự án xây dựng công trình là xác định hai loại chi phí trên mà đặc điểm của từng loại có ảnh hưởng riêng biệt tới bài toán của chúng ta. 2.3.3.1. Chi phí gián tiếp Theo quy hoạch của hạch toán kinh tế, chi phí gián tiếp của một công trình bao gồm: - Chi phí lãnh đạo, quản lý hành chính - Chi phí sửa chữa nhà cửa, hư hỏng tài nguyên - Chi phí gián tiếp tăng theo thời gian xây dựng. Nếu chi phí gián tiếp chỉ dùng cho công việc hành chính như lãnh đạo, quản lý, kiểm tra … thì nó được biểu diễn bằng một đường thẳng. Nếu cộng thêm chi phí mất mát, hư hỏng tài nguyên, sửa chữa nhà cửa thì nó là một đường cong. 56 Hình 2.5. Đồ thị chi phí gián tiếp 2.3.3.2. Chi phí trực tiếp Theo quy định về hạch toán kinh tế, chi phí trực tiếp của một công trình bao gồm: - Mua sắm nguyên vật liệu, thiết bị xây lắp công trình - Chi phí cho thuê máy móc thi công - Chi phí tiền lương cho công nhân Khác với chi phí gián tiếp, chi phí trực tiếp tăng khi thời gian giảm và khi thời gian vượt quá giới hạn của thời gian bình thường thì chi phí trực tiếp cũng tăng khi thời gian tăng. Đồ thị chi phí trực tiếp là một đường cong bậc hai có cực tiểu taị điểm bình thường. Trong thực tế thường không có đủ số liệu, nên đường cong biểu diễn mối Chi phí quan hệ thời gian và giá thành thường lấy gần đúng là một đường thẳng. C c Thời gian C D d D Hình 2.6. Đồ thị chi phí trực tiếp Cách thể hiện đơn giản của mối quan hệ giữa thời gian thực hiện công việc và chi phí trực tiếp có thể thấy ở đồ thị Hình 2.6. Nếu chỉ xét công việc một cách 57 độc lập không nói đến ngày hoàn thành dự án với người quản lý chắc chắn lựa chọn thời gian sao cho chi phí trực tiếp là nhỏ nhất, chúng được thể hiện và (như hình vẽ). Nếu mỗi công việc được lên kế hoạch cho thời gian hoàn thành thì sẽ đạt được chi phí nhỏ nhất theo cách đó, thời gian để hoàn thành toàn bộ dự án có thể sẽ kéo dài và các mốc thời gian quan trọng có thể bị ảnh hưởng do khởi công muộn của dự án bị mắc phải. Ở mức độ cao nhất, người quản lý có thể chọn lựa cách hoàn thành công việc với thời hạn nhỏ nhất có thể, , nhưng đồng thời với chi phí cao nhất . Đây chính là thời gian hoàn thành nhỏ nhất thông thường người ta gọi là “công việc bị dồn thời gian” hay “công việc nước rút”. Mỗi quan hệ tuyến tính của chúng được thể hiện trên đồ thị giữa các điểm này có ý nghĩa là bất kỳ khoảng thời gian hoàn thành công việc cũng có thể được lựa chọn. Và cũng có thể những điểm đó lại là tối ưu giữa thời gian và chi phí cho các công việc. Khi đó chi phí trực tiếp cho công việc i-j được tính bằng công thức: Trong đó, và thể hiện khoảng thời gian và chi phí cuối cùng được lập ra cho mỗi công việc i-j. Khoảng thời gian thực tế cho mỗi công việc cần nằm trong khoảng giữa thời gian với chi phí nhỏ nhất ( ) và thời gian tối thiểu để hoàn thành công việc i-j ( ). Khi đó chi phí trực tiếp tổng cộng được tính như sau: 2.3.3.3. Giá thành toàn bộ dự án Sau khi xác định được chi phí trực tiếp tổng cộng ( ) và chi phí gián tiếp ( ), chúng ta có thể xác định được giá thành toàn bộ dự án (C). C = 58 Mục đích của việc phân tích giá thành và thời gian là đi tìm một giá thành nhỏ nhất ( ) của dự án tương ứng với thời gian tối ưu ( ). Khi đã xác định được đồ thị giá thành tổng cộng của dự án, thì vấn đề tìm thời gian tối ưu không khó khăn nữa. Việc xác định giá thành tổng cộng bây giờ chuyển thành bài toán xác định chi phí trực tiếp. Như vậy không có nghĩa là chi phí gián tiếp không quan trọng hay dễ dàng xác định, nhưng nó ít ảnh hưởng tới bài toán chúng ta đang xét. 2.3.4. Cân đối giá thành Một trong những thông số quan trọng trong quản lý dựán là giá thành của dựán. Người quản lý mong muốn dựán hoàn thành sớm nhất ví chi phí nhỏ nhất. Bài toánđặt ra là khi muốn rút ngắn thời gian hoàn thành dựán thì chi phí tăng lên là nhỏ nhất. Đây là một bài toán lớn và có nhiều hướng giải quyết khác nhau: Phương pháp 1: Sử dụng sơđồ mạng, phương pháp này thực hiện theo 4 bước sau: Bước 1: Lập sơđồ PERT tìmđường găng và các công việc trên đường găng. Bước 2: Tính chi phí cho việc rút ngắn từng công việc theo từngđơn vị thời gian (hệ số giá thành ). Bước 3: Chọn công việc trên đường găng có hệ số giá thành nhỏ nhất và rút ngắn tốiđa công việc này nếu có thể hoặc rút ngắn thời gian hoàn thành công việc đến mục tiêu đãđịnh. Bước 4: Kiểm tra lạiđường găng mà ta đã rút ngắn có còn làđường găng không. Nếu nó vẫn làđường găng thì quay về bước 3, ngược lại, tìmđường găng khác rồi quay lại bước 3. Lặp lại bước 3 - 4 đến khi đạt mục tiêu rút ngắn cho trước. Ví dụ. Cho một sơ đồ mạng sự kiện hình 2.7 và các chỉ tiêu được liệt kê ở bảng 2.2 dưới đây. Bảng 2.2. Bảng các công việc và thông số về thời gian và chi phí Công việc 8
4
8
10
10
20
10 6
1
8
5
9
12
3 14
4
24
24
18
36
18 4
1
4
3
5
6
2 3
---
4
7
2
2.7
8 A
B
C
D
E
F
G 2 B 6 7 A 59 E X C 7 32 32 D G F Hình 2.7. Rút ngắn thời gian bằng phương pháp sơ đồ mạng Đơn vị tính: 1000$ Trong sơđồ mạng, theo các các thông số tínhđược thì thời gian hoàn thành dựán là 32 ngày, tổng chi phí bình thường là 70. Sơđồ có mộtđường găng: C, X, E, F, G. Tiến hành rút ngắn thời gian hoàn thành dựán: trên đường găng C, X, E, F, G, công việc E có hệ số giá thành nhỏ nhất là 2, chúng ta thực hiện rút ngắn công việc này từ 9 ngày, xuống còn 5 ngày (thời gian giới hạn). Khi đó chi phí tăng lên: (9 – 5) * 2 = 8. Do đó chi phí toàn phần là 78 và thời gian hoàn thành dựán là 28. Kết quảđược thể hiện trên hình 2.8 sau: B A E X C G D F Hình 2.8. Sơ đồ mạng sau khi rút ngắn công việc E. Sau khi rút ngắn công việc E, có hai đường găng: C, X, E, F, G và C, D, F, G. Tiếp tục rút ngắn thời gian của dự án, ta thấy công việc E tuy có hệ số giá thành nhỏ nhất nhưng sẽ không thể giảm thời gian thực hiện được nữa, đồng thời ta 60 thấy công việc F nằm trên cả 2 đường găng, và cũng có hệ số giá thành nhỏ nhất. Khi giảm thời gian thực hiện công việc F này từ 12 ngày xuống 6 ngày, sẽ làm cho chi phí tăng 16, nhưng vẫn không làm thay đổi đường găng, đồng thời thời gian thực hiện dự án lại rút ngắn thêm được 6 ngày nữa còn 22 ngày. Công việc tiếp theo có thể thay đổi là công việc C, nếu ta tiến hành giảm thời gian thực hiện công việc C xuống 1 ngày, sẽ làm tăng chi phí thêm 4, nhưng đồng thời cũng làm cho công việc A và B trở thành công việc găng. Và thời gian của dự án lúc này là 21 ngày. Bây giờ nếu tiếp tục muốn rút ngắn thời gian xuống còn 20 ngày, ta sẽ phải lựa chọn xem nên rút ngắn công việc nào là thích hợp. Nếu ta chọn công việc G để rút ngắn thì chi phí tăng lên là 8. Mặt khác ta thấy nếu công việc A đi thì chi phí sẽ tăng lên là 3, đồng thời C là việc găng có cùng sự kiện đầu với A nên cũng phải giảm công việc C. Chính vì thế chi phí thực sự sẽ tăng nếu giảm A và C là 3+4 =7<8. Nên trong trường hợp này, phương án được chọn là giảm công việc A và C, thay vì giảm công việc G. Tiếp tục làm như vậy, chú ý tới thời gian giới hạn của các công việc chúng ta sẽ thu được chi phí của dự án tương ứng với sự giảm thời gian của dự án. Phương pháp 2:Sử dụng quy hoạch tuyến tính (Project Crashing with Linear Programing). Chúng ta cần tính thời gian rút ngắn của từng công việc sao cho tổng chi phí của dựán là nhỏ nhất, tức là ta phải tìm giá trị nhỏ nhất của z, với: Với các ràng buộc sau: , với mọi công việc (i-j), điều kiệnđểđảm bảo thời gian thực 1) hiện không vượt quá cho phép. , với x(i) là thời gian sớm nhấtđể hoàn 2) thành sự kiện i, điều kiện nàyđểđảm bảo cấu trúc trước sau của các sự kiện và các công việc trong sơđồ mạng. 61 Bằng máy vi tính và các phần mềm giải các bài toán quy hoạch tuyến tính chúng ta dễ dàng tìm ra phương án tốiưu của bài toán. Sau đây, chúng tôi triển khai thuật toánđể giải bài toán bằng phương pháp sơđồ mạng trong mục 2.3.6. 2.3.5. Thuật toán tối ưu chi phí và giá thành Thời gian và chi phí có mối quan hệ mật thiết với nhau, đôi khi ta muốn rút ngắn 1 ngày thì chi phí có thể tăng thêm một chút, nhưng có thể rút ngắn 2 ngày thi chi phí lại tăng lên rất nhiều. Như vậy việc quyếtđịnh rút ngắn hay không và rút ngắn bao nhiêu ngày cho phù hợp còn phụ thuộc vàođiều kiện thực tế khi dựán diễn ra. Nếu thời gian hoàn thành dựán rút ngắn so với kế hoạch thì ta phải chịu chi phí vượt trội. Thuật toán dựa vào thông số hệ số giá thành của các công việc sao cho khi rút ngắn thời gian hoàn thành dựán thì chi phí vượt trộiở mức thấp nhất có thể. Nhưđã nêu phương pháp rút ngắn thời gian sử dụng sơđồ mạng trong mục 2.3.5, dướiđây là thuật toán cho bài toán tốiưu chi phí và giá thành: Thuật toán tối ưu chí phí và giá thành: Input: mảng công việc T[], ma trận của đồ thị sự kiện B[][], mảng thời gian dự trữ của công việc Dt[];thời gian rút gọn của dự án tg3; chi phí ban đầu của dự án cp1. Output: mảng công việc T[] chứa các công việc sau khi đã rút gọn, chi phí sau khi rút gọn dự án cp3. Trong thuật toán này sử dụng 1 mảng cv[] mà mỗi phần tử có cấu trúc như sau: { int tt; //số thứ tự của công việc sẽ giảm thời gian float hs; //Tổng chi phi sẽ tăng thêm nếu giảm thời gian công việc này int ds[30]; //Danh sách các công việc sẽ bị thay đổi theo } ; {int n, i, i0, k, h, c, dc, dh; myCost cv[100]; Tính hệ số giá thành Nhập khoảng thời gian muốn rút ngắn i0 do { n=0; 62 {//Nếu là việc găng và vẫn có khả năng rút ngắn được n++; cv[n].tt =k; cv[n].hs=hs[k]; cv[n].ds[0]=0; {Lấy sự kiện đầu của công việc k đưa vào biến h Lấy sự kiện cuối của công việc k đưa vào biến c Tính số công việc có cùng sự kiện đầu với k đưa vào biến dh Tính số công việc có cùng sự kiện cuối với k đưa vào biên dc d=0; {for(j=1;j<=sMax;j++) {if((B[h][j]!=k)&&(B[h][j]>0)&&(Dt(B[h][i]]==0)) //Công việc thật cùng sự kiện đầu, và là công việc găng {cv[n].hs=cv[n].hs+hs[B[h][j]]; cv[n].ds[++d]=B[h][j]; } if[[B[h][j]!=k)&&[B[h][j]==-1)) {//Công việc ảo có cùng sự kiện đầu //Tiến lên trước sự kiện đó,rồi lại tính tương tự {cv[n].hs=cv[n].hs+hs[B[j][l]]; cv[n].ds[++d]=B[j][l]; } //for j }//if dh>1 63 {Voi cac cong viec co cung su kien cuoi voi cong viec k làm tương tự như đối với các công việc có cùng sự kiện đầu với k Đối với công việc ảo có cùng sự kiện cuối thì ta lùi lại một sự kiện } cv.ds[0]=d; } k=tim_min(cv,n);//trả về chỉ số công việc găng cần giảm trong matran cv cp3=cp3+cv[k].hs; //tính chi phí tăng thêm //Giảm thời gian của các công việc liên T1[cv[k].tt].tgianth--; quan T1[cv[k].ds[i]].tgiangh--; TinhthongsoT(T,s,sMax); //Tính lại các thông số sau khi rút ngắn 1 đơn vị //Tim duong gang moi strPath.count = 1; strPath.item[1]=s[sMax].tt; GetPath(strPath,s,sMax); i0--; }//Rut_ngan_thoi_gian 64 3.1. Phân tích cấu trúc, thuật toán của chương trình Thuật toán cho bài toán lập và điều khiển tiến độ Thuật toán lập và điều khiển tiến độ: Biểu diễn sơ đồ mạng sang sơ đồ ngang. Để thực hiện được quá trình đưa sơ đồ mạng sang sơ đồ ngang ta triển khai các thuật toán chi tiết như sau: Thuật toán sắp xếp lại các công việc theo thứ tự topo: Input: mảng T với nT công việc, ma trận A biểu diễn quan hệ giữa các công việc ban đầu có cỡ nT x nT. Quan hệ giữa các công việc phải không có chu trình. Output: ma trận A biểu diễn quan hệ giữa các công việc theo trật tự tôpô, if (cột(A,i)&&(KT[i]==0)){ k=k+1; } d=d+1;
Order[k]=i;
KT[i]=1; if (d==0) break; //lỗi sắp topo có chu trình
for (i=d-k+1; i=k;i++) Xoahang(A,i); //xoá hàng i,cột i trong A. //lưu mảng T } mảng Order lưu thứ tự các công việc sau khi đã sắp xếp tôpô.
Void Topo;
{ //tạo mảng Order với thứ tự các công việc theo trật tự topo.
k=0; //số đỉnh trọc trong một lần xét.
do{
d=0;
for (i=1;i<=nT; i++) 65 Đổichỗ(T[i].truoc[i],T[i].truoc[k]); }
//Tạo lại ma trận A từ bảng công việc T mới { tăng_thêm_một_đỉnh_cho_nS;
} Input : ma trận biểu diễn quan hệ công việc A
Output: ma trận biểu diễn sự kiện B của sơ đồ mạng
Trong thuật toán có sử dụng các hàm :
int ladinhket(i,A):Hàm nhận giá trị 1 nếu đỉnh i không có cung đi ra trong đồ thị công việc biểu diễn bằng ma trận A và nhận giá trị 0 nếu ngược lại. if (cout1==1) //chỉ có một cung vào đỉnh i {for (hang=1; hang<=nS; hang++) Nối nút sự kiện vừa thêm băng công việc đang
xét*/ } //Các bước trên thực hiện tương tự như trường hợp cout=1 Duyệt tất cả các cung còn lại, tạo một công việc ảo đến
sự kiện đã chọn;
} 66 Input: Ma trận B[][], mảng sự kiện s[], mảng công việc T[]
Output: các công việc găng ghi trong mảng G[][] { cung sự có tới i với tổng Tìm
s[i].tgs+T[B[i][j]].tgian lớn nhất; Ghi các sự kiện có tổng s[j].tgs+T[B[i][j]].tgian đạt max vào
trường trường before } //end of i //tính thời gian muộn của mỗi sự kiện Tìm tgmin=min{ s[j].tgm-T[B[i][j].tgian }của sự kiện j có
cung đến i;
s[i].tgm=tgmin; D[i]=s[i].tgm-s[i].tgs; Ghi tất cả các sự kiện đó vào mảng G; 67 Thuật toán đưa ra mức tài nguyên ban đầu Input: Mảng công việc T[], mảng sự kiện s[], ma trận B[][] của đồ thị sự kiện. Output: Mảng Rs[] lưu mức sử dụng tài nguyên trong từng thời điểm và mảng Tg[] lưu thời gian tương ứng với Rs[], mảng c[] lưu mốc thời gian đánh dấu thời điểm có ít nhất một công việc bắt đầu hay kết thúc Trong thuật toán này ta sử dụng mảng T1[] làm trung gian để xét các công việc có cùng thời gian khởi sớm. { int d1=0; //số phần tử của mảng T1[] . int d=1; //số phần tử của mảng Tg[] và Rs[]. int khs[50]; //mảng lưu thời gian khởi sớm của mỗi công việc. Khởi tạo T1[]=0; Tính các giá trị thời gian khởi sớm khs[] cho từng công việc; i=1; T1[1]=T[1]; c[1]=0; Chép từ T[] vào T1[] những côngviệc có cùng thời gian khởi sớm
khs[i] và lưu lại chỉ số của công việc lần cuối cùng được chép từ
T[] sang T1[] vào biến luu; Đặt một mốc c[j] = khs[i], với mỗi công thời điểm kết thúc một
công việc, ta tạo thêm một mốc c[k] = khs[i] + T[k].tgian } d1=1; i=luu+1; T1[1]=T[i]; i++; //Sang công việc tiếp theo } Sắp xếp các mốc c[] theo chiều tăng dần. Giữ lại các mốc khác nhau
trong mảng c[], ta được m mốc Tổng thời gian thực hiện là Tgd = c[m], số khoảng phân biệt là m-
1. J=1 While (j { Tg[j]= c[j+1] - c[j] Tính tổng tài nguyên các công việc đang được thực hiện trong đoạn (c[j], c[j+1]), đưa vào Rs[j] 68 3.2. Xây dựng phần mềm 3.2.1. Lưu đồ thuật toán phần mềm Begin Đọc số liệu đầu vào Xử lý số liệu Sắp xếp Topo Vẽ biểu đồ Kết thúc Hình 3.1. Lưu đồ thuật toán phần mềm 69 3.2.2. Xây dựng thư viện kết nối từ phần mềm tới CSDL Bảng 3.1. Danh mục công việc Bảng 3.2. Thứ tự thực hiện các công việc 70 Bảng 3.3. Các công việc cần thực hiện 3.3. Các form giao diện Hình 3.2. form nhập số liệu 71 Hình 3.3. form xử lý số liệu Hình 3.4. form biểu đồ kết quả 72 Hình 3.5. form giới thiệu chương trình ứng dụng Hình 3.6. In biểu đồ công việc 73 Nghiên cứu phân tích ba bài toán cơ bản trong quản lí dự án, đó là: 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. Các vấn đề liên quan tới từng bài toán như đặt bài toán, ý tưởng, công cụ giải quyết và cuối cùng là thuật toán đã được chúng tôi trình bày một cách thống nhất trong chương 2 giúp cho việc triển khai chương trình được thuận lợi. Về ứng dụng: Chương 3 trình bày chương trình demo của bài toán quản lí mà chúng tôi triển khai cho một trong ba bài toán đã phân tích là Bài toán lập và điều khiển tiến độ. Chương trình viết bằng ngôn ngữ Visual Basic với giao diện chính cung cấp mốt số chọn lựa để thực hiện các chức năng của bài toán. Tuy nhiên, với thời gian và khuôn khổ có hạn của một luận văn thạc sĩ nên chúng tôi mới xây dựng chương trình ở mức độ triển khai được các thuật toán chứ chưa thành một phần mềm ứng dụng hoàn chỉnh. Hướng nghiên cứu tiếp theo: Chúng tôi mong muốn sẽ tiếp tục xây dựng chương trình giải quyết toàn bộ 3 bài toán mà chúng tôi đã phân tích và phát triển chương trình thành một phần mềm thương mại hỗ trợ cho người quản lý dự án được linh động, hiệu quả hơn nữa. Ngoài ra, hướng phát triển khác là hướng bài toán lập và điều khiển tiến độ vào việc hỗ trợ quản lý đào tạo tín chỉ, đây là vấn đề hay và đang được quan tâm. Được sự hướng dẫn tận tình của giảng viên hướng dẫn trong quá trình làm luận văn, sự giúp đỡ của các thầy cô giáo đã giảng dạy chúng tôi trong chương trình đạo tạo thạc sĩ và các bạn đồng nghiệp trong suốt thời kì học tập, tôi đã hoàn thành chương trình đào tạo của mình và bản luận văn này. Tôi rất mong nhận được sự góp ý của các thầy cô giáo trong hội đồng bảo vệ luận văn và những người quan tâm đến vấn đề này để có thể hoàn thiện hơn vốn kiến thức, trình độ của mình cũng như tiếp tục phát triển luận văn ở mức cao hơn. Tôi xin chân thành cảm ơn. 74 * Tiếng Việt: [1] Đỗ Xuân Lôi [1997), “Cấu trúc dữ liệu và giải thuật”, NXB Khoa học Kỹ Thuật, Hà Nội. [2] Nguyễn Thị Ngọc Mai [2004), “Microsoft Visual Basic và lập trình cơ sở dữ liệu” NXB Lao động xã hội,TP HCM. [3] Nguyễn Đức Nghĩa, Nguyễn Tô Thành [1999), “Toán rời rạc”, NXB Giáo dục Hà Nội. [4] Đặng Huy Ruận [2000), “Lý thuyết đồ thị và ứng dụng”, NXB Khoa học Kỹ Thuật, Hà Nội. [5] Trịnh Quốc Thắng [1998), “Các phương pháp sơ đồ mạng trong xây dựng”, NXB xây dựng, Hà Nội. [6] Th.s Nguyễn Hữu Quốc [2007), “Quản lý dự án”, Học viện CN BCVT.
[7] Viện CNTT-ĐHQG Hà Nội, “Giáo trình quản lý dự án”, NXB Viện CNTT- ĐHQG Hà Nội. * Tiếng Anh:
[8] Ian Sommerville [2001), Software Engineering. 6th Edition, Addison-Wasley.
[9] Ian Sommerville [2004), Software Engineering. 7th Edition, Addison-Wasley, chapter 5, chapter 14, chapter 24. [10] Walker Royce [1998), Software Project Management – A Unified Framework, Addison-Wesley.
* Các trang Website:
www.irnop.org, The International Research Network on Organizing by Project www.allpm.com, Te Project Manage’s Resource Center.
www.4pm.com, Project Management Control Center.
www.pmblv.com, Project Management Boulvard.
www.tenstep.com, The tenstep Project Management Process Methodology.
www.projectnet.co.uk, PeojectNet, the World of Project Management from the UK.
www.maxwideman.com, Max’s project Management Wisdom, provides studying project management. tips, tools,papers, and books. ===========ij ):
9
1
6
3
3
5
5
, suy ra dt = ndz
2
4
2
1
2
14
14
1
3
6
1
1
6
0
0
20
20
9
3
0
4
5
3
2
5
5
5
5
14
17
1
4
1
2
2
3
5
9
6
1
6
3
4
3
5
5
2
1
2
3
5
9
6
1
6
3
4
5
3
5
2
4
1
2
1414
1
6
0 0
20 20
3
5 5
5
1 2
14 17
C9
Công việc
Thời gian
CHƯƠNG 2: ỨNG DỤNG SƠ ĐỒ MẠNG VÀO LẬP VÀ QUẢN LÍ
TIẾN ĐỘ TRONG DỰ ÁN
Void Tai_nguyen_ban_dau();
while (i<=nT) //khi nào vẫn còn những công việc chưa được
void Can_doi_tai_nguyen();
4
88
1
0 0
3
5
6
8 8
17
2929
2
6 7
4
88
1
0 0
5
3
6
7
13 13
8 8
2525
28 28
Struct myCost
void Rut_ngan_thoi_gian()
for(k=1;k<=nT;k++)
if((Dt[i]==0)&&(T1[i].tgian>T1[i].tgian))
if(kqcount>1)//Co nhieu hon 1 duong gang
if(dh>1) //Có nhiều hơn 1 công việc có cùng sự kiện đầu
if(T1[B[h][j]].tgianth>T1[B[h][j]].tgiangh)
for[int l=1;l
if[[T1[B[j][l]].tgianth>T1[B[j][l]].tgiangh)&&[Dt[B[j][l]==0)
if(dc>1)
if[cv[k].ds[0]>0)
for[i=1;i<=cv[k].ds[0];i++)
while(i0>0);
CHƯƠNG 3. ÁP DỤNG XÂY DỰNG CHO CÁC DỰ ÁN
XÂY DỰNG
while (k==nT);
if (d==0) cout<<”lỗi sắp topo có chu trình”;
//xác định lại bảng công việc T theo thứ tự Order
T1=T;
for (i=1;i<=nT;i++)
{
T[i]=T1[Order[i]];
for (j=1; j<=T[i].truoc[0];j++)
for (k=1;k<=i-1;k++)
if(T[i].truoc[j]==Order[k])
T[i].truoc[j]=k;
T[i].tt=i;
for (k=1; k<=T[i].truoc[0];k++)
for (j=1; j<=(T[j].truoc[0]-1);j++)
if(T[i].truoc[i]>T[i].truoc[k])
}
Thuật toán chuyển đồ thị biểu diễn công việc sang đồ thị biểu diễn sự kiện
int khongcodinhvao(A,i): Hàm nhận giá trị 1 nếu đỉnh i không có cung
đi vào trong đồ thị công việc biểu diễn bằng ma trận A và nhận giá trị 0 nếu ngược
lại.
void chuyen() {
Khởi tạo mang B=0;
sMax=1; //số sự kiện
for (i=1; I<=nT; I++ )
{if (ladinhket(I,A)==0) tăng thêm 1 đỉnh cho nS;
if (ladinhket(I,A)==1))
if (khongcodinhvao(A,i)==0) B[1][nS] = i;
co1dinhvao(A,i,&cout1,&thu1); //tính toán số cung đi vào
đỉnh i //trả vào cout1, thu1 lưu giá trị của hàng có 1 phần
tử đầu tiên.
for (cot=1;cot<=nS; cot++)
{/*Tìm nút sự kiện kết thúc công việc trước.
if(B[hang][cot]==thư1) B[cot][nS] =i; }
else //cout1 >1 có nhiều cung vào
{
Chọn cung có thứ tự bé nhất;
Xác định công việc trước của cung này trong ma trận A;
Tìm_sự kiện kết thúc công việc này trong đồ thị biểu
diễn bằng ma trận B;
Nối nút này với sự kiện mới thêm;
Đánh số cung này là sự kiện đang xét;
} //end of for
Nếu có nhiều đỉnh kết, ta chọn một trong các đỉnh đó làm đỉnh kết,
nối các đỉnh kia với đỉnh được chọn bằng một công việc ảo.
}//end of chuyen
Thuật toán tìm đường găng
Void Criticalpath;
// Tính thời gian sớm của mỗi sự kiện
{
s[1].tgs=0; s[1].before[0]=1; s1.before1=0;
for (i=2; i<=sMax; i++)
d=0;
for (j=1; j<=i-1; j++)
kiện
s[nS].tgm=s[nS].tgs;
for (i=nS-1; i>=1; i++)
{ for(j=nS; j>=i+1;j++ )
} //end of i
//tính thời gian dự trữ của từng sự kiện
for (i=1; i<=nS; i++)
//Tìm đường găng
Duyệt các sự kiện có dự trữ D[i]=0 theo các chỉ số ghi trong
trường before của từng sự kiện;
Khi được 1 sự kiện thì tăng i;
if ((s[i].before[0]=1) &&(s[i].before[1]=0))
} // end of Criticalpath
Void Tai_nguyen_ban_dau();
while (i<=nT) //khi nào vẫn còn những công việc chưa được xét
Tối ưu hóa
KẾT LUẬN
TÀI LIỆU THAM KHẢO
