I. Giới thiệu về Phương pháp Gần đúng Giải Bài Toán Lập Lịch
Phương pháp gần đúng giải bài toán lập lịch là một lĩnh vực nghiên cứu quan trọng trong toán học ứng dụng và khoa học máy tính. Bài toán lập lịch với tài nguyên giới hạn (RCPSP) là một thách thức lớn trong quản lý dự án hiện đại. Các phương pháp gần đúng được phát triển để tìm kiếm các giải pháp tối ưu hoặc gần tối ưu trong thời gian hợp lý. Luận án tiến sĩ của Đặng Quốc Hữu từ Viện Khoa học và Công nghệ quân sự đã đề xuất nhiều thuật toán metaheuristic hiệu quả. Những phương pháp này kết hợp các kỹ thuật tìm kiếm thông minh để giải quyết các bài toán phức tạp trong lập lịch dự án.
1.1. Định nghĩa Bài Toán Lập Lịch
Bài toán lập lịch với tài nguyên giới hạn (MS-RCPSP) là bài toán xác định thứ tự thực hiện các tác vụ với các ràng buộc về tài nguyên. Mục tiêu chính là tối thiểu hóa thời gian hoàn thành dự án (makespan). Các tác vụ có mối quan hệ phụ thuộc, yêu cầu tài nguyên cụ thể, và phải tuân theo các ràng buộc về khả năng cung cấp tài nguyên.
1.2. Tầm quan trọng của Phương pháp Gần đúng
Do bài toán lập lịch là NP-khó, các phương pháp chính xác không khả thi với quy mô lớn. Phương pháp gần đúng cung cấp giải pháp hiệu quả và thực tế. Chúng cho phép tìm kiếm các lời giải chất lượng cao trong thời gian tính toán hợp lý, phù hợp với các ứng dụng thực tế.
II. Các Thuật toán Metaheuristic Chính
Luận án đã nghiên cứu và phát triển nhiều thuật toán metaheuristic khác nhau để giải bài toán lập lịch. Các thuật toán này bao gồm thuật toán PSO (Particle Swarm Optimization), thuật toán DE (Differential Evolution), và thuật toán Cuckoo Search. Mỗi phương pháp có những ưu điểm riêng trong việc khám phá không gian tìm kiếm. Thuật toán M-PSO được đề xuất kết hợp PSO với kỹ thuật Di cư để cải thiện hiệu suất. Thuật toán DEM áp dụng Tiến hóa vi phân với phương pháp tái thiết lập tài nguyên. Các thuật toán này đã chứng minh hiệu quả cao trong các thử nghiệm thực tế.
2.1. Thuật toán PSO và M PSO
Thuật toán PSO mô phỏng hành vi tập trung của bầy đàn. Phiên bản cải tiến M-PSO kết hợp kỹ thuật Di cư để tăng tính đa dạng của quần thể. Phương pháp này giúp tránh rơi vào cực tiểu địa phương và cải thiện chất lượng lời giải đáng kể.
2.2. Thuật toán DE và Cuckoo Search
Thuật toán DEM sử dụng Tiến hóa vi phân kết hợp với tái thiết lập tài nguyên. Thuật toán Cuckoo Search mô phỏng hành vi đẻ trứng của chim cuckoo. Cả hai phương pháp đều cho kết quả cạnh tranh với các thuật toán truyền thống.
III. Bài Toán Real RCPSP và Ứng Dụng
Bài toán Real-RCPSP là mở rộng của MS-RCPSP khi các tài nguyên là liên tục (không rời rạc). Đây là dạng bài toán gần với thực tế hơn khi tài nguyên có thể được chia nhỏ. Luận án đã phát triển thuật toán A-DEM với phương pháp thích nghi để giải bài toán này. Thuật toán R-CSM và RR-CSM được đề xuất sử dụng Cuckoo Search kết hợp các kỹ thuật tối ưu hóa. Những ứng dụng thực tế bao gồm lập lịch xây dựng, quản lý dự án phần mềm, và các dự án quy mô lớn.
3.1. Phân Loại Graham cho Real RCPSP
Phân loại Graham là cách phân loại hệ thống lập lịch dựa trên các đặc trưng: α (môi trường máy), β (đặc tính công việc), γ (tiêu chí tối ưu). Việc này giúp xác định độ khó của bài toán và lựa chọn thuật toán phù hợp nhất.
3.2. Ứng Dụng Thực Tế
Bài toán Real-RCPSP áp dụng trong quản lý dự án hiện đại, xây dựng hạ tầng, và sản xuất công nghiệp. Việc tối ưu hóa lập lịch giúp giảm chi phí, rút ngắn thời gian dự án, và sử dụng hiệu quả tài nguyên.
IV. Kết Quả Nghiên Cứu và Đánh Giá
Luận án đã tiến hành các thử nghiệm toàn diện để đánh giá chất lượng các phương pháp gần đúng được đề xuất. Các thuật toán được so sánh với GA-M (Genetic Algorithm) trên các bộ dữ liệu tiêu chuẩn. Kết quả cho thấy M-PSO, DEM, A-DEM, R-CSM, và RR-CSM đều vượt trội hơn các phương pháp cũ. Giá trị trung bình (AVG) và giá trị tốt nhất (BEST) của các giải pháp được ghi nhận. Các hình ảnh so sánh minh họa rõ ràng sự cải thiện hiệu suất. Nghiên cứu này góp phần quan trọng vào phát triển lĩnh vực tối ưu hóa lập lịch.
4.1. Các Chỉ Tiêu Đánh Giá
Chất lượng lời giải được đánh giá qua giá trị tốt nhất, giá trị trung bình, và độ lệch chuẩn. Thời gian tính toán là tiêu chí quan trọng khác. Các thuật toán mới đều thể hiện cải thiện đáng kể so với các phương pháp cũ.
4.2. Hướng Phát Triển Tương Lai
Nghiên cứu mở ra các hướng phát triển mới: kết hợp nhiều thuật toán (hybrid), ứng dụng trí tuệ nhân tạo, và mở rộng cho bài toán đa mục tiêu. Phương pháp gần đúng sẽ tiếp tục được cải tiến để xử lý các bài toán phức tạp hơn.
