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

BỘ GIÁO DỤC VÀ ĐÀO TẠO

BỘ QUỐC PHÒNG

VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ

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

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, LiL
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, SiS
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, WiW
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