Giáo trình: Tài nguyên và sơ đồ mạng
Từ "Tài nguyên" (Resourse) (viết tắt là R) ở đây 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 ) với giả thiết là bất cứ lúc nào nhu cầu về tài nguyên cũng được thoả mãn. Giả thiết này không hoàn toàn đúng. Trong thực tế thường gặp trường hợp nhu cầu tài nguyên phân bố không đều theo thời gian, có lúc ít hơn, có lúc lại vượt quá giới hạn về khả năng cung cấp tài nguyên......
--------------- ---------------
GIÁO TRÌNH
TÀI NGUYÊN VÀ SƠ ĐỒ
MẠNG
--------------------------
CHƯƠNG 4
TÀI NGUYÊN và SƠ ĐỒ MẠNG
I. GIỚI THIỆU CHUNG về PHÂN PHỐI TÀI NGUYÊN
1. Giới thiệu chung
2. Các loại tài nguyên
II. BIỂU ĐỒ TÀI NGUYÊN
1. Phương pháp sơ đồ PERT cải tiến
2. Chất tải nguồn lực trên sơ đồ PERT cải tiến
3. Kết luận
III. PHÂN PHỐI TÀI NGUYÊN
Quy tắc ưu tiên
IV. CÁC PHƯƠNG PHÁP PHÂN PHỐI TÀI NGUYÊN
1. Phương pháp nối tiếp
2. Phương pháp song song
V. PHÂN PHỐI TÀI NGUYÊN CÓ HẠN CHO CÁC CÔNG VIỆC SAO
CHO THỜI GIAN HOÀN THÀNH DỰ ÁN NGẮN NHẤT
1. Phương pháp cân đối
2. Kết luận
Danh sách hình
H.1 Kết quả đĩều hoà tài nguyên
H.2 Phương pháp tổng bình phương
H.3 Sơ đồ mạng của ví dụ 1
H.4 Sơ đồ Pert cải tiến của ví dụ 1
H.5 Chất tải nguồn lực trên sơ dỗ PERT cải tiến
H.6 Minh hoạ cho ví dụ 7
H.7 Sơ đồ mạng ví dụ 8
H.8 Biểu đồ tài nguyên với số thợ hàn là 12
H. 9 Biểu đồ tài nguyên với số thợ hàn tăng lên 8 người
H.10 Biểu đồ tài nguyên với thợ hàn lên đến 8 các công việc đều khởi công sớm
H.11a Sắp xếp theo phương pháp nối tiếp với quy tắc ưu tiên theo dự trữ min sau
khi phân phối biểu đồ tài nguyên có T = 23 ngày và R 20
H.11b SĐM ban đầu theo thời hạn sớm nhất và biểu đồ nhân lực T=22 ngày và
H.12 Biểu đồ tài nguyên với số thợ hàn chỉ có 6 người
H.13 Sơ đồ mạng ví dụ 11
H.14 Kết quả điều chỉnh sau giai đoạn 1
H.15 Kết quả điều chỉnh lần hai
TÀI LIỆU THAM KHẢO
I. GIỚI THIỆU CHUNG về PHÂN PHỐI TÀI NGUYÊN
1. Giới thiệu chung
Từ "Tài nguyên" (Resourse) (viết tắt là R) ở đây 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 ) với giả thiết là bất cứ lúc nào nhu cầu về tài nguyên
cũng được thoả mãn. Giả thiết này không hoàn toàn đúng. Trong thực tế thường
gặp trường hợp nhu cầu tài nguyên phân bố không đều theo thời gian, có lúc ít
hơn, có lúc lại vượt quá giới hạn về khả năng cung cấp tài nguyên.
Vấn đề đặt ra là phải nghiên cứu cách phân phối 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. Đây là một bài toán
phức tạp bởi tính đa dạng của tài nguyên, mức độ đòi hỏi các loại tài nguyên của
các công việc ở mỗi thời điểm có khác nhau.
Vì thế hiện nay có nhiều công trình nghiên cứu vấn đề này. Về mặt toán học, đã có
nhiều cách giải của nhiều tác giả trong việc áp dụng thuật toán vào các bài toán cụ
thể cũng còn nhiều hạn chế... '
Tuỳ theo điều kiện cụ thể của các yêu cầu đặt ra trong quá trình thi công ta có các
dạng bài toán khác nhau về phân phối tài nguyên.
Tổng quát, có hai loại 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 cân đối tài nguyên một cách tốt
nhất (điều hoà tài nguyên).
Bài toán 2
Mức độ cung cấp tài nguyên có một giới hạn cố đị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ú ý : Hai loại 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 một loại tài nguyên.
Hiện nay có nhiều phương pháp phân phối tài nguyên. Trong trường hợp bài toán
1 cần tìm mọi cách sắp xếp các công việc (theo một quy tắc nào đó hoặc hoàn toàn
ngẫu nhiên) sao cho đường biểu diễn nhu cầu tài nguyên trong suốt thời gian thực
hiện dự án là một đường điều hoà, thể hiện trên hình 1.
H.1 : Kết quả điều hoà tài nguyên
Một cách đơn giản, để thực hiện yêu cầu này là dùng bình phương nhu cầu tài
nguyên 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.
Cách so sánh này rất tốt vì tổng bình phương nhu cầu tài nguyên giảm rất nhanh,
khi sự chênh lệch về nhu cầu tài nguyên giảm đi và sẽ đạt tối thiểu khi tài nguyên
được hoàn toàn điều hoà. 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 đạt tối
thiểu.
Phương pháp so sánh này dựa trên kết quả của toán học. Người ta luôn chứng
minh được rằng :
Nếu x1 +x2 + .... +xn = A
Bất đẳng thức này đạt giá trị tối thiểu khi :
xl = x2 = ... = xn
Trong bài toán phân phối tàì nguyên: Khi tổng bình phương của các giá trị x đại
lối thiểu thì tài nguyên là điều hoà nhất:
Ví dụ 1
Để hoàn thành một công việc cần, 9 công thợ, giới hạn thời gian là 3 ngày. Có
nhiều cách để bố trí số công nhân hoàn thành công việc trong thời gian giới hạn
đó. Như bổ trí 9 công nhân làm trong 1 ngày = 9 công. Một người làm ngày thứ
nhất, 8 người trong ngày thứ hai cũng bằng 9 công, hoặc 3 người cùng làm trong 3
ngày cũng bằng 9 công. . .
Để so sánh phương án nào là tốt nhất ta dùng phương pháp tổng bình phương min.
Kết quả được thể hiện trên hình 6- 2.
H.2 Phương pháp tổng bình phương
a) 92 = 81 b) 12= 1
82 = 64
R = Σx2i = 81 R =Σx2i = 65
c) 22 = 4 d) 32 = 9
72 = 49 32 = 9
R = Σx2i = 53 32 = 9
R =Σx2i=27
Rõ ràng phương án (d) có lợi nhất vì Min = 27.
Ở đây, tài nguyên (R) là số lượng công nhân được phấn phối một cách điều hoà
nhất theo thời gian.
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 giới hạn của tài nguyên được xác định trước. Các công việc
sẽ được sắp xếp sao cho không vượt quá mức giới hạn đó.
Ví dụ 2 :
Điều kiện công trường chỉ cho ta :
10 ngày đầu : có 20 công nhân
20 ngày sau : có 50 công nhân
Phải sắp xếp sao cho các công việc trong 10 ngày đầu không vượt quá 20 công
nhân và 20 ngày sau < 50 công nhâ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
hay tất cả các công việc đòi lỏ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ông việc không những
phụ thuộc vào lôgíc 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ố nguyên tắc sắp xếp
trong đó quan trọng nhất là Quy tắc ưu tiên
2. Các loại tài nguyên
Trong thực tế, các công việc trên sớ đồ mạng cần nhiều loại tài nguyên, cần phải
phân biệt rõ và nắm vững những đặc điểm của tài nguyên.
• Tài nguyên sử dụng cần được xác định
Công việc thợ hàn không thể dùng lao động phổ thông ;muốn cẩu lắp cấu kiện 20
T ; nếu chỉ có cần trục 10 T thì không thể làm được việc đó ; ngược lại có thể dùng
cần trục 20 tấn để cẩu cấu kiện 10 tấn, tức là : Tài nguyên có thể thay thể cái này
bằng cái khác, nhưng nếu tài nguyên A thay được tài nguyên B thì không hẳn là tài
nguyên B đã thay được tài nguyên A.
• Sử dụng tài nguyên
Trong một ngày ta có 100 triệu đồng mà không tiêu đến thì sẽ để lưu lại cho ngày-
hôm sau. Nhưng nếu ta có 10 công thợ trong ngày mà không dùng thì 10 công thợ
đó xem như đã mất, không thể lấy lại được.
Tổng quát: 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 tài nguyên sẽ mất đi nếu không sử dụng vào đúng thời điểm của
nó.
• Đặc điểm của tài nguyên
Khi cần trục đã làm xong việc thì có thể dùng cho việc khác nhưng cái khuôn cửa
đã gắn vào công trình thì không dùng lại nó nữa. Nói cách khác, một số tài nguyên
xong công việc thì được giải phóng để dùng sang việc khác, nhưng có những tài
nguyên đã sử dụng thì coi như mất hắn.
• Công việc có thể sản sinh ra tài nguyên
Tài nguyên có thể tạo ra bới công việc cũng như tiêu thụ bởi công việc. Ví dụ :
Công việc đúc các cấu kiện cho nhà lắp ghép
II. BIỂU ĐỒ TÀI NGUYÊN
1. Phương pháp sơ đồ PERT cải tiến
a. Định nghĩa
Phương pháp sơ đồ PERT cải tiến là sự biến đổi của phương pháp sơ đồ PERT;
trong đó, việc biểu diễn các tiến trình và mối quan hệ giữa chúng được thể hiện
trên hệ trục toạ độ hai chiều, với trục hoành biểu thị thời gian thực hiện các hoạt
động và trục tung biểu
thị trình tự các tiến trình và mối quan hệ bên trong giữa các hoạt động trên tiến
trình đó
b. Quy trình thực hiện
• Bước 1: Lập bảng phân tích hoạt động trong dự án (Tương tự đối với
phương pháp sơ đồ
GANTT).
• Bước 2: Vẽ sơ đồ PERT của dự án với các hoạt động và thời gian từng
hoạt động.
• Bước 3: Vẽ hệ trục toạ độ hai chiều, trong đó:
- Trục hoành: Biểu thị thời gian thực hiện các hoạt động trên tùng tiến trình đã
được xác định từ sơ đồ PERT.
- Trục tung. Biểu thị trình tự các tiến trình và mối quan hệ bên trong giữa các hoạt
động trên tiến trình đó, đã được xác định từ sơ đồ PERT.
• Bước 4: Vẽ sơ đồ PERT cải tiến trên hệ trục toạ độ hai chiều, theo nguyên
tắc:
1/ Tiến trình tới hạn (CP) có thời gian thực hiện dài nhất (Max) dược biểu diễn
thấp nhất (gần trục hoành)
2/ Các tiến trình có thời gian thực hiện tiến trình ngắn dần được biểu diễn lần lượt
theo thứ tự từ dưới lên trên.
3/ Tiến trình có thời gian thực hiện tiến trình ngắn nhất (Min) dược biểu diễn trên
cùng (cao nhất).
4/ Các tiến trình trên sơ đồ PERT cải tiến dược biểu diễn bằng các đường mũi tên,
thẳng hàng, song song với trục hoành (khác với sơ dỗ PERT - liên kết mạng).
5/ Khép kín sơ đồ PERT cải tiến bằng các đường nét đứt (------).
Ví dụ 3
Hãy biểu diễn sơ đồ PERT cải tiến của dự án nghiên cứu có các thông số được cho
trong bảng 1
Bài giải
Bước 1: Lập bảng phân tích hoạt động trong dự án
- Xem Bảng 1.
Bước 2: Vẽ sơ đồ PERT của dự án với các hoạt động và thời gian từng hoạt động.
- Xem Hình 13, sơ đồ PERT của dự án.
H.3 Sơ đồ mạng của ví dụ 1
Bước 3: Vẽ hệ trục toạ độ hai chiều để biểu diễn sơ đồ PERT cải tiến.
- Xem Hình 4.
H.4 Sơ đồ Pert cải tiến của ví dụ 1
Bước 4: Vẽ sơ đồ PERT cải tiến trên hệ trục toạ độ hai chiều, theo các nguyên tắc
quy định.
- Tiến trình A - B - E = 20 + 15 + 25 = 60 ngày là tiến trình tới hạn, dược biểu
diễn bằng đường gạch đậm, nằm gần trục hoành nhất.
- Tiến trình A - D - G = 20 + 20 + 0 = 40 ngày, được biểu diễn phía trên đường
biểu diễn tiến trình A - B - E.
- Tiến trình A - C - F = 20 + 10 + 0 = 30 ngày, là tiến trình có thời gian thực hiện
ngắn nhất, dược biểu diễn trên cùng, (cao nhất).
- Khép kín sơ đồ PERT cải tiến bằng đường nét đút.
2. Chất tải nguồn lực trên sơ đồ PERT cải tiến
a. Quy trình thực hiện
Bước 1: Vẽ sơ đồ PERT cải tiến trên hệ trục toạ độ hai chiều (xem phần trên)
Bước 2: Chất tải nguồn lực trên sơ đồ PERT cải tiến, theo nguyên tắc:
• Căn cứ vào đường biểu diễn các tiến trình trên sơ đồ PERT cải tiến.
• Chất tải hao phí nguồn lực cho từng hoạt động nằm trên tiến trình trong
từng dợn vị thời gian.
• Mỗi hoạt động chỉ có một lần hao phí nguồn lực thực hiện duy nhất; mặc
dù, một hoạt động có thể có mặt trong nhiều tiến trình trên dơ đồ PERT cải
tiến.
Bước 3: Nhận dạng "đình lồi" hay "hốc lõm trong chất tải nguồn lực thực hiện dự
án. Từ đó đề ra biện pháp khắc phục trong điều hoà nguồn lực.
Ví dụ 4
Áp dụng phương pháp sơ đồ PERT cải tiến để chất tải nguồn lực trong ví dụ 1
Bài giải
Bước 1: Vẽ sơ đồ PERT cải tiến trên hệ trục toạ độ hai chiều, theo các nguyên tắc
quy định.
- Xem H.4, sơ đồ PERT cải tiến ở ví dụ 1
Bước 2: Chất tải nguồn lực trên sơ đồ PERT cải tiến, theo các nguyên tắc quy
đình.
- Xem Hình 5. Chất tải nguồn lực trên sơ đồ PERT cải tiến.
H.5 Chất tải nguồn lực trên sơ dỗ PERT cải tiến.
Bước 3: Nhận dạng sơ đồ chất tải nguồn lực trên sơ đồ PERT cải tiến.
Trong thời gian đến 20 ngày đầu: Dự án huy động 2 đơn vị nguồn lục.
Trong thời gian từ 20 đến 30 ngày: Dự án huy động 6 đơn vị nguồn lực (xuất hiện
"Đỉnh lồi").
Trong thời gian từ 30 đến 40 ngày: Dự án huy dộng 4 đơn vị nguồn lục.
Trong thời gian từ 40 đến 60 ngày: Dự án huy động 2 dợn vị nguồn lực.
3. Kết luận
"Đỉnh lồi hay cao điểm, hay sự căng thẳng trong huy dộng nguồn lực thực hiện
dự án xuất hiện trong giai đoạn từ 20 đến 30 ngày.
Một trong số nhiệm vụ quan trọng của quản trị gia dự án là "san bằng dính lồi hay
hốc lõm trong huy động nguồn lực thực hiện dự án; có nghĩa là thực hiện việc diều
hoà nguồn lực bằng "Phương pháp cân bằng nguồn lực" được trình bày dưới đây.
III. PHÂN PHỐI TÀI NGUYÊ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 một ví dụ
Ví dụ 5
Giả sử từ một sự kiện : chúng ta 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 = 4, B = 2, C = 2 ,
Giả thiết ở thời điểm i bắt đầu các công việc, mức tài nguyên giới hạn là 8 công
nhân.
Chúng ta có 3 phương án được mô tả ở hình 6.4.
Giới hạn. tài nguyên : 8CN
Phương án 1 : A, D bắt đầu ; B, C lùi lại
Phương án 2 : A, B, C bắt đấu ; D lùi lại
Phương án 3 : B, C, D bắc đẩu ; A lùi lại.
Cả 3 phương án đều thoả mãn mức giới hạn về tài nguyên nhỏ hơn hoặc bằng mức
tài nguyên cho phép là 8 công nhân.
Một vấn đề được đặt ra là : 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 biết được
công việc nào có quyền xếp thứ tự trước hoặc quyết định phương án nào sẽ được
chọn.
- Các công việc găng cần được ưu tiên vì phải kết thúc các công việc này đúng
thời hạn dự án. ---
- Cũng có thể các công việc ngắn nhất phải được ưu tiên trước, vì sẽ nhanh chóng
vượt qua được tình trạng khó khăn về tài nguyên khi các công việc này kết thúc ;
- Hoặc có thể các công việc có thời điểm bắt đầu hay kết thúc muộn nhất hoặc
sớm nhất, nên làm trước...
Nói tóm lại, chúng ta có nhiều cách ưu tiên và lí do ưu tiên nào cũng có ưu điểm
của nó. Hiện nay chưa có công trình nghiên cứu nào công bố kết quả về quy tắc ưu
tiên tốt nhất ? bởi vì ngoài những quy tắc đề ra ở trên còn có nhiều biến số phức
tạp khác, phụ thuộc nhu cầu tài nguyên của từng công việc và của cả những công
việc tiếp theo. Điều phức tạp hơn nữa là thực tế khi một công việc được lưu lại thì
thời gian dự trữ của nó bị rút ngắn, đó cũng có thể là một quy tắc ưu tiên.
Một vài ví dụ dưới đây sẽ minh hoạ cho những điều trên.
Ví dụ 6:
Trên hình 6- 5 trình bày một mạng nhỏ với 3 công việc, 2 công việc cần thợ mộc
kí hiệu (M) và một công việc cần lao động thường (L) . Giả sử mức tài nguyên chỉ
có một thợ mộc và 1 lao động. Kết quả của các cách sắp xếp ưu tiên khác nhau
được mô tả trên hình vẽ.
a) Với quy tắc ưu tiên theo thời gian dự trữ min có thời gian T = 11 ngày
Hình 6-5 : Kết quả của các cách xếp ưu tiên khác nhau
b) Với quy tắc ưu tiên theo thời gian thực hiện công việc có thời gian i = 7 ngày.
Trên hình 6.5.a là sắp xếp theo thời gian dự trữ minh thì công việc găng ( 1- 3)
được làm trước ; thợ mộc làm trong 6 ngày, sau đó thợ mộc làm tiếp công việc (1-
2) một ngày, rồi lao động thường nới bắt đầu công việc (2- 3) hết 4 ngày. Kết quả
là T : 11 ngày.
Hình 6- 5.b sắp xếp theo thời gian thực hiện công việc nhỏ nhất , thì thợ mộc M
làm công việc (1- 2) trước, sau đó lao động thường có thể tiến hành công việc (2-
3) tiếp theo và IVI làm công việc (l- 3). Kết quả là thời hạn T = 7 ngày
Rõ ràng rằng khi áp dụng các quy tắc ưu tiên khác nhau sẽ thu được kết quả khác
nhau. Trong ví dụ này quy tắc ưu tiên theo thời gian thực hiện công việc cho ta kết
quả tốt hơn.
Cũng với những yêu cầu như ví dụ trên ta làm tiếp một mạng khác như sau . Giới
hạn tài nguyên 1M và 1 L Cũng phân tích như vậy với hình 6.ta ta thấy ưu tiên
theo thời gian dự trữ thì thời hạn là 12 ngày. Còn hình
6.6b
a) Kết quả với quy tắc ưu tiên theo dự trữ công việc
b) Kết quả với quy tắc ưu tiên theo thời gian thực hiện công việc.
ưu tiên theo thời gian thực hiện công việc nhỏ nhất thì thời hạn là 15 ngày.
Ở ví dụ này quy tắc ưu tiên theo thời gian dự trữ công việc lại tốt hơn. Điều đáng
tiếc là cát kết quả đó trước khi phân tích không thể biết được và cũng chưa có thể
nói được là quy tắc ưu tiên nào sẽ cho kết quả tốt hơn. Có một điều cần chú ý là
mọi quy tắc ưu tiên đề ra nhiều khi vẫn thua trực giác của con người.
Ví dụ 7
Một mạng nhỏ có 5 công việc song song trong đó có 2 công việc thời gian thực
hiện là 12 ngày và 3 công việc thời gian thực hiện là 8 ngày. Mỗi công việc đều
cần 1 công nhân. Mức tài nguyên giới hạn là 2 công nhân.
a) Nếu ưu tiên theo thời gian dự trứ cho ta kết quả là thời gian hoàn thành dự án T
= 28 ngày. .
b) Nếu ưu tiên theo thời gian thực hiện công việc cho ta T = 28 ngày.
c) Nhưng theo trực giác có thể sắp xếp để có T = 24 ngay là kết quả tối ưu.
H. 6 Minh hoạ cho ví dụ 7
