Bảng 4.5: Các hợp đồng may công nghiệp
Mã hợp đồng | Loại sản phẩm | Số sản phẩm | Số công đoạn | |
1 | WE1190/1698402 Liner Buy Mar 14-F19 | Áo nỷ | 33,693 | 71 |
2 | FM4013/ 1536181 buy Nov 08- F19 | Quần bơi | 83,340 | 137 |
Có thể bạn quan tâm!
- Xếp Loại Bài Toán Real-Rcpsp Thông Qua Phân Loại Graham
- 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 - 13
- Ý Tưởng Của Phương Pháp Thích Nghi
- Đánh Giá Chất Lượng Lời Giải Của Thuật Toán
- Đánh Giá Chất Lượng Lời Giải Của Thuật Toá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 - 18
Xem toàn bộ 156 trang tài liệu này.
Bảng 4.6: Dữ liệu chuyền may của TNG
Số tác vụ | Số công nhân | Số ràng buộc ưu tiên | Số mức kỹ năng | Thời gian thực hiện (PT) | |
TNG1 | 71 | 37 | 1026 | 6 | 409 |
TNG2 | 71 | 39 | 1026 | 6 | 325 |
TNG3 | 71 | 41 | 1026 | 6 | 296 |
TNG4 | 71 | 45 | 1026 | 6 | 392 |
TNG5 | 137 | 37 | 1894 | 6 | 1174 |
TNG6 | 137 | 39 | 1894 | 6 | 1052 |
TNG7 | 137 | 41 | 1894 | 6 | 871 |
TNG8 | 137 | 45 | 1894 | 6 | 996 |
Trong bảng 4.6, cột “Thời gian thực hiện (PT)” là tổng thời gian thực hiện hợp đồng thực tế tương ứng với từng tổ may, tính theo giờ.
4.2.3.2. Kết quả thực nghiệm
Thuật toán A-DEM thực nghiệm với 2 bộ dữ liệu, bộ dữ liệu iMOPSE (bảng 2.11) hiệu chỉnh và bộ dữ liệu TNG (bảng 4.6). Các tham số thực nghiệm và cài đặt được thiết lập tương tự như mục 2.3.3.2.
Kết quả thực nghiệm thuật toán A-DEM với mô hình bài toán Real-RCPSP chạy trên bộ dữ liệu iMOPSE được trình bày trong bảng 4.7; với bộ dữ liệu TNG trong bảng 4.8.
Bảng 4.7: Kết quả thực nghiệm A-DEM trên bộ dữ liệu iMOPSE
GA-M | A-DEM | |||||
Best | Avg | Std | Best | Avg | Std | |
100_5_22_15 | 465 | 469 | 3.1 | 452 | 454 | 1.1 |
100_5_46_15 | 523 | 529 | 5.4 | 505 | 506 | 0.2 |
GA-M | A-DEM | |||||
Best | Avg | Std | Best | Avg | Std | |
100_5_48_9 | 476 | 481 | 4.5 | 467 | 471 | 3.7 |
100_5_64_15 | 478 | 487 | 8.2 | 456 | 461 | 4.7 |
100_5_64_9 | 453 | 457 | 3.2 | 429 | 430 | 0.7 |
100_10_26_15 | 221 | 224 | 2.1 | 204 | 208 | 3.8 |
100_10_47_9 | 247 | 253 | 5.9 | 236 | 238 | 1.2 |
100_10_48_15 | 238 | 246 | 7.6 | 234 | 237 | 2.7 |
100_10_64_9 | 239 | 249 | 9.4 | 216 | 222 | 5.8 |
100_10_65_15 | 240 | 244 | 3.2 | 227 | 230 | 2.7 |
100_20_22_15 | 109 | 115 | 5.2 | 91 | 95 | 3.8 |
100_20_46_15 | 145 | 150 | 4.1 | 143 | 147 | 3.2 |
100_20_47_9 | 121 | 125 | 3.3 | 117 | 119 | 1.9 |
100_20_65_15 | 193 | 200 | 6.8 | 183 | 185 | 1.8 |
100_20_65_9 | 124 | 131 | 6.5 | 100 | 101 | 0.3 |
200_10_128_15 | 440 | 446 | 5.7 | 421 | 422 | 0.6 |
200_10_50_15 | 468 | 471 | 2.9 | 463 | 466 | 2.3 |
200_10_50_9 | 481 | 484 | 2.6 | 454 | 459 | 4.3 |
200_10_84_9 | 487 | 498 | 10.9 | 479 | 484 | 4.8 |
200_10_85_15 | 465 | 469 | 4.0 | 453 | 456 | 2.7 |
200_20_145_15 | 222 | 229 | 6.1 | 170 | 175 | 4.1 |
200_20_54_15 | 249 | 255 | 5.1 | 234 | 237 | 2.2 |
200_20_55_9 | 248 | 254 | 5.7 | 227 | 228 | 0.8 |
200_20_97_15 | 317 | 321 | 3.3 | 283 | 288 | 4.8 |
200_20_97_9 | 234 | 241 | 6.2 | 228 | 232 | 3.9 |
200_40_133_15 | 126 | 134 | 7.4 | 106 | 110 | 3.6 |
200_40_45_15 | 160 | 164 | 3.8 | 122 | 123 | 0.3 |
200_40_45_9 | 133 | 146 | 12.1 | 117 | 121 | 3.4 |
200_40_90_9 | 130 | 133 | 3.0 | 107 | 112 | 4.9 |
200_40_91_15 | 133 | 139 | 5.8 | 114 | 117 | 2.0 |
Bảng 4.8: Kết quả thực nghiệm A-DEM với bộ dữ liệu TNG
GA-M | A-DEM | |||||
Avg | Best | Std | Avg | Best | Std | |
TNG1 | 203 | 201 | 3.5 | 138 | 135 | 2.7 |
TNG2 | 205 | 198 | 8.3 | 141 | 137 | 3.8 |
TNG3 | 218 | 212 | 7.1 | 138 | 134 | 3.4 |
TNG4 | 187 | 176 | 11.3 | 138 | 129 | 8.3 |
TNG5 | 757 | 751 | 6.2 | 580 | 570 | 9.5 |
GA-M | A-DEM | |||||
Avg | Best | Std | Avg | Best | Std | |
TNG6 | 796 | 791 | 5.5 | 629 | 621 | 7.3 |
TNG7 | 820 | 810 | 10.7 | 577 | 571 | 5.2 |
TNG8 | 728 | 720 | 9.4 | 564 | 557 | 6.6 |
4.2.4. Đánh giá chất lượng lời giải của thuật toán
Các thực nghiệm được triển khai trên 02 thuật toán GA-M và A-DEM, mỗi thuật toán thực hiện trên bộ dữ liệu iMOPSE và bộ dữ liệu TNG. Luận án đã tiến hành thực nghiệm các thuật toán một cách độc lập với 50 lần chạy, cài đặt trên môi trường thử nghiệm là Matlab 2014. Kết quả thực nghiệm được trình bày trong bảng 4.7 và bảng 4.8 chỉ ra thuật toán A-DEM có chất lượng lời giải tốt hơn thuật toán GA-M trong mọi trường hợp.
Với bộ dữ liệu iMOPSE, giá trị tốt nhất của A-DEM tốt hơn GA-M từ 0,52% đến 18,80. So sánh chi tiết được thể hiện trong hình 4.4. Tổng độ lệch chuẩn của GA-M là 163,1, của A-DEM là 84,2, điều này cho thấy độ ổn định của thuật toán A-DEM tốt hơn, hình 4.5 cho so sánh độ lệch chuẩn giữa A- DEM và GA-M.
Với bộ dữ liệu TNG, giá trị tốt nhất của A-DEM tốt hơn GA-M từ 5,2% đến 21,7%, so sánh chi tiết được thể hiện trong hình 4.6. Tổng độ lệch chuẩn của GA-M là 62, của DEM là 46,8, điều này cho thấy độ ổn định của thuật toán A-DEM tốt hơn, hình 4.7 so sánh độ lệch chuẩn giữa A-DEM và GA-M. Từ kết quả thực nghiệm với bộ dữ liệu TNG cho thấy, nếu tài nguyên có số mức kỹ năng càng lớn, khả năng chênh lệch giữa mức kỹ năng yêu cầu và mức kỹ năng của tài nguyên thực hiện càng cao, do vậy tổng thời gian thực hiện dự án sẽ giảm nhiều hơn.
105
4.2.5. Hình ảnh so sánh A-DEM và GA-M
Hình 4.4. So sánh giá trị BEST giữa A-DEM với GA-M trên iMOPSE
Hình 4.5. So sánh giá trị STD giữa A-DEM với GA-M trên iMOPSE
Hình 4.6. So sánh giá trị BEST giữa A-DEM và GA-M và TNG
Hình 4.7. So sánh giá trị STD giữa A-DEM với GA-M trên bộ dữ liệu TNG
4.3. Đề xuất thuật toán R-CSM
Thuật toán R-CSM (Reallocate Cuckoo Search for MS-RCPSP) được cải tiến dựa trên thuật toán CS [CT5] để giải bài toán Real-RCPSP [CT9] với mục tiêu là tìm ra lịch biểu có thời gian thực hiện ngắn nhất để điều phối quá trình sản xuất trong thực tế. R-CSM có cải tiến quan trọng là sử dụng hàm Reallocate() [CT9] để tái thiết lập tài nguyên thực hiện tác vụ cho cá thể tốt nhất sau mỗi thế hệ.
4.3.1. Thuật toán
R-CSM sử dụng phương pháp tái thiết lập tài nguyên (đã trình bày chi tiết trong mục 2.4.1) để cải thiện chất lượng lời giải. R-CSM dịch chuyển quần thể bằng bước dịch chuyển Lévy Flight với kỹ thuật Tìm kiếm cục bộ (Local Search) và Tìm kiếm toàn cục (Global Search) giúp mở rộng không gian tìm kiếm đồng thời thoát khỏi bẫy cực trị địa phương.
R-CSM thực hiện qua các bước như sau:
- Bước 1: Khởi tạo quần thể với n cá thể: Pall
- Bước 2: Tính toán các giá trị trong quần thể: cá thể tốt nhất bestnest, giá trị tốt nhất của mỗi cá thể trong quần thể qua các thế hệ (fitness), …
- Bước 3: Thực hiện các tiến hóa qua các thế hệ
- Bước 4: Với mỗi thế hệ, thực hiện
- Bước 4.1: Tạo ra 01 cá thể mới bằng kỹ thuật GS, cá thể mới là: Pnew
- Bước 4.2: Chọn Pi ngẫu nhiên từ quần thể
𝑃𝑖
= { 𝑃𝑛𝑒𝑤 𝑖𝑓 𝑓(𝑃𝑛𝑒𝑤) < 𝑓(𝑃𝑖)
𝑃𝑖 𝑖𝑓 𝑓(𝑃𝑛𝑒𝑤) ≥ 𝑓(𝑃𝑖)
- Bước 4.3: Tính toán các giá trị trong quần thể: bestnest, fitness, …
- Bước 4.4: Thay thế pa% cá thể kém nhất bằng các cá thể mới được tạo ra bởi kỹ thuật Local Search.
- Bước 4.5: Áp dụng hàm Reallocate() (trình bày ở mục 2.4.1) đối với cá thể tốt nhất (bestnest)
- Bước 5: Lặp lại từ bước 2 cho đến khi kết thúc
Cải tiến chính của thuật R-CSM toán nằm trong bước 4.5 khi áp dụng các phương pháp Reallocate với cá thể tốt nhất.
Thuật toán R-CSM được trình bày trong Algorithm 4.3 dưới đây.
Algorithm 4.3. Thuật toán R-CSM
Input : dataset
tmax : số thế hệ tiến hóa Output : cá thể tốt nhất và makespan
1. Begin
2. Load and Valid dataset 3. t 0
4. Pall Initial population
5. f Calculate the fitness, makespan, bestnest
6. while(t
7. Pnew Tạo cá thể mới bằng Lévy Flight (GS)
8. Pi Lấy ngẫu nhiên một cá thể từ Pall
9. 𝑃𝑖
= { 𝑃𝑛𝑒𝑤 𝑖𝑓 𝑓(𝑃𝑛𝑒𝑤) < 𝑓(𝑃𝑖)
𝑃𝑖 𝑖𝑓 𝑓(𝑃𝑛𝑒𝑤) ≥ 𝑓(𝑃𝑖 )
10. Ppa pa% tổ kém nhất từ Pall
11. For j = 1 to size(Ppa)
12. Pnew Tạo cá thể mới bằng Lévy Flight (LS)
𝑃𝑛𝑒𝑤 𝑖𝑓 𝑓(𝑃𝑛𝑒𝑤) < 𝑓(𝑃𝑝𝑎)
13. 𝑃𝑝𝑎 = { 𝑗
𝑗 𝑃𝑝𝑎 𝑖𝑓 𝑓(𝑃𝑛𝑒𝑤) ≥ 𝑓(𝑃𝑝𝑎)
𝑗 𝑗
14. End For
15. Pall Thay thế Ppa vào Pall
16. f Calculate the fitness, makespan, bestnest
17. bestnest = Reallocate(bestnest)
18. makespan = f(bestnest)
19. t = t+1
20. End while
Với: - f: hàm tính makespan của một lịch biểu |
Các dòng 17 là các lời gọi đến hàm Reallocate để cải tiến kết quả của cá thể tốt nhất bestnest, sau đó sẽ tính toán lại makespan của cả quần thể bằng lời gọi ở dòng 18.
4.3.2. Kết quả thực nghiệm
Để kiểm chứng thuật toán R-CSM, luận án tiến hành thực nghiệm trên 02 bộ dữ liệu: iMOPSE (bảng 2.11) hiệu chỉnh và bộ dữ liệu của TNG[54] (bảng 4.6). Các thông số cấu hình thực nghiệm tương tự như trong mục 2.3.3.2. Kết quả thực nghiệm được trình bày trong bảng 4.9 và bảng 4.10 dưới đây.
Bảng 4.9: Kết quả thực nghiệm R-CSM với bộ dữ liệu iMOPSE
GA-M | R-CSM | |||||
Best | Avg | Std | Best | Avg | Std | |
100_5_22_15 | 465 | 469 | 3.1 | 454 | 455 | 1.0 |
100_5_46_15 | 523 | 529 | 5.4 | 506 | 509 | 2.1 |
100_5_48_9 | 476 | 481 | 4.5 | 471 | 473 | 1.5 |
100_5_64_15 | 478 | 487 | 8.2 | 461 | 464 | 2.3 |
100_5_64_9 | 453 | 457 | 3.2 | 430 | 432 | 1.4 |
100_10_26_15 | 221 | 224 | 2.1 | 208 | 210 | 1.3 |
100_10_47_9 | 247 | 253 | 5.9 | 238 | 240 | 1.6 |
100_10_48_15 | 238 | 246 | 7.6 | 237 | 238 | 0.1 |
100_10_64_9 | 239 | 249 | 9.4 | 222 | 225 | 2.1 |
100_10_65_15 | 240 | 244 | 3.2 | 230 | 232 | 1.8 |
100_20_22_15 | 109 | 115 | 5.2 | 95 | 101 | 5.2 |
100_20_46_15 | 145 | 150 | 4.1 | 144 | 152 | 7.8 |
100_20_47_9 | 121 | 125 | 3.3 | 119 | 126 | 6.1 |
100_20_65_15 | 193 | 200 | 6.8 | 185 | 189 | 3.6 |
100_20_65_9 | 124 | 131 | 6.5 | 101 | 110 | 8.9 |
200_10_128_15 | 440 | 446 | 5.7 | 422 | 428 | 5.1 |
200_10_50_15 | 468 | 471 | 2.9 | 466 | 467 | 0.9 |
200_10_50_9 | 481 | 484 | 2.6 | 459 | 461 | 1.2 |
200_10_84_9 | 487 | 498 | 10.9 | 484 | 485 | 0.4 |
200_10_85_15 | 465 | 469 | 4.0 | 456 | 457 | 0.3 |
200_20_145_15 | 222 | 229 | 6.1 | 175 | 185 | 9.2 |
200_20_54_15 | 249 | 255 | 5.1 | 237 | 240 | 2.7 |
200_20_55_9 | 248 | 254 | 5.7 | 228 | 232 | 3.1 |
200_20_97_15 | 317 | 321 | 3.3 | 288 | 293 | 4.9 |
200_20_97_9 | 234 | 241 | 6.2 | 232 | 234 | 1.5 |
200_40_133_15 | 126 | 134 | 7.4 | 110 | 119 | 8.1 |
200_40_45_15 | 160 | 164 | 3.8 | 123 | 129 | 5.7 |
200_40_45_9 | 133 | 146 | 12.1 | 121 | 132 | 10.3 |