I. Tổng quan về bài toán lập lịch
Bài toán lập lịch là một lĩnh vực nghiên cứu quan trọng trong quản lý thời gian và tài nguyên. Lịch biểu được định nghĩa là một kế hoạch chi tiết cho việc thực hiện các công việc trong một khoảng thời gian nhất định. Mục tiêu chính của bài toán này là tối ưu hóa thời gian hoàn thành các tác vụ, từ đó nâng cao hiệu quả sử dụng tài nguyên. Các ứng dụng của bài toán lịch biểu rất đa dạng, từ lập lịch sản xuất, lập thời khóa biểu cho giảng viên, đến lập lịch cho các bác sĩ trong bệnh viện. Việc nghiên cứu và phát triển các thuật toán để giải quyết bài toán này là rất cần thiết, đặc biệt trong bối cảnh ngày càng gia tăng nhu cầu tối ưu hóa trong các lĩnh vực khác nhau. Theo nghiên cứu, có hai phương pháp chính để giải bài toán lập lịch: phương pháp chính xác và phương pháp gần đúng. Phương pháp chính xác, như thuật toán nhánh cận, đảm bảo tìm ra giải pháp tối ưu nhưng thường tốn nhiều thời gian. Ngược lại, phương pháp gần đúng, mặc dù không đảm bảo giải pháp tối ưu, lại có ưu điểm về tốc độ và khả năng áp dụng trong thực tế.
1.1. Định nghĩa bài toán lập lịch Jobshop JSP
Bài toán lập lịch Jobshop (JSP) là một trong những bài toán tối ưu tổ hợp khó nhất hiện nay. Được định nghĩa như sau: cho một tập hợp các công việc, mỗi công việc bao gồm nhiều thao tác cần được thực hiện trên các máy khác nhau theo một trình tự nhất định. Mỗi máy chỉ có thể xử lý một công việc tại một thời điểm. Mục tiêu là tìm ra một lịch biểu sao cho thời gian hoàn thành tất cả các công việc, được gọi là makespan, là nhỏ nhất. Bài toán này không chỉ có độ phức tạp cao mà còn có nhiều ứng dụng thực tiễn trong sản xuất và quản lý. Việc giải quyết bài toán JSP đã thu hút sự quan tâm của nhiều nhà nghiên cứu và đã có nhiều phương pháp được đề xuất, từ các thuật toán chính xác đến các phương pháp gần đúng. Đặc biệt, thuật toán di truyền và các kỹ thuật tìm kiếm địa phương đã cho thấy hiệu quả trong việc tìm kiếm các giải pháp gần tối ưu cho bài toán này.
II. Tình hình nghiên cứu thuật toán tìm kiếm lịch biểu tối ưu
Nghiên cứu về bài toán lịch biểu đã diễn ra từ những năm 1950 và đã có nhiều công trình quan trọng được công bố. Tình hình nghiên cứu trên thế giới cho thấy, bài toán JSP lần đầu tiên được giới thiệu bởi Akers và Friedman, và sau đó trở nên nổi tiếng nhờ vào bài toán 10 công việc 10 máy của Fisher và Thompson. Nhiều phương pháp đã được phát triển để giải quyết bài toán này, bao gồm các thuật toán chính xác như quy hoạch nguyên và thuật toán nhánh cận. Tuy nhiên, do độ phức tạp của bài toán, các phương pháp gần đúng như thuật toán di truyền và tìm kiếm Tabu cũng đã được áp dụng rộng rãi. Tại Việt Nam, nghiên cứu về JSP cũng đang được quan tâm, với nhiều công trình tìm kiếm các phương pháp cải tiến thuật toán đã được đề xuất. Các ứng dụng thực tiễn của bài toán này chủ yếu tập trung vào lĩnh vực giáo dục và sản xuất, như lập thời khóa biểu và kế hoạch sản xuất. Việc phát triển các thuật toán hiệu quả để giải quyết bài toán JSP không chỉ có ý nghĩa lý thuyết mà còn mang lại giá trị thực tiễn cao.
2.1. Tình hình nghiên cứu trên thế giới
Nghiên cứu về bài toán lập lịch đã có một lịch sử dài và phong phú. Các công trình nghiên cứu đầu tiên đã chỉ ra rằng bài toán JSP là NP-hard, điều này có nghĩa là không có giải pháp chính xác nào có thể tìm ra trong thời gian hợp lý cho tất cả các trường hợp. Nhiều nhà nghiên cứu đã phát triển các phương pháp khác nhau để giải quyết bài toán này, từ các thuật toán chính xác đến các phương pháp gần đúng. Các thuật toán như nhánh cận và quy hoạch tuyến tính nguyên đã được chứng minh là hiệu quả trong việc tìm kiếm giải pháp tối ưu. Tuy nhiên, do tính chất phức tạp của bài toán, các phương pháp gần đúng như thuật toán di truyền và tìm kiếm Tabu đã trở thành lựa chọn phổ biến trong thực tế. Những nghiên cứu này không chỉ giúp cải thiện hiệu suất của các thuật toán mà còn mở ra hướng đi mới cho việc ứng dụng trong các lĩnh vực khác nhau.
