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