BỘ QUỐC PHÒNG | |
VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ |
Có thể bạn quan tâm!
-
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 - 2 -
Giải Bài Toán Real-Rcpsp Bằng Phương Pháp Tiến Hóa Vi Phân Và Phương Pháp Cuckoo Search -
Một Số Ứng Dụng Thực Tế Của Bài Toán Ms-Rcpsp
Xem toàn bộ 156 trang tài liệu này.
ĐẶNG QUỐC HỮU
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
Chuyên ngành: Cơ sở toán học cho tin học Mã số: 9 46 01 10
LUẬN ÁN TIẾN SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
1. TS. Nguyễn Thế Lộc
2. TS. Nguyễn Doãn Cường
Hà Nội - 2021
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nghiên cứu được trình bày trong luận án là hoàn toàn trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác, các dữ liệu tham khảo được trích dẫn đầy đủ.
Hà Nội, ngày tháng 08 năm 2021
Nghiên cứu sinh
Đặng Quốc Hữu
LỜI CẢM ƠN
Luận án này được hoàn thành tại Viện Công nghệ thông tin - Viện Khoa học và Công nghệ quân sự và Trường Đại học Thương mại.
Lời đầu tiên, nghiên cứu sinh bày tỏ lòng biết ơn sâu sắc tới tập thể giáo viên hướng dẫn: TS. Nguyễn Thế Lộc và TS. Nguyễn Doãn Cường đã trực tiếp giảng dạy và tận tình hướng dẫn, định hướng cho nghiên cứu sinh trong suốt quá trình thực hiện luận án này.
Nghiên cứu sinh trân trọng gửi lời cảm ơn tới Thủ trưởng Viện Khoa học và Công nghệ quân sự, Phòng Đào tạo - Viện Khoa học và Công nghệ quân sự, Viện Công nghệ thông tin đã giúp đỡ tôi trong suốt thời gian học tập, nghiên cứu, thực hiện luận án. Cảm ơn các thầy cô tại Viện Khoa học và Công nghệ quân sự, Đại học Quốc gia Hà Nội, Đại học Sư phạm Hà Nội,... đã nhiệt tình hướng dẫn, giúp đỡ tôi hoàn thành các nội dung của chương trình tiến sĩ và đóng góp cho tôi những ý kiến quý báu về mặt nội dung khoa học và bố cục của luận án.
Tôi xin trân trọng cảm ơn các thầy cô, các nhà khoa học, đồng nghiệp trong và ngoài Viện đã đọc, nhận xét luận án, đóng góp những ý kiến quý báu để nghiên cứu sinh hoàn thiện luận án này.
Trân trọng cảm ơn Ban Giám hiệu trường Đại học Thương mại, các đồng nghiệp và gia đình đã động viên, chia sẻ và tạo điều kiện cho tôi trong suốt thời gian làm nghiên cứu sinh.
Nghiên cứu sinh
Đặng Quốc Hữu
MỤC LỤC
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT v
DANH MỤC CÁC BẢNG vii
DANH MỤC CÁC HÌNH VẼ ix
MỞ ĐẦU 1
CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN MS-RCPSP 8
1.1. Bài toán MS-RCPSP 9
1.1.1. Mô tả bài toán 9
1.1.2. Một số ứng dụng thực tế của bài toán MS-RCPSP 15
1.1.3. Những nghiên cứu liên quan 19
1.2. Một số thuật toán metaheuristic tìm nghiệm gần đúng 24
1.2.1. Thuật toán PSO 25
1.2.2. Thuật toán PSO kết hợp với tìm kiếm lân cận 27
1.2.3. Thuật toán DE 31
1.2.4. Thuật toán Cuckoo Search 33
Kết luận chương 1 42
CHƯƠNG 2: GIẢI BÀI TOÁN MS-RCPSP BẰNG PHƯƠNG PHÁP TỐI ƯU BẦY ĐÀN VÀ PHƯƠNG PHÁP TIẾN HÓA VI PHÂN 43
2.1. Phương pháp biểu diễn cá thể 44
2.2. Thang đo độ chênh của cá thể 45
2.3. Đề xuất thuật toán M-PSO 50
2.3.1. Kỹ thuật Di cư 51
2.3.2. Thuật toán M-PSO 54
2.3.3. Thực nghiệm 56
2.3.4. Đánh giá chất lượng lời giải của thuật toán 61
2.3.5. Hình ảnh so sánh M-PSO và GA-M 63
2.4. Đề xuất thuật toán DEM 64
2.4.1. Phương pháp tái thiết lập tài nguyên thực hiện 64
2.4.2. Thuật toán 70
2.4.3. Kết quả thực nghiệm 70
2.4.4. Đánh giá chất lượng lời giải của thuật toán 74
2.4.5. Hình ảnh so sánh DEM với thuật toán GA-M 77
Kết luận chương 2 79
CHƯƠNG 3: BÀI TOÁN REAL-RCPSP 80
3.1. Bài toán Real-RCPSP 80
3.1.1. Phát biểu bài toán 81
3.1.2. Những ứng dụng thực tế của bài toán Real-RCPSP 82
3.2. Xếp loại bài toán Real-RCPSP thông qua phân loại Graham 83
Kết luận chương 3 88
CHƯƠNG 4: GIẢI BÀI TOÁN REAL-RCPSP BẰNG PHƯƠNG PHÁP TIẾN HÓA VI PHÂN VÀ PHƯƠNG PHÁP CUCKOO SEARCH 89
4.1. Phương pháp biểu diễn cá thể 90
4.2. Đề xuất thuật toán A-DEM 92
4.2.1. Phương pháp thích nghi 93
4.2.2. Thuật toán A-DEM 97
4.2.3. Thực nghiệm 99
4.2.4. Đánh giá chất lượng lời giải của thuật toán 104
4.2.5. Hình ảnh so sánh A-DEM và GA-M 105
4.3. Đề xuất thuật toán R-CSM 106
4.3.1. Thuật toán 107
4.3.2. Kết quả thực nghiệm 109
4.3.3. Đánh giá chất lượng lời giải của thuật toán 110
4.3.4. Hình ảnh so sánh R-CSM với thuật toán GA-M 111
4.4. Đề xuất thuật toán RR-CSM 112
4.4.1. Phương pháp Rotate 113
4.4.2. Thuật toán 117
4.4.3. Kết quả thực nghiệm 119
4.4.4. Đánh giá chất lượng lời giải của thuật toán 120
4.4.5. Hình ảnh so sánh RR-CSM với thuật toán GA-M 122
Kết luận chương 4 124
KẾT LUẬN 125
DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ 127
TÀI LIỆU THAM KHẢO 129
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT
Tập tác vụ (task) cần thực hiện trước tác vụ i | |
L | Tập các tài nguyên; |
Li | Tập tài nguyên có thể thực hiện tác vụ i, LiL |
Li | Tài nguyên thứ i |
P | Một lịch biểu khả thi của bài toán; |
Pall | Tập tất cả các lịch biểu |
S | Tập tất các các kỹ năng của các tài nguyên; |
Si | Tập các kỹ năng của tài nguyên i, SiS |
W | Tập các tác vụ của dự án |
Wi | Tập các tác vụ có thể thực hiện bởi tài nguyên i, WiW |
Wi | Tác vụ thứ i |
Algorithm | Thuật toán, mô tả bằng mã giả của một thuật toán |
A-DEM | Thuật toán mới A-DEM (Adaptive DEM) |
AVG | Giá trị trung bình (Average) |
BEST | Giá trị tốt nhất (BEST) |
CR | Xác suất lai ghép (Crossover Probability ) |
CS | Thuật toán Cuckoo Search (Cuckoo Search) |
CSM | Thuật toán CS áp dụng giải bài toán MS-RCPSP (CS for MS-RCPSP) |
DE | Thuật toán tiến hóa vi phân (Differential Evolution) |
DEM | Thuật toán đề xuất DEM áp dụng giải bài toán MS-RCPSP (DE for MS-RCPSP) |
Fitness | Giá trị tốt nhất của một cá thể trong quần thể từ thế hệ đầu tiên cho đến thế hệ hiện tại. |
GA | Thuật toán di truyền (Genetic Algorithms) |
GRASP | Thuật toán lai giữa Greedy và Adative(Greedy Randomized |
Adaptive Search Procedure) | |
GreedyDO | Thuật toán tham lam nhằm tối ưu thời gian thực hiện (Greedy algorithm for Duration Optimization) |
GS | Kỹ thuật tìm kiếm toàn cục (Global Search) |
HAntCO | Thuật toán tối ưu đàn kiến lai (Hybrid Ant Colony Optimization) |
iMOPSE | Bộ dữ liệu chuẩn iMOPSE (iMOPSE dataset) |
LS | Kỹ thuật tìm kiếm cục bộ (Local Search) |
Makespan | Thời gian tối thiểu để hoàn thành dự án |
M-PSO | Thuật toán đề xuất M-PSO (Migration PSO) |
MS-RCPSP | Bài toán lập lịch với tài nguyên giới hạn và đa kỹ năng (Multi skill - RCPSP) |
PSO | Thuật toán tối ưu bầy đàn (Particle Swarm Optimization) |
RCPSP | Bài toán lập lịch thực hiện dự án với tài nguyên giới hạn - sau này viết gọn là: bài toán lập lịch với tài nguyên giới hạn (Resource-Constrained Project Scheduling Problem) |
Real-RCPSP | Bài toán mới Real-RCPSP (Real-RCPSP Problem) |
R-CSM | Thuật toán đề xuất R-CSM (Reallocate CSM) |
RR-CSM | Thuật toán đề xuất RR-CSM (Rotate and Reallocate CSM) |
STD | Độ lệch chuẩn (Standard Deviation) |
TNG | Công ty cổ phần đầu tư và thương mại TNG |
DANH MỤC CÁC BẢNG
Trang
Bảng 1.1: Thông tin đầu vào của dự án 11
Bảng 1.2: Dữ liệu về tác vụ và yêu cầu thực hiện 18
Bảng 1.3: Tổng hợp các nghiên cứu về bài toán MS-RCPSP 24
Bảng 2.1: Thời gian thực hiện các tác vụ 44
Bảng 2.2: Thang đo tài nguyên thực hiện tác vụ 46
Bảng 2.3: Tài nguyên có thể thực hiện tác vụ 48
Bảng 2.4: Giá trị vector thang đo 48
Bảng 2.5: Tài nguyên thực hiện tác vụ của cá thể S1, S2 48
Bảng 2.6: Giá trị của vector độ chênh d 48
Bảng 2.7: Kết quả cộng hai cá thể 50
Bảng 2.8: Năng lực của các tài nguyên 53
Bảng 2.9: Lịch biểu khả thi của dự án trong ví dụ 2.2 53
Bảng 2.10: Lịch biểu mới sau khi di cư 53
Bảng 2.11: Bộ dữ liệu iMOPSE cho bài toán MS-RCPSP 56
Bảng 2.12: Kết quả thực nghiệm M-PSO 59
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 61
Bảng 2.14: Thời gian thực hiện các tác vụ 68
Bảng 2.15: Năng lực các tài nguyên 68
Bảng 2.16: Tài nguyên thực hiện tác vụ 69
Bảng 2.17: Kết quả thực nghiệm DEM với bộ dữ liệu iMOPSE 71
Bảng 2.18: So sánh kết quả thực nghiệm DEM với các thuật toán 73
Bảng 2.19: So sánh kết quả thực nghiệm DEM với M-PSO 73
Bảng 4.1: Thời gian chuẩn thực hiện các tác vụ 90
Bảng 4.2: Năng lực tài nguyên của dự án 90
Bảng 4.3: Yêu cầu tài nguyên thực hiện tác vụ và thời gian thực hiện 91
Bảng 4.4: Thời gian thực hiện các tác vụ 92
Bảng 4.5: Các hợp đồng may công nghiệp 102
Bảng 4.6: Dữ liệu chuyền may của TNG 102