Đánh Giá Chất Lượng Lời Giải Của Thuật Toán 26898

Bảng 4.5: Các hợp đồng may công nghiệp

STT

Mã hợp đồng

Loại sản

phẩm

Số sản

phẩm

Số công

đoạn

WE1190/1698402 Liner Buy

Mar 14-F19

Áo nỷ

33,693

FM4013/ 1536181 buy Nov

08- F19

Quần bơi

83,340

137

Có thể bạn quan tâm!

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

Bộ dữ liệu

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

Dataset

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

Dataset

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

Dataset

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

Dataset

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(tmax)

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

21. return {bestnest, makespan}
22. End

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

Dataset

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