• Giới thiệu
• Cấu trúc tập tin
• Tiêu chí đánh giá chất lượng
• Giải thuật
• Thực nghiệm
• Screenshots

Giới thiệu

Thuật toán giúp tự động sắp xếp thời khóa biểu THPT cho học sinh và giáo viên. Chất lượng của thời khóa biểu được đánh giá dựa trên nhiều ràng buộc cứng và mềm dựa trên dữ liệu thực tế. Đây là thuật toán được cài đặt hỗ trợ cho bài báo khoa học của học viên cao học Nguyễn Hồ Thiên Đăng và TS. Phan Tấn Quốc.

Cấu trúc tập tin

Chương trình chính: main.cpp

Input Files:

(Dữ liệu mẫu - Trường THPT Ngô Quyền, Q.7, TP.HCM)

PC_HK1.txt PC_HK2.txt (Danh sách phân công của học kì I và II).

cấu trúc file: <Mã PC> <Lớp> <Môn> <Mã GV> <Số Tiết> <Cụm>
vd: PC001 10A Anh GV1024 3 2

Output Files:

• TKB của lớp: TKB_lop.txt
• TKB của gv: TKB_gv.txt
• Vi phạm của lớp: VP_lop.txt
• Vi phạm của gv: VP_gv.txt
• Vi phạm chi tiết: VP_chitiet.txt
• Vi phạm tổng: VP_tong.txt
• Số liệu về điểm vi pham (Cải Thiện 2): stat.txt

Tiêu chí đánh giá chất lượng

Chất lượng của một thời khóa biểu thể hiện qua thời khóa biểu của các lớp học và thời khóa biểu của mỗi giáo viên. Việc đánh giá chất lượng một thời khóa biểu là công việc khó khăn và thông thường giáo viên sẽ đánh giá dựa vào thông tin thời khóa biểu có vi phạm các ràng buộc của bài toán

Danh sách các điều kiện ràng buộc

Chi tiết: Chi tiết ràng buộc

Trọng số các vi phạm ràng buộc cứng và ràng buộc mềm

Công thức điểm vi phạm (càng nhỏ càng tốt)

Điểm vi phạm dựa vào hệ số vi phạm và số lần vi phạm của từng ràng buộc.

Giải thuật

• Tiền xử lý: Khởi tạo trạng thái bắt đầu cho TKB lớp và giáo viên theo các tiêu chí ưu tiên.
• Cải Thiện 1: Làm gọn TKB và Thêm PC chưa xếp (không quan tâm đến điểm vi phạm, có thể làm tăng hoặc giảm điểm vi phạm)
• Cải Thiện 2: Làm giảm điểm vi phạm
• (Optional): Khi chạy Cải Thiện 1 và Cải Thiện 2 xong mà vẫn còn phân công chưa xếp thì lặp lại Cải Thiện 1 và Cải Thiện 2.

Thực nghiệm

Bộ dữ liệu mẫu

Với dữ liệu mẫu (dữ liệu thực tế được lấy từ Trường THPT Ngô Quyền, Q.7, TP.HCM, 2019 - 2020)

PC_HK1.txt: Thời khóa biểu học kì I của 3 khối lớp 10, 11, 12.

PC_HK2.txt: Thời khóa biểu học kì II của 3 khối lớp 10, 11, 12.

Bảng thông số các bộ dữ liệu thực nghiệm

Kết quả

So sánh kết quả chạy của giải thuật với kết quả mẫu (Thời khóa biểu thật của trường)

Thực nghiệm chạy 10 lần với mỗi học kì.

Bảng thực nghiệm Học kì I.

Bảng thực nghiệm Học kì II

Bảng kết quả thực nghiệm

Screenshots