I. Tổng quan về bài toán lập lịch tại Đại học Quốc gia
Bài toán lập lịch luôn là một bài toán khó, mang tính khoa học đồng thời tính thực tiễn cũng rất cao. Không chỉ Việt Nam mà trên toàn cầu từ lâu việc lập lịch đã trở thành một vấn đề có tính thời sự, một bài toán gây được sự chú ý, quan tâm của nhiều người. Bài toán lập thời khóa biểu là một nhánh của bài toán lập lịch trong đó đưa ra một chuỗi các sự kiện (thông thường là các môn học, bài giảng hoặc các môn thi) và bao gồm các giáo viên và học viên trong một khoảng thời gian định trước và thỏa mãn một tập hợp các ràng buộc của từng loại thời khóa biểu khác nhau. Mỗi bài toán có các tính chất riêng, khi xếp lịch thi bài toán đặt ra là phải đáp ứng được yêu cầu về thời gian (như không được trùng hay quá sát nhau) giữa các lần thi liên tiếp của cùng một học sinh, sinh viên. Còn khi xếp lịch cho trường phổ thông thì chúng ta cần quan tâm giờ rảnh mà giáo viên đăng ký và các tiết trống giữa giờ học của học sinh đóng vai trò rất quan trọng cho việc đánh giá kết quả của thời khóa biểu. Đối với đại học, bài toán cần giải quyết cũng là việc tránh xung đột giữa các thành phần tham gia trong thời khóa biểu (giáo viên, lớp học, phòng học và thiết bị). Vì thế, mục tiêu cuối cùng của người xếp thời khóa biểu là tạo ra một thời khóa biểu với ít xung đột nhất. Cũng đã có các khảo sát về bài toán xếp thời khóa biểu. Như việc đưa ra tổng quan các vấn đề về xếp thời khóa biểu thuộc ba dạng ta đã đề cập ở trên của Schaerf, 1995 [1]. Các khảo sát về xếp lịch thi Carter & Laporte, 1996 [2] và xếp lịch cho trường đại học Carter & Laporte, 1998 [3] Bardadym, 1996 [4].
1.1. Bài toán lập lịch thi và lập lịch học khác nhau thế nào
Bài toán lập lịch thi có những đặc điểm khác sau đây: Chỉ có một kỳ thi cho mỗi một môn thi. Các điều kiện xung đột nói chung là hạn chế. Thực tế, chúng ta có thể chấp nhận một sinh viên có thể bỏ qua một bài giảng do sự chồng chéo các môn học; nhưng không có sinh viên nào được phép bỏ qua một kỳ thi hết môn đã học vì nếu sinh viên không qua được kỳ thi này coi như trượt môn đó. Và một số ràng buộc khác như hầu hết một sinh viên sẽ chỉ có một môn thi trong một ngày và không có nhiều quá các môn thi liên tiếp nhau với một sinh viên. Thời gian thi của các môn thi có thể khác nhau, ngược lại với bài toán lập thời khóa biểu cho trường đại học thì thời gian học được tính bằng tiết (45 – 50 phút tùy quy định của trường).
1.2. Tổng quan về bài toán lập lịch theo tín chỉ
II. Thách thức trong lập lịch thi tại Đại học Quốc gia
Việc lập lịch thi hiệu quả tại Đại học Quốc gia Hà Nội đối mặt với nhiều thách thức. Số lượng sinh viên lớn, đa dạng các môn học và chương trình đào tạo tạo ra một không gian tìm kiếm phức tạp. Các ràng buộc về phòng thi, giảng viên, và thời gian thi càng làm tăng độ khó của bài toán. Hơn nữa, việc đảm bảo tính công bằng, minh bạch và sự hài lòng của sinh viên cũng là một yếu tố quan trọng cần xem xét. Các phương pháp lập lịch truyền thống thường gặp khó khăn trong việc xử lý các ràng buộc phức tạp và tìm kiếm giải pháp tối ưu trong thời gian ngắn. Do đó, việc nghiên cứu và áp dụng các giải pháp lập lịch thông minh là vô cùng cần thiết.
2.1. Độ phức tạp của bài toán lập lịch và các ràng buộc
Bài toán lập lịch thuộc lớp bài toán NP-khó, có nghĩa là thời gian giải bài toán tăng theo cấp số nhân với kích thước của bài toán. Các ràng buộc cứng (hard constraints) như không có sinh viên nào thi hai môn cùng lúc, không có phòng thi nào được sử dụng cho hai môn cùng lúc, và các ràng buộc mềm (soft constraints) như tối thiểu hóa số lượng sinh viên phải thi hai môn liên tiếp trong cùng một ngày, tạo ra một không gian tìm kiếm khổng lồ. Việc tìm kiếm một giải pháp thỏa mãn tất cả các ràng buộc là một thách thức lớn.
2.2. Yêu cầu về tính công bằng và minh bạch trong lập lịch thi
Sinh viên mong muốn lịch thi được công bố sớm, không có sự thay đổi đột ngột, và không có sự ưu ái cho bất kỳ môn học hay khoa nào. Việc đảm bảo tính công bằng và minh bạch đòi hỏi quy trình lập lịch phải được chuẩn hóa, có sự tham gia của các bên liên quan, và có cơ chế phản hồi để giải quyết các khiếu nại. Các giải pháp lập lịch thông minh cần có khả năng tạo ra các lịch thi đa dạng, đánh giá các lịch thi dựa trên nhiều tiêu chí, và cho phép người dùng tùy chỉnh các ràng buộc để đáp ứng các yêu cầu cụ thể.
III. Giải thuật Tabu Search cho bài toán lập lịch hiệu quả
Giải thuật Tabu Search là một phương pháp tìm kiếm meta-heuristic hiệu quả để giải quyết các bài toán tối ưu hóa tổ hợp, bao gồm bài toán lập lịch. Tabu Search hoạt động bằng cách di chuyển từ một giải pháp hiện tại sang một giải pháp lân cận tốt nhất, ngay cả khi giải pháp lân cận đó không tốt hơn giải pháp hiện tại. Để tránh lặp lại các giải pháp đã được xét, Tabu Search sử dụng một danh sách cấm (tabu list) để lưu trữ các thuộc tính của các giải pháp đã được xét gần đây. Các thuộc tính này bị cấm (tabu) trong một số lần lặp nhất định, ngăn chặn giải thuật quay lại các giải pháp đã được xét.
3.1. Cơ sở lý thuyết của giải thuật Tabu Search
Tabu Search dựa trên ý tưởng rằng việc khám phá không gian tìm kiếm một cách có hệ thống, thay vì chỉ tìm kiếm các giải pháp tốt hơn, có thể giúp giải thuật thoát khỏi các cực trị địa phương và tìm kiếm các cực trị toàn cục. Danh sách cấm giúp giải thuật tránh lặp lại các giải pháp đã được xét, nhưng cũng có thể ngăn chặn giải thuật tìm kiếm các giải pháp tốt trong vùng lân cận của các giải pháp đã được xét. Do đó, việc thiết kế danh sách cấm và các tiêu chí chấp nhận (aspiration criteria) là rất quan trọng để đảm bảo hiệu quả của Tabu Search.
3.2. Ưu điểm của Tabu Search so với các giải thuật khác
Tabu Search có nhiều ưu điểm so với các giải thuật tìm kiếm khác như giải thuật di truyền (Genetic Algorithm) và giải thuật mô phỏng luyện kim (Simulated Annealing). Tabu Search có khả năng thoát khỏi các cực trị địa phương tốt hơn, hội tụ nhanh hơn, và dễ dàng tùy chỉnh để phù hợp với các bài toán cụ thể. Tuy nhiên, Tabu Search cũng có một số nhược điểm như yêu cầu nhiều tham số, khó khăn trong việc thiết kế danh sách cấm và các tiêu chí chấp nhận, và có thể bị mắc kẹt trong các chu kỳ tìm kiếm.
IV. Ứng dụng Tabu Search để tối ưu hóa thời khóa biểu
Ứng dụng Tabu Search vào bài toán lập lịch tại Đại học Quốc gia Hà Nội mang lại nhiều lợi ích. Giải thuật có khả năng xử lý các ràng buộc phức tạp, tìm kiếm giải pháp tối ưu trong thời gian ngắn, và tạo ra các lịch thi đa dạng. Việc áp dụng Tabu Search giúp cải thiện hiệu quả lập lịch, giảm thiểu xung đột, và tăng sự hài lòng của sinh viên. Hơn nữa, giải thuật có thể được tích hợp vào các phần mềm quản lý đào tạo hiện có, giúp tự động hóa quy trình lập lịch và giảm tải cho cán bộ quản lý.
4.1. Mô hình hóa bài toán lập lịch cho Tabu Search
Để áp dụng Tabu Search, bài toán lập lịch cần được mô hình hóa một cách phù hợp. Các yếu tố như môn học, sinh viên, phòng thi, thời gian thi, và các ràng buộc cần được biểu diễn dưới dạng các biến và hàm mục tiêu. Hàm mục tiêu thường được thiết kế để tối thiểu hóa số lượng xung đột và vi phạm các ràng buộc mềm. Các giải pháp lân cận được tạo ra bằng cách thay đổi vị trí của các môn học trong lịch thi, và danh sách cấm được sử dụng để ngăn chặn việc quay lại các lịch thi đã được xét gần đây.
4.2. Cài đặt và thử nghiệm Tabu Search cho lập lịch thi
Việc cài đặt Tabu Search đòi hỏi kiến thức về lập trình và giải thuật. Các tham số của Tabu Search như kích thước danh sách cấm, số lần lặp, và các tiêu chí chấp nhận cần được điều chỉnh để đạt được hiệu quả tốt nhất. Các thử nghiệm cần được thực hiện trên các bộ dữ liệu thực tế để đánh giá hiệu quả của giải thuật so với các phương pháp lập lịch truyền thống. Kết quả thử nghiệm có thể được sử dụng để cải thiện mô hình hóa bài toán và các tham số của Tabu Search.
V. Kết quả nghiên cứu và so sánh với phần mềm lập lịch
Nghiên cứu đã đạt được những kết quả khả quan trong việc áp dụng Tabu Search cho bài toán lập lịch tại Đại học Quốc gia Hà Nội. Giải thuật đã tạo ra các lịch thi có số lượng xung đột ít hơn so với các lịch thi được tạo ra bằng các phương pháp thủ công. So sánh với phần mềm lập lịch Open Course Timetable, Tabu Search cho thấy khả năng tùy chỉnh cao hơn và khả năng xử lý các ràng buộc phức tạp tốt hơn. Tuy nhiên, Tabu Search cũng đòi hỏi thời gian tính toán lâu hơn và yêu cầu kiến thức chuyên môn để cài đặt và điều chỉnh.
5.1. Đánh giá hiệu quả của Tabu Search trên dữ liệu thực tế
Hiệu quả của Tabu Search được đánh giá dựa trên các tiêu chí như số lượng xung đột, thời gian tính toán, và sự hài lòng của sinh viên. Các thử nghiệm được thực hiện trên các bộ dữ liệu thực tế từ Đại học Quốc gia Hà Nội, và kết quả cho thấy Tabu Search có khả năng tạo ra các lịch thi tốt hơn so với các phương pháp thủ công. Tuy nhiên, cần có thêm các nghiên cứu để đánh giá hiệu quả của Tabu Search trên các bộ dữ liệu lớn hơn và phức tạp hơn.
5.2. So sánh Tabu Search với phần mềm Open Course Timetable
So sánh Tabu Search với phần mềm Open Course Timetable cho thấy Tabu Search có khả năng tùy chỉnh cao hơn và khả năng xử lý các ràng buộc phức tạp tốt hơn. Open Course Timetable là một phần mềm lập lịch miễn phí và dễ sử dụng, nhưng nó có một số hạn chế trong việc xử lý các ràng buộc phức tạp và tùy chỉnh các tham số. Tabu Search đòi hỏi kiến thức chuyên môn để cài đặt và điều chỉnh, nhưng nó có khả năng tạo ra các lịch thi tốt hơn trong các trường hợp phức tạp.
VI. Hướng phát triển và ứng dụng lập lịch trong tương lai
Trong tương lai, việc nghiên cứu và phát triển các giải pháp lập lịch thông minh sẽ tiếp tục là một hướng đi quan trọng. Các giải thuật meta-heuristic như Tabu Search, giải thuật di truyền, và giải thuật mô phỏng luyện kim có thể được kết hợp với các kỹ thuật học máy và trí tuệ nhân tạo để tạo ra các hệ thống lập lịch tự động và thích ứng. Các hệ thống này có thể học hỏi từ dữ liệu lịch sử, dự đoán nhu cầu của sinh viên, và tự động điều chỉnh các tham số để đạt được hiệu quả tốt nhất.
6.1. Tích hợp trí tuệ nhân tạo vào hệ thống lập lịch
Tích hợp trí tuệ nhân tạo vào hệ thống lập lịch có thể giúp hệ thống học hỏi từ dữ liệu lịch sử, dự đoán nhu cầu của sinh viên, và tự động điều chỉnh các tham số để đạt được hiệu quả tốt nhất. Các kỹ thuật học máy như học sâu (deep learning) và học tăng cường (reinforcement learning) có thể được sử dụng để xây dựng các mô hình dự đoán và tối ưu hóa. Các mô hình này có thể được sử dụng để dự đoán số lượng sinh viên đăng ký mỗi môn học, tối ưu hóa việc phân bổ phòng thi, và tự động điều chỉnh các tham số của Tabu Search.
6.2. Phát triển hệ thống lập lịch thích ứng và cá nhân hóa
Phát triển hệ thống lập lịch thích ứng và cá nhân hóa có thể giúp sinh viên tạo ra các lịch thi phù hợp với nhu cầu và sở thích của mình. Hệ thống có thể cho phép sinh viên tùy chỉnh các ràng buộc, chọn các môn học ưu tiên, và xem các lịch thi khác nhau trước khi quyết định. Hệ thống cũng có thể cung cấp các gợi ý và khuyến nghị dựa trên dữ liệu lịch sử và thông tin cá nhân của sinh viên. Các hệ thống lập lịch thích ứng và cá nhân hóa có thể giúp tăng sự hài lòng của sinh viên và cải thiện hiệu quả học tập.
