Mục tiêu của đề tài nhằm nghiên cứu, đề xuất các phương pháp gần đúng để giải bài toán MS-RCPSP nhằm cực tiểu hóa thời gian thực hiện dự án; đề xuất bài toán mới Real-RCPSP, là bài toán có khả năng ứng dụng cao trong việc lập kế hoạch điều phối sản xuất đặc biệt là các dây chuyền sản xuất sản phẩm; nghiên cứu và đề xuất thuật toán gần đúng để giải bài toán Real-RCPSP. Mời các bạn tham khảo nội dung đề tài!
Nội dung trích xuất từ tài liệu:
Luận án Tiến sĩ Toán học: 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 fơơn vị 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Ự ĐẶNG QUỐC HỮU MỘT SỐ PHƯƠNG PHÁP GẦN ĐÚNGGIẢI BÀI TOÁN LẬP LỊCH VỚI TÀI NGUYÊN GIỚI HẠN LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2021 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Ự ĐẶNG QUỐC HỮU MỘT SỐ PHƯƠNG PHÁP GẦN ĐÚNGGIẢ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 i 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ưatừ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 ii 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 Khoahọ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áoviên hướng dẫn: TS. Nguyễn Thế Lộc và TS. Nguyễn Doãn Cường đã trực tiếpgiảng dạy và tận tình hướng dẫn, định hướng cho nghiên cứu sinh trong suốtquá 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ọcvà 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êncứ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ìnhhướ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ụccủ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ệptrong 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 đồngnghiệp và gia đình đã động viên, chia sẻ và tạo điều kiện cho tôi trong suốt thờigian làm nghiên cứu sinh. Nghiên cứu sinh Đặng Quốc Hữu iii MỤC LỤCDANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT .......................................................vDANH MỤC CÁC BẢNG....................................................................................... viiDANH MỤC CÁC HÌNH VẼ....................................................................................ixMỞ ĐẦU .....................................................................................................................1CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN MS-RCPSP ........................................81.1. Bài toán MS-RCPSP ......................................................................................... 91.1.1. Mô tả bài toán ................................................................................................... 91.1.2. Một số ứng dụng thực tế của bài toán MS-RCPSP ......................................... 151.1.3. Những nghiên cứu liên quan ........................................................................... 191.2. Một số thuật toán metaheuristic tìm nghiệm gần đúng ................................... 241.2.1. Thuật toán PSO ............................................................................................... 251.2.2. Thuật toán PSO kết hợp với tìm kiếm lân cận ................................................ 271.2.3. Thuật toán DE ................................................................................................. 311.2.4. Thuật toán Cuckoo Search .............................................................................. 33Kết luận chương 1 .....................................................................................................42CHƯƠNG 2: GIẢI BÀI TOÁN MS-RCPSP BẰNG PHƯƠNG PHÁP TỐI ƯUBẦY ĐÀN VÀ PHƯƠNG PHÁP TIẾN HÓA VI PHÂN ........................................432.1. Phương pháp biểu diễn cá thể ......................................................................... 442.2. Thang đo độ chênh của cá thể ......................................................................... 452.3. Đề xuất thuật toán M-PSO .............................................................................. 502.3.1. Kỹ thuật Di cư ................................................................................................. 512.3.2. Thuật toán M-PSO .......................................................................................... 542.3.3. Thực nghiệm ................................................................................................... 562.3.4. Đánh giá chất lượng lời giải của thuật toán .................................................... 612.3.5. Hình ảnh so sánh M-PSO và GA-M ............................................................... 632.4. Đề xuất thuật toán DEM ........................ ...