Công cụ tạo tự động / Thuật toán tạo thời khóa biểu

Công cụ tạo tự động của Omniscol tính toán vị trí của các tiết học trong một thời khóa biểu theo tuần, theo chu kỳ hoặc theo lịch. Nó xếp những tiết học đã tạo mà chưa được đặt vị trí, có thể di chuyển những tiết học đã đặt nếu việc đó làm thời khóa biểu tốt hơn, và giữ nguyên vị trí của các tiết học đã khóa.

Cách hoạt động

Khi bạn khởi chạy một lượt tạo tự động, Omniscol khởi động một môi trường tính toán riêng, chạy song song. Phía nhà trường không có hàng đợi nào phải quản lý; phần khởi tạo thường mất khoảng mười giây trước khi thấy được những bước tính toán đầu tiên. Kết quả phụ thuộc vào chất lượng dữ liệu đã nhập: cơ sở, phòng học, giáo viên, nhóm, khối lượng giờ, thời gian rảnh và các điểm không tương thích. Ràng buộc càng nhiều hoặc càng mâu thuẫn với nhau thì việc tạo tự động càng có thể kéo dài hoặc chỉ cho ra kết quả một phần.

Bộ máy này là một AI tối ưu hóa theo hướng siêu heuristic Monte-Carlo nơ-ron – ký hiệu: nó kết hợp tìm kiếm ngẫu nhiên, các quy tắc nghiệp vụ dạng ký hiệu và việc chấm điểm ràng buộc. Điều quan trọng ở đây mang tính vận hành: công cụ tạo tự động được thiết kế cho những trường hợp bị ràng buộc rất chặt, đồng thời báo hiệu các tình huống bất khả thi thay vì che giấu lỗi tương thích.

Ràng buộc cứng

Công cụ tạo tự động tuân thủ nghiêm ngặt những ràng buộc mà nếu vi phạm sẽ làm thời khóa biểu không hợp lệ:

• một giáo viên không thể có mặt ở hai nơi cùng một lúc;
• một lớp không thể học hai tiết học cùng một lúc, trừ các nhóm nằm trong một phân vùng;
• thời gian rảnh và ràng buộc thời gian ở mức không thể sẽ chặn việc xếp tiết học;
• một phòng học tiêu chuẩn không thể chứa hai tiết học vào cùng một thời điểm;
• một phòng lớn chỉ chứa được nhiều tiết học trong giới hạn sức chứa và số lớp đã cấu hình;
• phòng học chuyên ngành, sức chứa, tài nguyên vật chất và việc di chuyển giữa các cơ sở phải luôn tương thích với nhau;
• một tiết học đã khóa thì giữ nguyên vị trí.

Ràng buộc tối ưu hóa

Các ràng buộc mềm dùng để chấm điểm và cải thiện những lời giải tìm được. Chúng không bị bỏ qua: chúng trở thành các điểm trừ mà công cụ tạo tự động tìm cách giảm bớt.

Các ví dụ thường gặp:

• thời gian rảnh hoặc ràng buộc thời gian ở mức không mong muốn đối với một giáo viên, một phòng học, một khóa học, một nhóm hay một lớp;
• điểm không tương thích về mặt sư phạm giữa các môn học, ví dụ tránh xếp một tiết thực hành trước tiết học lý thuyết tương ứng, tránh xếp giờ thể dục ngay sau một tiết học có cường độ rất cao, hoặc buộc phải theo đúng thứ tự của tiến trình dạy học;
• tránh xếp cùng một môn học hai lần trong cùng một ngày cho một lớp;
• số giờ học tối thiểu hoặc tối đa mỗi ngày hay mỗi tuần;
• sự cân đối giữa các ngày;
• giảm bớt giờ trống trong thời khóa biểu của các lớp và của giáo viên;
• số ngày có mặt của giáo viên, tùy theo thông lệ của nhà trường hoặc của quốc gia.

Tìm ra một lời giải hợp lệ là bước đầu tiên. Sau đó, việc tối ưu hóa các điểm trừ có thể trở thành phần tốn thời gian nhất của quá trình tính toán.

Khả dụng

• Thời khóa biểu theo tuần — khả dụng.
• Thời khóa biểu theo chu kỳ — khả dụng.
• Thời khóa biểu theo lịch — khả dụng, với các tiết học có ngày cụ thể và một khoảng ngày.

Phải làm gì nếu việc tạo tự động thất bại

Nếu không tìm được lời giải đầy đủ, Omniscol giữ lại thời khóa biểu tốt nhất đã tính được và để lại những tiết học không thể xếp trong danh sách thẻ post-it chưa được xếp. Khi đó bạn có thể xem xét thời khóa biểu chưa hoàn chỉnh, đọc chẩn đoán và sửa lại các ràng buộc.

Các nguyên nhân thường gặp:

• thời gian rảnh quá hạn chế (một giáo viên không còn khung giờ trống nào tương thích),
• không đủ phòng học, hoặc không có phòng học chuyên ngành nào còn trống,
• căn chỉnh nhóm không nhất quán (khối lượng giờ khác nhau giữa các nhóm được căn chỉnh),
• các điểm không tương thích quá nhiều hoặc quá chặt,
• sĩ số lý thuyết của lớp > sức chứa của mọi phòng học ứng viên.

Xem Chẩn đoán khi việc tạo thời khóa biểu thất bại.

Ấn định vị trí của một tiết học

Bạn có thể khóa vị trí của một tiết học trước khi chạy lại việc tạo tự động: khi đó công cụ tạo tự động không di chuyển tiết học ấy nữa, mà điều chỉnh những tiết học khác xung quanh. Cách này tiện để cố định những tiết học “không thể xê dịch” (chuyên gia bên ngoài đến giảng theo hợp đồng đã ấn định, kỳ thi đã định ngày, v.v.).