VÀ QUẢN LÝ PHẠM VI DỰ ÁN
5. QUAN HỆ GIỮA THỜI GIAN VÀ CHI PHÍ THỰC HIỆN DỰ ÁN
5.2. Bài toán rút ngắn thời gian thực hiện dự án với mức chi phí tăng lên ít nhất
30 24 18
18 0 24
6 24 36
Hình 7.8. Sơ đồ mạng xuất phát với chế độ làm việc bình thường Tổng chi phí 2040 tr. đ.
1 3 4 6
2 5 7
0/0
6/12
30/30 54/54 72/72
96/96 54/60
Cho một dự ỏn với sơ ủồ mạng như hỡnh 7.8 và cỏc số liệu như bảng 7.10.
Bảng 7.10. Số liệu về chi phí thực hiện các công việc Chế ủộ bỡnh thường Chế ủộ khẩn trương
t/t Công việc i-j
top (ngày) Cmin (tr. ủ) tmin (ngày) Cmax (tr. ủ)
e (tr.ủ/ngày)
1 1-2 6 80 4 100 10
2 1-3 30 400 20 520 12
3 2-3 18 180 12 234 9
4 2-5 24 360 18 450 15
5 3-4 24 360 18 420 10
6 4-5 0 0 0 0 0
7 4-6 18 270 12 318 8
8 5-7 36 240 24 360 10
9 6-7 24 150 15 195 5
Thực hiện dự ỏn với chế ủộ khẩn trương nhất của tất cả cỏc cụng việc ta cú sơ ủồ mạng tương ứng như hình 7.9.
Tổng chi phí tăng lên là 2697 - 2040 = 657 tr. VNð có phải là nhỏ nhất không? Phương ỏn rỳt ngắn như hỡnh 7.9 về mặt thời gian ủương nhiờn là ngắn nhất (khụng thể rỳt ngắn hơn ủược nữa vỡ cỏc cụng việc ủều ủó ủược thực hiện với chế ủộ khẩn trương nhất), nhưng chi phớ như thế có thể chưa phải là thấp nhất.
Núi khỏc ủi, phương ỏn thực hiện dự ỏn như hỡnh 7.9 chưa chắc ủó tối ưu. Ta thử rỳt ngắn thời gian thực hiện cỏc cụng việc của dự ỏn theo cỏc nguyờn tắc như ủó trỡnh bày trong mục 7.5.1.
20 18 12
18 0 15
4 18 24
Hình 7.9. Sơ đồ mạng với chế độ làm việc khẩn trương ở tất cả các công việc Tổng chi phí 2697 đ.v.
1 3 4 6
2 5 7
0/0
4/8
20/20 38/38 50/50
65/65 38/41
1. Trong tất cả cỏc cụng việc nằm trờn ủường găng thỡ cụng việc 6-7 là cú mức tăng chi phớ ủơn vị e là nhỏ nhất. Cụng việc này nếu thực hiện theo chế ủộ khẩn trương thỡ cú thể rỳt ngắn từ 24 xuống cũn 15 ngày. Nhưng liệu rỳt ngắn nhiều như vậy cú thay ủổi ủường găng hay khụng? Vẽ lại sơ ủồ mạng với thời gian thực hiện cụng việc 6-7 là 15 ngày (hỡnh 7.10).
30 24 18
18 0 15
6 24 36
Hình 7.10. Sơ đồ mạng khi rút ngắn 6-7 từ 24 xuống còn 15 ngày
1 3 4 6
2 5 7
0/0
6/12
30/30 54/54 72/75
90/90 54/54
Theo sơ ủồ mạng mới ta thấy xuất hiện ủường găng mới 1-3-4-5-7 với chiều dài 90. Như vậy từ sơ ủồ mạng ban ủầu ta rỳt ngắn 9 ngày của cụng việc 6-7 trờn ủường găng cũ 1-3-4-6-7 với chiều dài 96 ngày, ủỏng lẽ thời gian thực hiện dự ỏn chỉ cũn 96 - 9 = 87.
30 24 18
18 0 18
6 24 36
Hình 7.11. Sơ đồ mạng khi rút ngắn 6-7 từ 24 xuống còn 18 ngày
1 3 4 6
2 5 7
0/0
6/12
30/30 54/54 72/72
90/90 54/54
Nhưng do xuất hiện ủường găng mới (cụng việc 4-5 và 5-7 trở nờn găng thay cho 4-6 và 6-7) nờn chỉ rỳt ngắn ủược 96 - 90 = 6 ngày. Vậy ta chỉ nờn rỳt ngắn 6-7 ủi 6 ngày thụi. Lỳc ủú cả 2 cặp cụng việc 4-5; 5-7 và 4-6; 6-7 sẽ ủều găng. Ta cú sơ ủồ mạng mới hỡnh 7.11.
2. Theo sơ ủồ mạng hỡnh 7.11 thỡ lỳc này cú 2 ủường găng là 1-3-4-6-7 và 1-3-4-5-7. ðể rỳt ngắn thời gian thực hiện dự ỏn thỡ cần rỳt ngắn thời gian thực hiện cả 2 ủường găng. Cú cỏc phương ỏn rỳt ngắn với mức tăng chi phớ ủơn vị như bảng sau:
t/t Tên các công việc có thể rút ngắn
Khả năng rỳt ngắn tối ủa (ngày)
Mức tăng chi phớ ủơn vị (tr.ủ/ngày)
1 1-3 10 12
2 3-4 6 10
3 4-6 ủồng thời với 5-7 6 8+10=18
4 6-7 ủồng thời với 5-7 9 5+10=15
Cụng việc 4-6 cú thể rỳt ngắn tối ủa 6 ngày, cụng việc 5-7 cú thể rỳt ngắn tối ủa 12 ngày. Khi rỳt ngắn ủồng thời 2 cụng việc này thỡ khả năng rỳt ngắn tối ủa là 6 ngày.
Tương tự cho cặp cụng việc 6-7 ủồng thời với 5-7.
Vậy rút ngắn 3-4 là rẻ nhất.
Cú thể rỳt ngắn 3-4 tối ủa là 6 ngày từ 24 xuống cũn 18 ngày.
Ta cú sơ ủồ mạng mới hỡnh 7.12.
30 18 18
18 0 18
6 24 36
Hình 7.12. Sơ đồ mạng khi rút ngắn 3-4 từ 24 xuống còn 18 ngày
1 3 4 6
2 5 7
0/0
6/12
30/30 48/48 66/66
84/84 48/48
3. Theo sơ ủồ mạng hỡnh 7.12 vẫn chỉ cú 2 ủường găng cũ. Muốn rỳt ngắn sơ ủồ mạng này có các phương án theo bảng sau:
t/t Tờn cỏc cụng việc rỳt ngắn Khả năng rỳt ngắn tối ủa Mức tăng chi phớ ủơn vị
1 1-3 10 12
2 4-6 ủồng thời với 5-7 6 8+10=18
3 6-7 ủồng thời với 5-7 3 5+10=15
Như vậy rỳt ngắn cụng việc 1-3 là rẻ nhất. Cụng việc này cú thể rỳt ngắn tối ủa là 10 ngày, từ 30 xuống còn 20.
Ta cú sơ ủồ mạng mới hỡnh 7.13.
20 18 18
18 0 18
6 24 36
Hình 7.13. Sơ đồ mạng khi rút ngắn 1-3 từ 30 xuống còn 20 ngày
1 3 4 6
2 5 7
0/0
6/6
24/24 42/42 60/60
78/78 42/42
Theo sơ ủồ mạng mới ta thấy xuất hiện cỏc cụng việc găng mới 1-2; 2-3 thay cho 1-3.
Chớnh vỡ lý do ủú ta rỳt ngắn 1-3 ủi 10 ngày mà chiều dài ủường găng chỉ rỳt ủược 6 ngày từ 84 xuống 78.
Vậy ta chỉ nờn rỳt ngắn 1-3 ủi 6 ngày từ 30 xuống 24 thụi. Lỳc ủú cả 1-3 và cả cặp cụng việc 1-2; 2-3 ủều sẽ găng.
Ta cú sơ ủồ mạng mới hỡnh 7.14.
24 18 18
18 0 18
6 24 36
Hình 7.14. Sơ đồ mạng khi rút ngắn 1-3 từ 30 xuống còn 24 ngày
1 3 4 6
2 5 7
0/0
6/6
24/24 42/42 60/60
78/78 42/42
4. Theo sơ ủồ mạng hỡnh 7.14 ta thấy 4 ủường găng: 1-3-4-6-7; 1-3-4-5-7; 1-2-3-4-6-7 và 1-2-3-4-5-7. Lỳc này cụng việc 3-4 ủó ủược thực hiện theo chế ủộ khẩn trương nhất, ta cú các phương án rút ngắn như bảng sau:
t/t Tờn cỏc cụng việc rỳt ngắn Khả năng rỳt ngắn tối ủa Mức tăng chi phớ ủơn vị
1 1-3 và 1-2 2 22
2 1-3 và 2-3 4 21
3 5-7 và 4-6 6 18
4 5-7 và 6-7 3 15
Vậy ta rỳt ngắn ủồng thời cỏc cụng việc 5-7 và 6-7 với thời gian rỳt ngắn tối ủa ủi 3 ngày (do cụng việc 6-7 cú thời gian thực hiện khẩn trương nhất là 15 ngày). Ta cú sơ ủồ mạng mới hình 7.15.
24 18 18
18 0 15
6 24 33
Hình 7.15. Sơ đồ mạng khi rút ngắn 5-7 từ 36 xuống còn 33 ngày và 6-7 từ 18 xuống còn 15 ngày
1 3 4 6
2 5 7
0/0
6/6
24/24 42/42 60/60
75/75 42/42
5. Theo sơ ủồ mạng hỡnh 7.15 vẫn chỉ cú 4 ủường găng như cũ, nhưng lỳc này ủó cú thờm cụng việc 6-7 ủược thực hiện theo chế ủộ khẩn trương nhất. Ta cú cỏc phương ỏn rỳt ngắn như bảng sau:
t/t Tờn cỏc cụng việc rỳt ngắn Khả năng rỳt ngắn tối ủa Mức tăng chi phớ ủơn vị
1 1-3 và 1-2 2 22
2 1-3 và 2-3 4 21
3 5-7 và 4-6 6 18
Ta rỳt ngắn ủồng thời cỏc cụng việc 5-7 và 4-6 với thời gian rỳt ngắn tối ủa là 6 ngày (do cụng việc 4-6 cú thời gian thực hiện khẩn trương nhất là 12 ngày). Ta cú sơ ủồ mạng mới hình 7.16.
24 18 12
18 0 15
6 24 27
Hình 7.16. Sơ đồ mạng khi rút ngắn 5-7 từ 33 xuống còn 27 ngày và 4-6 từ 18 xuống còn 12 ngày
1 3 4 6
2 5 7
0/0
6/6
24/24 42/42 54/54
69/69 42/42
6. Theo sơ ủồ mạng hỡnh 7.16 với 4 ủường găng cũ nhưng lỳc này cú thờm cụng việc 4-6 ủược thực hiện theo chế ủộ khẩn trương nhất. Bõy giờ chỉ cũn cú thể rỳt ngắn chiều dài ủường găng bằng các cách rút ngắn như bảng sau:
t/t Tên các công việc rút ngắn
Khả năng rỳt ngắn tối ủa Mức tăng chi phớ ủơn vị
1 1-3 và 1-2 2 22
2 1-3 và 2-3 4 21
Ta chọn phương án rút ngắn cặp công việc 1-3 và 2-3 với thời gian rút ngắn nhiều nhất 4 ngày do cụng việc 1-3 cú thời gian thực hiện khẩn trương nhất là 20 ngày. Ta cú sơ ủồ mạng mới hình 7.17.
Sơ ủồ mạng hỡnh 7.17 khụng thể rỳt ngắn hơn ủược nữa vỡ cỏc cụng việc 1-3; 3-4; 4-6 và 6-7 ủều ủó thực hiện với chế ủộ khẩn trương nhất. Nếu rỳt ngắn bất cứ cụng việc nào khỏc (khụng kể cỏc cụng việc trờn) ủều khụng dẫn ủến rỳt ngắn chiều dài ủường găng.
20 18 12
14 0 15
6 24 27
Hình 7.17. Sơ đồ mạng khi rút ngắn 1-3 từ 24 xuống còn 20 ngày và 2-3 từ 18 xuống còn 14 ngày
1 3 4 6
2 5 7
0/0
6/6
20/20 38/38 50/50
65/65 38/38
Tổng chi phớ thực hiện dự ỏn theo sơ ủồ mạng hỡnh 7.17 là 2439 tr. VNð ủược tớnh theo bảng sau:
Chế ủộ bỡnh thường
Chế ủộ khẩn trương t/t Công việc i-j
top Cmin tmin Cmax
e T. gian thực hiện theo sơ
ủồ 7.17
Chi phí thực hiện
1 1-2 6 80 4 100 10 6 80
2 1-3 30 400 20 520 12 20 520
3 2-3 18 180 12 234 9 14 216
4 2-5 24 360 18 450 15 24 360
5 3-4 24 360 18 420 10 18 420
6 4-5 0 0 0 0 0 0 0
7 4-6 18 270 12 318 8 12 318
8 5-7 36 240 24 360 10 27 330
9 6-7 24 150 15 195 5 15 195
Tổng cộng 65 2439
Rừ ràng chi phớ thực hiện dự ỏn thấp hơn so với phương ỏn thực hiện theo chế ủộ cỏc cụng việc ủều thực hiện khẩn trương nhất như sơ ủồ mạng hỡnh 7.9 (cú tổng chi phớ là 2697 tr.
VNð).
Sơ ủồ mạng ban ủầu ủó ủược rỳt ngắn tối ủa với mức tăng chi phớ tối thiểu.