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

Chia sẻ: Dopamine Grabbi | Ngày: | Loại File: PDF | Số trang:148

Thêm vào BST

Báo xấu

18
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 ĐÚNG GIẢ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 ĐÚ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
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ư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
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 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
iii 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
iv 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
v DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT Ci 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
vi 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
vii 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
viii Bảng 4.7: Kết quả thực nghiệm A-DEM trên bộ dữ liệu iMOPSE .............. 102 Bảng 4.8: Kết quả thực nghiệm A-DEM với bộ dữ liệu TNG...................... 103 Bảng 4.9: Kết quả thực nghiệm R-CSM với bộ dữ liệu iMOPSE ................ 109 Bảng 4.10: Kết quả thực nghiệm R-CSM với bộ dữ liệu TNG .................... 110 Bảng 4.11: Thời gian thực hiện các tác vụ.................................................... 113 Bảng 4.12: Kết quả thực nghiệm RR-CSM với bộ dữ liệu iMOPSE ........... 119 Bảng 4.13: Kết quả thực nghiệm RR-CSM với bộ dữ liệu TNG.................. 120
ix DANH MỤC CÁC HÌNH VẼ Trang Hình 1.1. Đồ thị ưu tiên thực hiện các tác vụ. ................................................ 11 Hình 1.2. Biểu đồ Gantt về thực hiện các tác vụ theo thời gian ..................... 12 Hình 1.3. Ma trận quan hệ giữa tác vụ và kỹ năng của tài nguyên ................. 15 Hình 1.4. Biểu đồ Gantt mô tả một phương án lịch biểu. ............................... 18 Hình 1.5. Sơ đồ bay của 2 chiếc UAV ............................................................ 19 Hình 1.6. Sơ đồ di chuyển của một cá thể i trong PSO .................................. 26 Hình 1.7. Kiểu lân cận Ring (a) và Von Neumann (b) ................................... 28 Hình 1.8. Hàm RotateRight (a) và hàm Exchange (b) .................................... 30 Hình 1.9. Chuyển động Brown của 5 hạt phấn hoa ........................................ 35 Hình 1.10. Chuyển động Brown của 3 hạt keo ............................................... 35 Hình 1.11. Đồ thị hàm mật độ xác suất của phân phối Lévy .......................... 37 Hình 1.12. 1000 bước dịch chuyển Lévy flight và chuyển động Brown ........ 38 Hình 2.1. Đồ thị ưu tiên các tác vụ trong dự án .............................................. 44 Hình 2.2. Tài nguyên thực hiện tác vụ theo thời gian ..................................... 45 Hình 2.3. Biểu diễn giá trị trên thang đo......................................................... 47 Hình 2.4. Thay đổi tài nguyên thực hiện tác vụ .............................................. 52 Hình 2.5. So sánh giá trị BEST giữa M-PSO và GA-M ................................ 63 Hình 2.6. So sánh giá trị STD giữa M-PSO và GA-M .................................. 63 Hình 2.7. Sơ đồ khối thực hiện di chuyển tác vụ sang tài nguyên khác ......... 67 Hình 2.8. Thứ tự ưu tiên của các tác vụ .......................................................... 68 Hình 2.9. Biểu đồ Gantt của lịch biểu 2.15 ..................................................... 69 Hình 2.10. Biểu đồ Gantt của lịch biểu mới ................................................... 69 Hình 2.11. Minh họa phương pháp tái thiết lập tài nguyên ............................ 69 Hình 2.12. So sánh giá trị BEST giữa DEM với GA-M ................................ 77 Hình 2.13. So sánh giá trị STD giữa DEM với GA-M ................................... 77 Hình 2.14. So sánh giá trị AVG giữa DEM với GA-M .................................. 78 Hình 3.1. Các kiểu thứ tự thực hiện tác vụ ..................................................... 86
x Hình 4.1. Biểu đồ Gantt của lịch biểu trong ví dụ 4.1 .................................... 92 Hình 4.2. Kiến trúc hình sao ........................................................................... 93 Hình 4.3. Tìm các cá thể lân cận ..................................................................... 94 Hình 4.4. So sánh giá trị BEST giữa A-DEM với GA-M trên iMOPSE ...... 105 Hình 4.5. So sánh giá trị STD giữa A-DEM với GA-M trên iMOPSE ........ 105 Hình 4.6. So sánh giá trị BEST giữa A-DEM và GA-M và TNG ................ 106 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 ................................................................................................ 106 Hình 4.8. So sánh giá trị BEST giữa R-CSM với GA-M trên iMOPSE ...... 111 Hình 4.9. So sánh giá trị STD giữa R-CSM với GA-M trên iMOPSE ......... 111 Hình 4.10. So sánh giá trị BEST giữa R-CSM, GA-M và TNG trên .......... 112 Hình 4.11. So sánh giá trị STD giữa R-CSM với GA-M.............................. 112 Hình 4.12. Đồ thị ưu tiên của dự án 1 ........................................................... 113 Hình 4.13. Đồ thị ưu tiên của dự án 2 ........................................................... 113 Hình 4.14. Các tài nguyên sử dụng liên tục (a) và có thời gian trống (b) .... 114 Hình 4.15. Biểu đồ Gantt khi áp dụng phương pháp Rotate......................... 116 Hình 4.16. So sánh giá trị BEST giữa R-CSM, RR-CSM, GA-M ............... 122 Hình 4.17. So sánh giá trị STD giữa R-CSM, RR-CSM, GA-M trên iMOPSE .......................................................................................... 122 Hình 4.18. So sánh giá trị BEST giữa R-CSM, RR-CSM và TNG ............. 123 Hình 4.19. So sánh giá trị STD giữa RR-CSM với R-CSM ......................... 123
1 MỞ ĐẦU 1. Tính cấp thiết của đề tài luận án Cách mạng công nghiệp 4.0 đang diễn ra mạnh mẽ trên toàn thế giới với nền tảng là các hệ thống điều khiển và tự động hóa thông minh cho phép các thiết bị giao tiếp với nhau và với con người. Internet vạn vật (IoT) mang lại khả năng kết nối nhiều thiết bị tạo thành hệ thống thông minh đồng thời làm bùng nổ lượng dữ liệu trên các mạng truyền thông, trong khi đó các tài nguyên phục vụ kết nối, truyền thông lại là hữu hạn. Do vậy, cần có các phương án lập lịch phân phối, cấp phát tài nguyên cũng như quản lý các dự án công việc sao cho hiệu quả. Trong thực tế, việc lập lịch trong các dự án hoặc các dây chuyền sản xuất luôn bị ràng buộc bởi những điều kiện như thời gian hoàn thành dự án, tài nguyên cần thiết để thực hiện dự án... nên cần có các phương án lập lịch điều phối một cách hiệu quả, gắn liền với thực tế. Bài toán RCPSP (Resource-Constrained Project Scheduling Problem) là bài toán giải quyết các vấn đề về lập lịch dự án với tài nguyên giới hạn bởi một số ràng buộc hoặc điều kiện nhất định. MS-RCPSP (Multi Skill - RCPSP) là bài toán mở rộng từ bài toán gốc RCPSP sau khi được bổ sung thêm ràng buộc về yếu tố đa kỹ năng của các tài nguyên. Trong bài toán MS-RCPSP, mỗi tài nguyên sẽ có thể có nhiều kỹ năng khác nhau, mỗi kỹ năng có thể có nhiều bậc (mức) kỹ năng khác, mỗi tác vụ cũng yêu cầu tài nguyên thực hiện cần đáp ứng đúng loại kỹ năng và phải đạt một mức nhất định mới có thể thực hiện được. Với sự mở rộng này bài toán MS-RCPSP có nhiều khả năng ứng dụng hơn trong thực tế. Hiện nay nhiều nhà khoa học đã đưa ra các phương pháp giải bài toán MS-RCPSP dựa trên giải thuật heuristic và metaheuristic, tuy nhiên các phương pháp này thường dựa trên các kỹ thuật khá truyền thống nên đạt hiệu quả chưa thực sự tốt. Do vậy, hướng nghiên cứu thứ nhất của luận án là
2 nghiên cứu đề xuất các phương pháp giải mới, hiệu quả hơn cho bài toán MS- RCPSP. Với bài toán MS-RCPSP, tài nguyên thực hiện tác vụ cần có kỹ năng phù hợp và bậc kỹ năng lớn hơn hoặc bằng bậc (mức) kỹ năng yêu cầu, thời gian thực hiện tác vụ là như nhau với bất kỳ tài nguyên thực hiện nào. Tuy nhiên, khi quan sát dữ liệu thực tế, tác giả nhận thấy tài nguyên có bậc kỹ năng cao hơn thường sẽ hoàn thành tác vụ nhanh hơn, chẳng hạn như thợ bậc 7 sẽ hoàn thành công việc trong thời gian ngắn hơn so với thợ bậc 3. Do vậy, luận án đề xuất bài toán mới Real-RCPSP, bài toán này bổ sung ràng buộc về thời gian thực hiện thay đổi theo bậc kỹ năng của tài nguyên thực hiện, đây là hướng nghiên cứu thứ hai của luận án. Tiếp theo, luận án nghiên cứu và đề xuất các thuật toán giải bài toán Real-RCPSP, đây là hướng nghiên cứu thứ ba của luận án. Bài toán MS-RCPSP và bài toán Real-RCPSP có thể ứng dụng trong nhiều lĩnh vực của khoa học và cuộc sống như lập lịch điều phối tài nguyên trong hệ điều hành, các hệ thống phân tán, lập lịch biểu cho các dây chuyền sản xuất,...Việc nghiên cứu giải hai bài toán trên có ý nghĩa quan trọng, giúp nâng cao hiệu suất của nhiều lĩnh vực nhất là trong điều kiện cách mạng công nghiệp 4.0 đang diễn ra trên mọi lĩnh vực. Nhiều trường hợp riêng của bài toán lập lịch đã được chứng minh là thuộc lớp NP-Khó, nên không thể tìm được lời giải tối ưu trong thời gian đa thức. Thay vì đó, một số phương pháp cận tối ưu được đề xuất để giải các bài toán này. Một số cách tiếp cận theo Heuristic truyền thống như Min-min, Max- min,... hoặc với các thuật toán truyền thống như GA[1],[52], Ant[12],[39],[41],[55],… thường cho chất lượng lời giải không tốt. Do vậy, việc nghiên cứu đề xuất các thuật toán mới là cần thiết để nâng cao chất lượng lời giải.
3 2. Mục tiêu nghiên cứu Trên cơ sở phân tích các vấn đề còn tồn tại của các nghiên cứu liên quan và xác định ba hướng nghiên cứu, mục tiêu của luận án là: - 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. 3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu - Bài toán lập lịch thực hiện dự án với tài nguyên giới hạn và khả năng áp dụng của bài toán này trong việc lập kế hoạch sản xuất, lập lịch điều phối luồng công việc, phân công thực hiện các tác vụ dựa trên các tập tài nguyên cho trước. - Các phương pháp Metaheuristic như thuật toán tối ưu bầy đàn PSO (Particle Swarm Optimization) [12],[23],[33],[56],[59], thuật toán di truyền GA (Genetic Algorithm) [1],[24], thuật toán tiến hóa vi phân DE (Differential Evolution) [8],[26], thuật toán tiến hóa CS (Cuckoo Search) [20],[25],[34],[36],[60],[61]. Phạm vi nghiên cứu của luận án là các phương pháp cận tối ưu và các thuật toán tiến hóa để giải bài toán MS-RCPSP và bài toán mới Real-RCPSP. 4. Nội dung nghiên cứu Luận án này tập trung vào nghiên cứu giải quyết hai bài toán: bài toán MS- RCPSP (đã có từ trước) và bài toán mới Real-RCPSP (do nghiên cứu sinh đề xuất, dựa trên bài toán RS-RCPSP) theo hướng tiếp cận Metaheuristic. Dựa
4 trên các giải thuật tiến hóa bao gồm Tối ưu bầy đàn PSO, Tiến hóa vi phân DE và CS, luận án đề xuất các thuật toán tiến hóa mới: - M-PSO và DEM để giải bài toán MS-RCPSP - A-DEM, R-CSM và RR-CSM để giải bài toán Real-RCPSP. Để kiểm chứng, cuối mỗi phần đều trình bày quá trình cài đặt các thuật toán đề xuất, thu thập, so sánh, phân tích và đánh giá kết quả thực nghiệm. 5. Phương pháp nghiên cứu Nghiên cứu được tiến hành dựa trên các phương pháp sau: - Phương pháp nghiên cứu tài liệu, phân tích và tổng hợp (Giai đoạn tìm hiểu bài toán); - Phương pháp phân tích và tổng hợp (Giai đoạn xây dựng mô hình lý thuyết và đề xuất giải pháp); - Phương pháp thực nghiệm (Giai đoạn kiểm chứng). Kết quả thực nghiệm trên các bộ dữ liệu được xử lý bằng những phương pháp sau: - Phân tích phương sai; - So sánh giá trị trung bình; - Phân tích tương quan. 6. Ý nghĩa khoa học và thực tiễn Về mặt lý thuyết khoa học, hiện nay có nhiều công trình nghiên cứu và đề xuất phương pháp giải cho bài toán MS-RCPSP, các phương pháp dựa trên các kỹ thuật truyền thống như Greedy, GA, Ant,... Luận án đề xuất các phương pháp hiệu quả hơn dựa trên các kỹ thuật tiến hóa như PSO, DE và CS. Luận án giới thiệu bài toán mới lần đầu được đề xuất là bài toán Real-RCPSP với khả năng ứng dụng thực tế cao hơn bài toán MS-RCPSP đã có, đặc biệt là khi được áp dụng trong các dây chuyền sản xuất hay các dự án tiến hành theo kiểu luồng công việc (workflow). Bài toán hướng tới việc lập kế hoạch sản xuất tự động
5 nhằm tối thiểu hóa thời gian thực hiện (makespan). Về thực tiễn, kết quả nghiên cứu của luận án là cơ sở khoa học để thực thi các thuật toán lập lịch điều phối thực hiện dự án với tài nguyên giới hạn trong thực tế. Luận án cũng nghiên cứu và đề xuất phương pháp số hóa dữ liệu thực tế để áp dụng cho mô hình bài toán lập lịch, điều này giúp ích trong việc chuyển đổi số và ứng dụng công nghệ thông tin trong tự động hóa sản xuất của doanh nghiệp. 7. Bố cục của luận án Luận án gồm các phần: Mở đầu, bốn chương chính, Kết luận và hướng phát triển, Danh mục các công trình khoa học đã công bố, Tài liệu tham khảo. Phần Mở đầu trình bày tính cấp thiết của đề tài luận án, những khái quát chung về mục tiêu, đối tượng, nội dung, phương pháp nghiên cứu, ý nghĩa khoa học và thực tiễn của luận án. Tóm tắt nội dung những phần còn lại như sau: Chương 1. Tổng quan về bài toán MS-RCPSP MS-RCPSP là bài toán lập lịch thực hiện dự án với tài nguyên giới hạn và đa kỹ năng, đã được chứng minh là bài toán NP-Khó. So với bài toán RCPSP tổng quát, bài toán MS-RCPSP là một trường hợp riêng có tính ứng dụng cao hơn trong một số lĩnh vực thực tế đặc thù do được bổ sung yếu tố kỹ năng và mức kỹ năng của tài nguyên thực hiện các tác vụ. Chương này trình bày tổng quan về bài toán MS-RCPSP, các ứng dụng của các bài toán này và ba trong số những thuật toán thuật toán metaheuristic mạnh nhất được các nhóm nghiên cứu trước đó áp dụng để giải bài toán MS-RCPSP nói riêng cũng như các bài toán NP-Khó nói chung là PSO, DE và CS. Ba thuật toán này cũng là cơ sở để luận án đề xuất các thuật toán mới trong các chương tiếp theo. 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.
6 Chương này trình bày về phương pháp biểu diễn cá thể của bài toán MS- RCPSP và đề xuất thang đo độ chênh lệch giữa các cá thể. Thang đo là thành phần quan trọng để phục vụ cho quá trình tính toán tiến hóa của các cá thể. Để phục vụ cho việc thực nghiệm, kiểm chứng thuật toán, chương này cũng giới thiệu về bộ dữ liệu iMOPSE, bộ dữ liệu chuẩn được Myszkowski [42],[45] và các cộng sự phát triển riêng cho bài toán MS-RCPSP. Trên cơ sở đó, luận án đề xuất hai thuật toán mới đề giải bài toán MS-RCPSP: - Thuật toán M-PSO được phát triển từ thuật toán tối ưu bầy đàn PSO - Thuật toán DEM được xây dựng trên cơ sở thuật toán tiến hóa vi phân DE Để kiểm chứng các thuật toán đề xuất, luận án tiến hành thực nghiệm, tổng hợp kết quả thực nghiệm, phân tích và đánh giá tính hiệu quả. Chương 3. Bài toán Real-RCPSP Chương 3 trình bày về bài toán mới đề xuất Real-RCPSP, bao gồm các nội dung như phát biểu toán học của bài toán, giới thiệu ứng dụng thực tế của bài toán và xếp loại bài toán. 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 Trong chương 4, luận án trình bày các vấn đề để giải bài toán Real-RCPSP gồm: mã hóa cá thể, xây dựng bộ dữ liệu thực tế và ba thuật toán mới để giải bài toán Real-RCPSP. - Thuật toán A-DEM, được xây dựng trên cơ sở thuật toán tiến hóa vi phân DE để ứng dụng tìm lời giải cho bài toán mới - Thuật toán R-CSM, thuật toán mới này được đề xuất trên cơ sở của thuật toán tiến hóa Cuckoo Search (CS) - Thuật toán RR-CSM, thuật toán mới này được cải tiến dựa trên thuật toán
7 R-CSM Các thuật toán này mang lại kết quả tốt với bài toán Real-RCPSP. Các thực nghiệm được tiến hành trên bộ dữ liệu iMOPSE và bộ dữ liệu TNG do nghiên cứu sinh tự thu thập và xây dựng. Kết quả thực nghiệm được thu thập, tổng hợp, phân tích và đánh giá tính hiệu quả.
8 CHƯƠNG 1 TỔNG QUAN VỀ BÀI TOÁN MS-RCPSP Các bài toán lập lịch đã được đề xuất, nghiên cứu từ năm 1950 [37], nhiệm vụ chính của việc lập lịch là tìm ra một lịch biểu để thiết lập các tài nguyên sẵn có trong việc thực hiện các công việc/tác vụ (task) và thỏa mãn tập ràng buộc cho trước nhằm đạt được một mục tiêu cụ thể, thường là tối thiểu hóa chi phí và/hoặc thời gian thực hiện của toàn dự án hoặc một quy trình sản xuất. Bài toán lập lịch được ứng dụng trong nhiều lĩnh vực khác nhau như lập lịch điều phối tài nguyên trong hệ điều hành [39], lập lịch cho dây chuyền sản xuất,... hoặc ứng dụng trong lĩnh vực kinh tế, tài chính [11],[62],[CT4], quân sự [17],[18],[28],[CT4], … Nhiều bài toán lập lịch tổng quát đã được chứng minh là thuộc lớp NP-Khó [2],[22],[46]. Ngày nay, rất nhiều ứng dụng trong nghiên cứu khoa học và thực tiễn có sử dụng đến dữ liệu dạng luồng công việc, đặc trưng của các ứng dụng này là phải xử lý nhiều tác vụ với dữ liệu vào/ra giữa các tác vụ là rất lớn. Tìm ra một lịch biểu tốt để gán các tài nguyên thực hiện từng tác vụ trong một chuỗi công việc một cách hiệu quả là rất cần thiết và thu hút sự tập trung của nhiều nhà khoa học. RCPSP (Resource-Constrained Project Scheduling Problem) [2],[46], [CT4] là bài toán lập lịch dự án với tài nguyên giới hạn, đã được chứng minh là bài toán thuộc lớp NP-Khó. Mục tiêu là tìm ra lịch biểu thực hiện dự án với thời gian tối thiểu trong điều kiện hạn chế về tài nguyên thực hiện. Hiện nay, bài toán này được nghiên cứu và ứng dụng trong nhiều lĩnh vực. Luận án tập trung tìm hiểu một trường hợp mở rộng của bài toán RCPSP, được đặt tên là MS-RCPSP. Chương này gồm các nội dung chính sau: Phần 1.1: Trình bày về bài toán lập lịch thực hiện dự án với tài nguyên giới