Luận án Một số phương pháp gần đúng giải bài toán lập lịch với tài nguyên giới hạn

ó giá trị được biểu diễn trong bảng 
2.6. 
Bảng 2.6: Giá trị của vector độ chênh d 
Task W1 W2 
 d 55 40 
49 
Tính độ chênh giữa 2 cá thể được trình bày trong Algorithm 2.1. 
Algorithm 2.1. Tính độ chênh giữa 2 cá thể 
Input: 
- S1,S2: 2 cá thể đầu vào 
- taskcount: số lượng tác vụ 
 Output: vector độ chênh 
1 Begin 
2 d = {} 
3 p = thang đo 
4 for i=1 to taskcount 
5 j = vị trí tài nguyên thực hiện task i của S1 
6 k = vị trí tài nguyên thực hiện task i của S2 
7 di = mod(abs(pi,j - pi,k),100) 
8 end for 
9 return d; 
10 End 
Phép cộng 02 cá thể - tạo cá thể mới 
Phép cộng 02 cá thể tạo ra một cá thể mới, được thực hiện qua các bước 
như sau: 
- Tính độ chênh giữa 02 cá thể 
- Cộng thang đo của cá thể 1 với độ chênh 
- Cá thể mới nhận được bằng việc tham chiếu kết quả vào thang đo để 
tìm tài nguyên thực hiện, được thực hiện theo công thức 2.4 
Si = index (round(mod((di + pi,j),100)) ) (2.4) 
Trong đó: 
- i: chỉ số của tác vụ 
- j: vị trí tài nguyên thực hiện tác vụ trong thang đo 
- index: trả về chỉ số tài nguyên ở vị trí tương ứng trên thang đo 
Trong ví dụ 2.4 ở trên, xét S = S1 + S2, ta có: 
S1 = index (round(mod(d1 + p1,3))) = index(round(75)) = 9 
50 
S2 = index (round(mod(d2 + p2,8))) = index(round(115)) = 6 
Như vậy, ta được phương án mới S với W1 được thực hiện bởi L9, W2 được 
thực hiện bởi tài nguyên L6. Chi tiết được thể hiện trong bảng 2.7. 
Bảng 2.7: Kết quả cộng hai cá thể 
Task W1 W2 
d 55 40 
p 20 75 
S1 + p 75 115 
S 9 6 
Phép cộng 2 cá thể được trình bày trong Algorithm 2.2. 
Algorithm 2.2. Cộng 2 cá thể để tạo cá thể mới 
Input: 
- S1,S2: hai cá thể đầu vào 
- taskcount: số lượng tác vụ 
 Output: cá thể mới 
