THUẬT TOÁN TIẾN HÓA GIẢI BÀI TOÁN LẬP LỊCH DỰ ÁN VỚI TÀI NGUYÊN GIỚI HẠN (MS-RCPSP) VÀ ỨNG DỤNG TRONG VIỆC LẬP KẾ HOẠCH SẢN XUẤT THÔNG MINH
Tóm tắt
TÓM TẮT
Bài báo trình bày phương pháp lập kế hoạch sản xuất thông minh bằng việc ứng dụng bài toán lập lịch thực hiện dự án với tài nguyên giới hạn MS-RCPSP đa kỹ năng (Multi Skill-Resource Constrained Project Scheduling Problem). Bài toán này đã được chứng minh là bài toán thuộc lớp bài toán kho (NP-Hard), do vậy không thể tìm được lời giải chính xác trong thời gian đa thức mà cần sử dụng một số giải thuật cận tối ưu để tìm nghiệm tốt nhất trong khoảng thời gian cho phép. Bài báo này nghiên cứu và đề xuất phương pháp giải bài toán MS-RCPSP dựa trên thuật toán Memetic kết hợp với phương pháp tái thiết lập tài nguyên (Reassignment), thuật toán mới gọi là MEM-RES, có khả năng tìm kiếm được các nghiệm tốt hơn sau mỗi thế hệ tiến hóa. Bài báo thực hiện chạy thử nghiệm thuật toán mới với bộ dữ liệu sản xuất thực tế chuyền may công nghiệp TNG. Kết quả cho thấy, thuật toán đề xuất phù hợp với bài toán và đạt được hiệu quả cao. Lời giải của bài toán này là một lịch biểu thể hiện việc sắp xếp các tài nguyên thực hiện từng công việc của dự án theo thời gian cho đến khi dự án hoàn thành. Do vậy, lời giải có thể áp dụng được trong việc lập kế hoạch sản xuất tự động thay cho cách thức lập kế hoạch truyền thống như hiện nay trong các nhà máy sản xuất, đặc biệt với mô hình sản xuất theo dây chuyền.
ABSTRACT
This paper introduces an intelligent production planning approach that addresses the challenges of scheduling project execution with limited resources in the MS-RCPSP (Multi Skill-Resource Constrained Project Scheduling Problem). Due to its classification as an NP-Difficult problem, finding an exact solution within a polynomial time frame is impossible. However, the paper proposes a method called MEM-RES, which combines the Memetic algorithm with the Reassignment method to find approximate solutions efficiently. The algorithm iteratively improves the solutions with each evolutionary generation. The proposed algorithm has experimented using actual production data from the TNG industrial sewing line. The results demonstrate the algorithm's suitability for the problem and its ability to achieve high efficiency. The solution obtained through this approach provides a schedule that organizes resources for executing each project's tasks over time until finished. Consequently, this solution can be made the automatic production planning, replacing the traditional methods currently employed in production factories, especially those utilizing a production line model.
Tệp đính kèm
© 2023 DNTU. All rights reserved.