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ả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

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

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

Xem toàn bộ 156 trang tài liệu này.

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

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

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à

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.

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

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

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.