1 Begin 
2 S = {} 
3 p = thang đo 
4 d = độ chênh giữa S1 và S2 
5 for i=1 to taskcount 
6 Si = index (round(mod((di + p1,i),100)) ) 
7 end for 
8 return S; 
9 End 
2.3. Đề xuất thuật toán M-PSO 
Thuật toán tối ưu bầy đàn PSO là thuật toán tiến hóa trong đó mỗi cá thể 
được tạo ra dựa trên thừa kế kinh nghiệm của cả quần thể và của chính cá thể 
đó, do vậy nâng cao được khả năng hội tụ, nhanh tìm ra được nghiệm tốt. 
Là thuật toán có tốc độ hội tụ nhanh nên PSO được giới nghiên cứu quan 
tâm và đề xuất nhiều phiên bản cải tiến, trong đó một phương pháp thông dụng 
là Tìm kiếm lân cận Local search PSO [CT2], [CT6]. Tuy nhiên phương pháp 
51 
Tìm kiếm lân cận đôi lúc khiến chương trình mắc kẹt tại bẫy cực trị địa phương. 
Mục tiếp theo sẽ đề xuất một phương pháp hiệu quả khác, phương pháp Di cư, 
cho phép thuật toán thoát khỏi vùng cực trị địa phương để tìm tới những vùng 
nghiệm mới có thể có các nghiệm tốt hơn. 
Thuật toán M-PSO (Migration PSO) là thuật toán áp dụng cho bài toán MS-
RCPSP nhằm cực tiểu hóa makespan, thuật toán được xây dựng dựa trên thuật 
toán tối ưu bầy đàn PSO và được cải tiến ở các điểm sau: 
(i) Tìm và phát hiện cực trị địa phương; 
(ii) Áp dụng kỹ thuật di cư (Migration) để thoát khỏi cực trị địa phương. 
2.3.1. Kỹ thuật Di cư 
Khi thực hiện tiến hóa, thuật toán PSO có xu hướng rơi vào các vùng cực 
trị địa phương nghĩa là sau nhiều thế hệ quần thể vẫn bị hút vào khu vực xung 
quanh một cực trị địa phương. Để hướng dẫn quần thể đi tới giá trị tối ưu, cần 
phải đưa chúng thoát ra khỏi vùng lân cận xung quanh cực trị địa phương để 
chuyển tới một vùng không gian nghiệm khác, đó là mục đích của kỹ thuật di 
cư trong luận án này. Ngoài việc giúp thuật toán thoát khỏi cực trị địa phương, 
kỹ thuật di cư còn mở rộng không gian tìm kiếm, nâng cao kết quả của thuật 
toán. 
Định nghĩa 2.3: Quần thể được gọi là tiến hóa không thành công nếu giá 
trị makespan của quần thể không thay đổi qua 2 thế hệ liên tiếp. 
2.3.1.1. Ý tưởng của kỹ thuật di cư 
Kỹ thuật Di cư áp dụng trong thuật toán M-PSO được thực hiện qua các 
bước sau: 
Bước 1: Tìm và phát hiện cực trị địa phương 
Để phát hiện cực trị địa phương, ta dùng một biến nfail để đếm số lần quần 
52 
thể tiến hóa không thành công liên tiếp, nếu giá trị này lớn hơn một ngưỡng 
quy định (nmax), thì quần thể đã rơi vào cực trị địa phương. Công thức 2.5 trình 
bày cách tính nfail. 
𝑛𝑓𝑎𝑖𝑙 = {
𝑛𝑓𝑎𝑖𝑙 + 1 𝑖𝑓 𝑛𝑒𝑤𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛 = 𝑜𝑙𝑑𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛 
0 𝑖𝑓 𝑛𝑒𝑤𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛 ≠ 𝑜𝑙𝑑𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛
 (2.5) 
 Bước 2: Di chuyển quần thể 
Việc di chuyển quần thể sang vị trí khác được thực hiện như sau: 
- Duyệt từng cá thể của quần thể; 
- Với mỗi tác vụ i của cá thể, xem xét tập Li các tài nguyên có thể thực 
hiện được tác vụ i, sắp xếp các tài nguyên thứ tự tăng dần của chỉ số tài 
nguyên; 
- Lấy tài nguyên ở vị trí đối xứng để thực hiện tác vụ i thay cho tài nguyên 
hiện tại. 
Hình 2.4 minh họa việc di cư của tác vụ bằng việc thay đổi tài nguyên thực 
hiện. Cụ thể, tác vụ đang được thực hiện bởi tài nguyên L2 sẽ được bố trí tài 
nguyên thực hiện mới là Lm-1 và tác vụ đang được thực hiện bởi tài nguyên Lm 
sẽ được bố trí tài nguyên mới là L1 để thực hiện. 
Hình 2.4. Thay đổi tài nguyên thực hiện tác vụ 
Việc dịch chuyển tài nguyên thực hiện tác vụ cần đảm bảo ràng buộc của 
bài toán. Sau khi thực hiện với toàn bộ quần thể, ta sẽ được một quần thể mới 
được di chuyển bằng kỹ thuật Migration. 
Ví dụ 2.2: 
Xem xét một dự án với các thông tin như sau: 
L1 L2 ... Lm-1 Lm 
L1 L2 ... Lm-1 Lm 
53 
- Tập tác vụ W ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
- Tập tài nguyên L={1, 2, 3, 4}; 
- Năng lực của các tài nguyên được thể hiện như trong Bảng 2.8. 
Bảng 2.8: Năng lực của các tài nguyên 
 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 
L1 × × × × × × 
L2 × × × × × × × × 
L3 × × × × × × × 
L4 × × × × × × × 
Xem xét một phương án lịch biểu với các thiết lập tài nguyên thực hiện tác 
vụ như trong bảng 2.9. 
Bảng 2.9: Lịch biểu khả thi của dự án trong ví dụ 2.2 
Tác vụ 1 2 3 4 5 6 7 8 9 10 
Tài nguyên 1 1 2 1 2 2 4 1 1 4 
Xét tác vụ 1, tập tài nguyên thực hiện tác vụ 1, W1 = {L1, L2, L3, L4} 
Áp dụng kỹ thuật di cư với tác vụ 1, ta thấy, tài nguyên thực hiện tác vụ 1 
hiện tại là L1, dùng kỹ thuật di cư để thiết lập tài nguyên thực hiện tác vụ 1 bằng 
cách lấy tài nguyên đối xứng trong tập tài nguyên W1, ta có tài nguyên mới để 
thực hiện tác vụ 1 là L4. 
Áp dụng tương tự với các tác vụ 2, 3, 4, 5, 6, 7, 8, 9, 10, ta sẽ được cá thể 
sau khi di cư với thiết lập tài nguyên thực hiện được thể hiện trong bảng 2.10. 
Bảng 2.10: Lịch biểu mới sau khi di cư 
Tác vụ 1 2 3 4 5 6 7 8 9 10 
Tài nguyên 4 3 4 4 3 2 2 4 4 2 
Ta có thể thấy, trong lịch biểu mới, tại vị trí của tác vụ 6, tài nguyên thực 
hiện không thay đổi do W6 = {L1,L2,L3}. Điều này hạn chế khả năng tạo ra các 
54 
bước di chuyển lớn của cá thể. Tuy nhiên, vấn đề này sẽ ít gặp phải trong bài 
toán với số lượng tài nguyên thực hiện lớn hơn. 
2.3.1.2. Hàm Migration 
Algorithm 2.2. Migration 
Input: Pall – quần thể hiện tại 
Output: Pnew – quần thể sau khi di chuyển 
Begin 
1. Pnew = {} 
2. For i=1 to size(P) // duyệt lần lượt từng cá thể 
3. Pi = Pall[i]; // lấy cá thể thứ i từ quần thể 
4. For j = 1 to y // duyệt lần lượt từng task 
5. Wi = Danh sách tài nguyên thực hiện Wi 
6. Wi = Sort(Wi) // sắp xếp chỉ số tài nguyên trong Wi 
7. idx = Chỉ số tài nguyên thực hiện task i 
8. idx = size(Wi) – idx + 1 
9. Li = Wi[idx] 
10. End for // j 
11. Pnew = Pnew + {Pi} 
12. End for // i 
13. Return Pnew; 
End Function 
2.3.2. Thuật toán M-PSO 
M-PSO được trình bày trong Algorithm 2.3 với đầu vào của thuật toán là 
số thế hệ thực hiện để tìm phương án tốt nhất (tmax) và ngưỡng phát hiện cực trị 
địa phương (nmax). Các bước chạy chi tiết như sau: 
Algorithm 2.3. M-PSO 
Input: nmax: ngưỡng áp áp dụng migration, tmax: số thế hệ 
Output phương án tốt nhất gbest 
1 Begin 
55 
2 Pall = Load dữ liệu iMOPSE và khởi tạo quần thể ban đầu 
3 t = 0 
4 nfail = 0 
5 while ( t < tmax ) 
6 t = t + 1 
7 for i=1 to size(Pall) do 
8 tính giá trị hàm mục tiêu f(Pi) 
9 end for 
10 for i = 1 to size(Pall) do 
11 if f(Pi) < f(fitnessi) then 
12 pbesti = Pi 
13 f(pbesti) = f(Pi) 
14 end if 
15 end for 
16 for i=1 to size(Pall) do 
17 if(f(Pi) < f(gbest)) then 
18 gbest = Pi 
19 f(gbest) = f(Pi) 
20 end if 
21 if f(Pi)!= f(Pi-1) then 
22 nfail = 0 
23 else 
24 nfail += 1 
25 end if 
26 end for 
27 for i=1 to size(Pall) do 
28 cập nhật vector dịch chuyển theo (1.1.a) 
29 Cập nhật vector vị trí theo (1.1.b) 
30 end for 
31 if (nfail = nmax) 
32 Pall = Migration(Pall) 
33 nfail = 0 
34 end if 
35 end while 
56 
36 return gbest 
37 end 
f: objective function 
Các dòng 21 đến 25 thể hiện biến đếm để phát hiện cực trị địa phương. 
Các dòng 31 đến 34 xử lý việc áp dụng kỹ thuật di cư quần thể khi đã phát 
hiện ra cực trị địa phương. 
2.3.3. Thực nghiệm 
2.3.3.1. Dữ liệu thực nghiệm 
Để đánh giá, thuật toán đã được cài đặt, chạy thử nghiệm với bộ dữ liệu 
iMOPSE [42],[45], đây là bộ dữ liệu chuẩn đã được chứng minh phù hợp với 
bài toán MS-RCPSP và đã có nhiều nhóm nghiên cứu sử dụng. 
Bộ dữ liệu được lưu trữ dưới dạng file def, mỗi file bao gồm các thông tin: 
 Số tác vụ (Task) cần thực hiện; 
 Số tài nguyên (Resource) sử dụng để thực hiện các tác vụ; 
 Số lương ràng buộc giữa các tác vụ (Precedence Relation), chỉ ra thứ tự ưu 
tiên trong việc thực hiện các tác vụ; 
 Số lượng kỹ năng của các tài nguyên (Skill); 
 Kỹ năng và mức kỹ năng của mỗi tài nguyên, một tài nguyên có thể bao 
gồm nhiều kỹ năng. 
Chi tiết bộ dữ liệu iMOPSE được trình bày trong bảng 2.11 dưới đây. 
Bảng 2.11: Bộ dữ liệu iMOPSE cho bài toán MS-RCPSP 
Dataset instance Tasks Resources 
Precedence 
Relations 
Skills 
100_5_20_15 100 5 22 15 
100_5_48_9 100 5 48 9 
100_5_48_15 100 5 46 15 
57 
Dataset instance Tasks Resources 
Precedence 
Relations 
Skills 
100_5_64_9 100 5 64 9 
100_5_64_15 100 5 64 15 
100_10_26_15 100 10 26 15 
100_10_47_9 100 10 47 9 
100_10_48_15 100 10 48 15 
100_10_64_9 100 10 64 9 
100_10_65_15 100 10 65 15 
100_20_22_15 100 20 22 15 
100_20_47_9 100 20 47 9 
100_20_46_15 100 20 46 15 
100_20_65_9 100 20 65 9 
100_20_65_15 100 20 65 15 
200_10_50_9 200 10 50 9 
200_10_50_15 200 10 50 15 
200_10_84_9 200 10 84 9 
200_10_85_15 200 10 85 15 
200_10_128_15 200 10 128 15 
200_40_144_15 200 40 133 15 
200_20_55_9 200 20 55 9 
200_20_54_15 200 20 54 15 
200_20_97_9 200 20 97 9 
200_20_97_15 200 20 97 15 
200_20_145_15 200 20 145 15 
200_40_45_9 200 40 45 9 
200_40_45_15 200 40 45 15 
200_40_90_9 200 40 90 9 
200_40_91_9 200 40 91 15 
2.3.3.2. Cấu hình thực nghiệm 
Các tham số thực nghiệm: 
- Dữ liệu: 30 file dữ liệu trong bộ dữ liệu iMOPSE như trong bảng 2.11; 
- Khởi tạo quần thể ban đầu với 100 cá thể; 
- Số thế hệ tiến hóa: 100.000; 
- Số lần chạy thực nghiệm trên mỗi bộ dữ liệu: 50; 
58 
- Hệ số phát hiện cực trị địa phương nmax: 30. 
Môi trường thực nghiệm: 
- Thực nghiệm được tiến hành trên môi trường Matlab 2014 
- Máy tính thực nghiệm: CPU Intel Core i5, tốc độ 2.2 GHz, RAM 6GB, 
hệ điều hành Windows 10 (64 bit). 
2.3.3.3. Kết quả thực nghiệm 
Kết quả thực nghiệm được thể hiện trong bảng 2.12 dưới đây. Kết quả thực 
nghiệm của M-PSO được so sánh với: 
- Thuật toán GA-M: là thuật toán di truyền cải tiến của nhóm 
Myszkowski, thuật toán này được nhóm tác giả công bố cùng với bộ 
công cụ GA Runner để chạy và kiểm chứng kết quả, nên kết quả của 
GA-M là khách quan và tin cậy [42],[45]. 
- Một số thuật toán lai (hybrid) như: HAntCO, GRASP[44]. Đây là các 
thuật toán tiến hóa được lai ghép tính ưu việt của hai hoặc nhiều thuật 
toán hoặc kỹ thuật khác nhau. 
59 
Bảng 2.12: Kết quả thực nghiệm M-PSO 
TT Dataeset 
GA-M HAntCO GRASP M-PSO 
Best Avg Std Best Avg Std Best Avg Std Best Avg Std 
1 100_5_22_15 517 524 5.3 504 505 0.8 503 504 0.5 485 486 1.7 
2 100_5_46_15 584 587 4.7 604 604 0 552 556 2.6 530 531 0.5 
3 100_5_48_9 528 535 9.7 521 523 1.6 510 510 0.8 490 492 1.6 
4 100_5_64_15 527 530 2.5 516 523 2.9 501 502 0.8 478 479 1.3 
5 100_5_64_9 508 521 9.9 507 515 3.9 494 494 0.6 471 474 2.5 
6 100_10_26_15 292 292 0.0 266 270 2.2 251 258 3.2 233 233 0.4 
7 100_10_47_9 296 296 0.0 297 302 4 263 264 0.7 257 261 3.7 
8 100_10_48_15 279 282 2.9 278 286 4.4 256 257 1.2 244 245 0.6 
9 100_10_64_9 296 305 6.6 287 296 5.1 255 257 1.9 240 246 5.9 
10 100_10_65_15 286 290 5.0 281 287 3.5 256 260 1.9 244 245 1.3 
11 100_20_22_15 163 169 5.8 161 170 3.6 134 137 1.6 128 131 3.1 
12 100_20_46_15 197 207 6.9 194 199 2.6 170 174 3.1 162 165 2.9 
13 100_20_47_9 185 186 0.5 180 187 3.7 133 140 2.2 124 128 3.6 
14 100_20_65_15 240 240 0.5 218 220 2.7 213 213 0 228 230 1.8 
15 100_20_65_9 181 187 4.5 180 185 3.1 135 135 1.4 125 125 0.3 
16 200_10_128_15 577 583 4.9 522 528 3.1 491 496 4.2 461 464 2.7 
60 
TT Dataeset 
GA-M HAntCO GRASP M-PSO 
Best Avg Std Best Avg Std Best Avg Std Best Avg Std 
17 200_10_50_15 553 577 17.5 529 543 8 524 528 3.8 489 490 0.7 
18 200_10_50_9 585 589 5.0 546 556 4.8 506 508 1.4 487 491 3.7 
19 200_10_84_9 567 583 11.4 571 581 6.9 526 527 0.8 508 510 2.1 
20 200_10_85_15 549 555 4.9 526 538 6.5 496 498 1.1 473 476 2.5 
21 200_20_145_15 326 328 2.0 309 314 4.4 262 271 4.2 236 237 1.4 
22 200_20_54_15 363 385 20.8 336 349 6.6 304 308 3.7 256 256 0.3 
23 200_20_55_9 312 318 4.2 313 317 3.1 257 258 0.6 251 255 3.5 
24 200_20_97_15 424 438 9.7 356 368 4.8 347 347 0 334 337 3.3 
25 200_20_97_9 321 326 6.2 326 332 4.1 253 256 1.6 255 256 0.9 
26 200_40_133_15 215 222 6.2 214 221 3.4 163 170 4.1 147 151 4.1 
27 200_40_45_15 201 210 6.3 206 212 2.6 164 164 0 163 167 4 
28 200_40_45_9 209 213 2.9 209 215 3.8 144 147 1.6 152 162 9.5 
29 200_40_90_9 211 215 3.1 211 214 1.8 148 153 4.5 145 152 7.1 
30 200_40_91_15 200 205 3.4 207 212 2.9 153 159 2.6 135 143 8.3 
61 
Bảng 2.13: So sánh kết quả thực nghiệm M-PSO với các thuật toán khác 
Thuật toán 
BEST AVG 
Tổng 
STD Số 
lượng 
Tỉ lệ (%) Số 
lượng 
Tỉ lệ (%) 
Từ Đến Từ Đến 
M-PSO 85.3 
GA-M 30/30 5.0 32.97 30/30 4.3 33.56 173.3 
HAntCO 29/30 -4.59 34.78 29/30 -4.55 32.55 110.9 
GRASP 27/30 -7.04 15.79 26/30 -10.2 16.88 56.7 
Trong bảng 2.13: 
- Cột “Số lượng” thể hiện số bộ dữ liệu (trên tổng số 30 bộ) mà thuật toán 
M-PSO có kết quả tốt hơn thuật toán ở hàng tương ứng. 
- Tỉ lệ (%) cho biết kết quả của M-PSO tốt hơn/kém hơn kết quả của các 
thuật toán. Giá trị âm thể hiện một vài trường hợp mà M-PSO cho kết 
quả kém hơn. 
2.3.4. Đánh giá chất lượng lời giải của thuật toán 
Luận án đã tiến hành thực nghiệm thuật toán M-PSO áp dụng cho bài toán 
MS-RCPSP. Thực nghiệm được chạy trên 30 bộ dữ liệu iMOPSE, với số lần 
chạy thực nghiệm là 50 lần, số thế hệ tiến hóa là 100.000, thuật toán được cài 
đặt trên môi trường thử nghiệm Matlab 2014. Kết quả thực nghiệm được trình 
bày trong bảng 2.12. Kết quả thực nghiệm được tổng hợp và so sánh trong 
bảng 2.13. 
So sánh với GA-M cải tiến của nhóm Myszkowski, ta thấy: 
- Về giá trị BEST và AVG: M-PSO tốt hơn GA-M trong tất cả các trường 
hợp, trong đó giá trị BEST tốt hơn GA-M từ 5.0% đến 32.97%, giá trị 
AVG tốt hơn GA-M từ 4.3% đến 33.56%. 
- Về giá trị độ lệch chuẩn STD, tổng độ lệch chuẩn của GA-M là 173,3, 
62 
của M-PSO là 85,3. Từ kết quả này, có thể thấy, thuật toán M-PSO mang 
lại hiệu quả cao hơn thuật toán GA-M và tính ổn định của M-PSO cũng 
tốt hơn. 
So sánh với các thuật toán lai (hybrid) khác 
- Bảng 2.13 cho thấy, kết quả của M-PSO có kết quả tốt hơn các thuật 
toán lai ở hầu hết các trường hợp, cụ thể: tốt hơn HAntCO 29/30 bộ dữ 
liêu, tốt hơn GRASP 27/30 bộ dữ liệu với giá trị BEST, 26/30 bộ dữ liệu 
với giá trị AVG. Một số trường hợp M-PSO kém hơn các thuật toán lai, 
tuy nhiên, giá trị kém hơn không nhiều. Ví dụ, khi so sánh với thuật toán 
GRASP, trường hợp kém nhất của M-PSO so với GRASP là -7.04%, 
trong khi đó giá trị tốt nhất cao hơn GRASP là 15.79%. 
Như vậy, trong thuật toán mới M-PSO với việc bổ sung phương pháp di cư 
quần thể đã mang lại hiệu quả tốt cho thuật toán. Bản chất của việc di cư quần 
thể là việc mở rộng không gian tìm kiếm, giúp thuật toán có khả năng quét và 
duyệt được nhiều phương án hơn, do vậy có khả năng tìm được nghiệm tốt hơn. 
Ngoài ra, phương pháp di cư giúp thuật toán mới dễ dàng thoát khỏi cực trị địa 
phương. 
63 
2.3.5. Hình ảnh so sánh M-PSO và GA-M 
Hình 2.5. So sánh giá trị BEST giữa M-PSO và GA-M 
Hình 2.6. So sánh giá trị STD giữa M-PSO và GA-M 
64 
2.4. Đề xuất thuật toán DEM 
Thuật toán DEM (Reallocate Differential Evolution for MS-RCPSP) 
[CT7], [CT8] được xây dựng trên cơ sở là thuật toán DE để giải bài toán MS-
RCPSP. Mục tiêu của thuật toán này là tìm ra được lịch biểu với thời gian thực 
hiện ngắn nhất. DEM áp dụng cho MS-RCPSP với cải tiến như sau: 
Với cá thể tốt nhất sau mỗi thế hệ, áp dụng phương pháp tìm và thay thế 
tài nguyên thực hiện các tác vụ của cá thể. Phương pháp này được gọi là 
tái thiết lập tài nguyên thực hiện. 
2.4.1. Phương pháp tái thiết lập tài nguyên thực hiện 
2.4.1.1. Ý tưởng của phương pháp tái thiết lập 
Trong bài toán MS-RCPSP, một lịch biểu là một cá thể biểu diễn tài nguyên 
thực hiện tác vụ thỏa mãn các ràng buộc ban đầu. Sau mỗi thế hệ, thuật toán sẽ 
tìm ra được lịch biểu tốt nhất (Cbest), dựa trên lịch biểu này, thực hiện tiếp thay 
đổi các tài nguyên thực hiện từng tác vụ sao cho vẫn đảm bảo được ràng buộc 
của bài toán. Việc thay đổi tài nguyên thực hiện tác vụ được gọi là phương pháp 
tái thiết lập (Reallocate). Phương pháp này giúp mở rộng được không gian tìm 
kiếm và có thể tránh được cực trị địa phương. 
Phương pháp tái thiết lập được thực hiện qua các bước như sau: 
- Bước 1: Tìm tài nguyên sử dụng nhiều nhất trong Cbest, gọi là Lb. Đây là tài 
nguyên kết thúc công việc sau cùng trong các tài nguyên sử dụng để thực 
hiện dự án. 
- Bước 2: Duyệt lần lượt từng tác vụ được thực hiện bởi tài nguyên Lb theo 
thứ tự ưu tiên thực hiện của các tác vụ trên lịch biểu. 
WRb: tập tác vụ đang được thực hiện bởi Lb 
- Bước 3: Với mỗi tác vụ Wi ∈ WRb (i=1- sizeof(WRb)), thực hiện: 
65 
• Tìm tất cả các tài nguyên có khả năng thực hiện được tác vụ Wi khác với 
tài nguyên hiện tại (Lb), ký hiệu là LW; 
• Duyệt lần lượt từng tài nguyên có thể thực hiện tác vụ Wi, với mỗi tài 
nguyên Lj
W ∈ LW, thực hiện: 
o (1) Thiết lập tài nguyên thực hiện Wi là RjW; 
o (2) Xóa Wi khỏi danh sách tác vụ mà là Lb đang thực hiện. 
Sau (1) và (2) ta sẽ nhận được lịch biểu mới, tính makespan của lịch biểu 
mới newbest, nếu tốt hơn makespan của Cbest, thay thế Cbest bằng lịch newbest và 
dừng lại, nếu không, tiếp tục thực hiện vòng lặp để kiểm tra. 
𝐶𝑏𝑒𝑠𝑡 {
 𝑛𝑒𝑤𝑏𝑒𝑠𝑡 𝑖𝑓 𝑓(𝑛𝑒𝑤𝑏𝑒𝑠𝑡) < 𝑓(𝐶𝑏𝑒𝑠𝑡)
𝐶𝑏𝑒𝑠𝑡 𝑖𝑓 𝑓(𝑛𝑒𝑤𝑏𝑒𝑠𝑡) ≥ 𝑓(𝐶𝑏𝑒𝑠𝑡) 
Phép dịch chuyển này giúp thuật toán mở rộng không gian tìm kiếm bằng 
việc tạo ra các cá thể mới dựa trên cá thể tốt nhất. Do cá thể newbest được tạo ra 
từ cá thể tốt nhất nên có khả năng sử dụng được kinh nghiệm của cả quần thể 
và của cá thể tốt nhất qua các thế hệ, đây chính là đặc tính của thuật toán DE. 
Do vậy, sau khi áp dụng Reallocate, chúng ta có thể nhận được các cá thể tốt 
hơn. 
2.4.1.2. Sơ đồ thuật toán 
Các bước thực hiện của phương pháp tái thiết lập được thể hiện chi tiết 
trong sơ đồ thuật toán hình 2.7. 
2.4.1.3. Hàm Reallocate 
Thuật toán tái thiết lập tài nguyên [CT7], [CT8] thực hiện tác vụ được thể 
hiện chi tiết trong Algorithm 2.2 sau đây. 
Algorithm 2.2. Reallocate 
Input: currentBest (các thể tốt nhất sau mỗi thế hệ) 
Output: lịch biểu sau khi được hiệu chỉnh 
66 
1. makespan = f(currentBest) 
2. newbest = currentBest; 
3. Lb = lastResource (newbest) //tài nguyên hoàn thành sau 
cùng 
4. Wb = {các tác vụ được thực hiện bởi Lb} 
5. For i=1 to size(Wb) // duyệt lần lượt từng tác vụ 
6. Wi = Wb[i]; // lấy tác vụ thứ i 
7. Li = {các tài nguyên thực hiện được Wi # Lb} 
8. For j = 1 to size(Li) // duyệt lần lượt từng tài nguyên 
9. Li[j] = Li[j] + {Wi} // chuyển ti sang Li[j] 
10. Lb = Lb – {Wi} // loại Wi khỏi Lb 
11. newmakespan = f(newbest) // t