Xếp TKB tín chỉ uniScheGA

Trong cuộc sống ta thường gặp các bài toán liên quan đến xếp lịch như xếp lịch vận hành máy móc, xếp lịch biểu cho việc thực hiện một dự án, xếp lịch làm việc, xếp lịch thi đấu thể thao,… Đối với loại bài toán này cần phải tìm ra một phương án xếp lịch thỏa mãn tất cả các ràng buộc cũng như khai thác hiệu quả các nguồn tài nguyên hiện có, giảm thời gian và chi phí thực hiện.

Bài toán xếp thời khóa biểu trong trường học nói chung và trong trường Đại học nói riêng là một trong những bài toán như vậy. Có rất nhiều các ràng buộc được đặt ra trong bài toán này như ràng buộc về đối tượng tham gia (giảng viên, lớp học, sinh viên), ràng buộc về tài nguyên phục vụ giảng dạy (phòng học lý thuyết, phòng thực hành,…), ràng buộc về thời gian (số tiết học, số lần học, số tiết mỗi lần), ràng buộc về chuyên môn và rất nhiều các ràng buộc khác tùy thuộc vào từng trường. Vấn đề đặt ra là cần xây dựng một thời khóa biểu thỏa mãn tất cả các ràng buộc trên đồng thời khai thác hiệu quả các nguồn tài nguyên phục vụ giảng dạy.

Bài toán xếp thời khóa biểu thuộc lớp các bài toán NP-đầy đủ vì vậy có thể không tìm ra được lời giải tối ưu. Đây là một bài toán không mới và đã có nhiều giải thuật được đưa ra để giải quyết như giải thuật nhánh cận, giải thuật leo đồi, giải thuật luyện thép, giải thuật tô màu đồ thị, giải thuật xấp xỉ,… Tuy nhiên các giải thuật này thường không có tính tổng quát và chỉ áp dụng hiệu quả đối với các trường học có quy mô nhỏ, ít ràng buộc về mặt dữ liệu.

Ở Việt Nam hiện nay, các trường Đại học đang dần chuyển sang hình thức đào tạo tín chỉ. Mặc dầu hình thức đào tạo này có nhiều ưu điểm hơn so với đào tạo niên chế tuy nhiên việc xếp thời khóa biểu vẫn là một gánh nặng thực sự cho các trường, đặc biệt là các trường có quy mô đào tạo lớn. Vả lại trên thị trường cũng chưa có sản phẩm phần mềm nào giải quyết hiệu quả bài toán trên.

Trong những năm gần đây, phương pháp tiếp cận di truyền đã thu hút rất nhiều sự chú ý trong các lĩnh vực nghiên cứu khác nhau trong đó có khoa học máy tính. Phương pháp này có nhiều đặc điểm nổi trội như không đòi hỏi tri thức, tránh tối ưu cục bộ, thực hiện tốt với các bài toán có không gian lời giải lớn và có thể áp dụng cho nhiều loại bài toán tối ưu khác nhau. Trên thế giới hiện nay, giải thuật di truyền kết hợp với tin học được ứng dụng để giải quyết những bài toán tối ưu một cách rất hiệu quả.

Vì vậy, việc nghiên cứu và ứng dụng giải thuật di truyền (Genetic Algorithm - GA) để giải quyết hiệu quả bài toán xếp thời khóa biểu nói trên là việc làm cần thiết.

Một số hình ảnh của hệ thống xếp TKB tín chỉ uniScheGA:

Giao diện xếp thời khóa biểu

Thời khóa biểu của lớp

Thời khóa biểu của giảng viên

Lịch sử dụng phòng

In thời khóa biểu.