Bài viết này đề xuất và phát biểu dưới hình thức toán học một bài toán mới được đặt tên là TDOS-RCPSP. Là bài toán thuộc họ RCPSP đã biết, TDOSRCPSP có nhiều ứng dụng thiết thực trong các lĩnh vực khác nhau, đặc biệt là trong việc tổ chức các dây chuyền sản xuất công nghiệp. | HNUE JOURNAL OF SCIENCE DOI Natural Sciences 2023 Volume 68 Issue 1 pp. 77-90 This paper is available online at http GIẢI THUẬT TIẾN HÓA CHO BÀI TOÁN LẬP LỊCH VỚI TÀI NGUYÊN GIỚI HẠN MỚI Nguyễn Thế Lộc1 Đặng Quốc Hữu2 và Vũ Thái Giang1 Khoa Công nghệ thông tin Trường Đại học Sư phạm Hà Nội 1 2 Khoa Hệ thống thông tin Kinh tế và Thương mại điện tử Trường Đại học Thương mại Tóm tắt. Bài báo này đề xuất và phát biểu dưới hình thức toán học một bài toán mới được đặt tên là TDOS-RCPSP. Là bài toán thuộc họ RCPSP đã biết TDOS- RCPSP có nhiều ứng dụng thiết thực trong các lĩnh vực khác nhau đặc biệt là trong việc tổ chức các dây chuyền sản xuất công nghiệp. Bài báo này sẽ đề xuất một thuật toán tiến hóa dựa trên chiến lược Cuckoo Search để tìm lời giải gần đúng cho bài toán TDOS-RCPSP. Bài báo sẽ giới thiệu những kết quả thực nghiệm được tiến hành nhằm kiểm chứng hiệu quả của thuật toán đề xuất dựa trên hai bộ dữ liệu thực nghiệm. Bộ dữ liệu thứ nhất iMOPSE đã được công bố trong các công trình nghiên cứu cùng lĩnh vực trước đây. Bộ dữ liệu còn lại được tác giả thu thập từ các dây chuyền dệt may công nghiệp của tập đoàn TNG. Những kết quả thu được đã khẳng định sự vượt trội của thuật toán tiến hóa đề xuất so với những thuật toán trong cùng lĩnh vực đã được công bố trước đó. Từ khóa lập lịch với tài nguyên giới hạn thuật toán tiến hóa thuật toán Cuckoo Seach. 1. Mở đầu RCPSP 1 là lớp các bài toán lập lịch có ứng dụng trong nhiều lĩnh vực thực tế mà điển hình là việc tổ chức các dây chuyền sản xuất công nghiệp 2-5 . Một số bài toán trong lớp RCPSP đã được chứng minh là NP-Khó ví dụ như bài toán MS-RCPSP Multi Skill - Resource-Constrained Project Scheduling Problem Bài toán lập lịch đa kĩ năng với tài nguyên giới hạn 6-9 . Đã có nhiều nhóm nghiên cứu công bố giải pháp cho bài toán MS-RCPSP hướng tới việc tìm lịch biểu có thời gian thực hiện từ đây gọi là makespan tối thiểu trong một số điều kiện ràng buộc về tài nguyên và giả .
