Đây là một chủ đề lớn, khó có thể nói nhanh bằng vài lời. Chỉ biết rằng con đường tối ưu hóa dữ liệu thời khóa biểu vẫn đang tiếp tục phát triển cho đến tận hôm nay.

Phần mềm TKB vẫn được liên tục phát triển từ đó đến nay:

2007: TKB 6.5

2008: TKB 7.0

2009: TKB 7.5

2010: TKB 8.0

2011: TKB 8.5

2012: TKB 9.0

Trong bài viết ngắn này tôi chỉ điểm lại những nét chính của công việc phức tạp này.
1. Thế nào là tối ưu hóa, làm đẹp thời khóa biểu

Trong bài toán xếp thời khóa biểu trong nhà trường, một trong những vấn đề phức tạp nhất là làm sao thỏa mãn được yêu cầu của tất cả các giáo viên. Mỗi giáo viên có một hoàn cảnh khác nhau, yêu cầu khác nhau, không có một tiêu chuẩn chung thống nhất nào cho điều này, do vậy bài toán này càng trở nên khó khăn cho bất cứ phần mềm nào.

Như vậy bài toán tối ưu hóa dữ liệu thời khóa biểu, làm đẹp thời khóa biểu cần phải được hiểu như thế nào?

Có nhiều cách tiếp cận vấn đề này. Sau đây là cách làm của chúng tôi.

- Chúng tôi đưa ra một số "tiêu chuẩn" dùng để đánh giá một thời khóa biểu của GV là đẹp hay không đẹp. Tất nhiên việc đưa ra các tiêu chuẩn này không phải là tuyệt đối đúng, nhưng nó sẽ phù hợp với đại đa số các GV trong nhà trường.

- Bên cạnh các tiêu chuẩn đánh giá các thời khóa biểu GV, chúng tôi còn đưa ra đưa ra thêm khái niệm "chuyển tiết tối ưu". Có thể tóm tắt ý này như sau: để làm "đẹp" một thời khóa biểu của GV cần xác định những tiết học nào cần chuyển đi, và chuyển đi đâu. Như vậy cần đánh giá tiết nào cần chuyển đi? và cần chuyển tới đâu là tối ưu nhất? Đó chính là các phác thảo đầu tiên của khái niệm tối ưu hóa thời khóa biểu mà chúng tôi đưa ra trong phần mềm.

2. Các công cụ, thước đo tối ưu thời khóa biểu

Để thực hiện các ý tướng trên chúng tôi đã lần lượt xây dựng các công cụ dùng để tính toán và thực thi các ý tưởng đã nêu. Các công cụ này không được xây dựng ngay mà được lần lượt xây dựng theo các kế hoạch phát triển của phần mềm.

Có thể liệt kê một số công cụ mà chúng tôi đã xây dựng trong phần mềm TKB tính từ phiên bản 6.0 trở lại đây:

- Công cụ đánh giá sự thay đổi thời khóa biểu của một GV. Việc đánh giá này sẽ dựa trên 12 tiêu chí, trong đó 6 tiêu chí định lượng thời khóa biểu và 6 tiêu chí dựa trên sự thỏa man các ràng buộc GV. Mục đích của công cụ đánh giá này như sau:

Giả sử sau một lệnh tinh chỉnh dữ liệu, thời khóa biểu của một giáo viên A sẽ thay đổi từ trạng thái P1 sang trạng thái P2. Công cụ đánh giá này sẽ đánh giá sự thay đổi P1-->P2 này. Kết quả trả lại là 12 tiêu chí, môi tiêu chí được đánh giá bởi 3 mức: Xanh (TKB bằng hoặc tốt lên), Đỏ (TKB xấu đi).

Tổng hợp của 12 tiêu chí sẽ chỉ ra sự thay đổi chung P1-->P2 này là Xanh (tốt lên), Vàng (trung bình) và Đỏ (xấu đi).

- Công cụ đánh giá các tiết học và đánh giá sự chuyển tiết từ một vị trí này đến vị trí khác.
Có 8 tiêu chí đánh giá 1 tiết học là "xấu" hay "tốt":

1. Tiết tạo ra tiết trống

2. Tiết duy nhất trong buổi học

3. Tiết vi phạm ràng buộc Bận, Nghỉ, Hạn chế

4. Tiết vi phạm ràng buộc không dạy

5. Tiết vi phạm ràng buộc nghỉ buổi dạy

6. Tiết vi phạm ràng buộc không dạy qua trưa

7. Tiết vi phạm điều kiện thời gian nghỉ giữa buổi

8. Tiết vi phạm ràng buộc tính chất môn học

- Công cụ đánh giá việc dịch chuyển 1 tiết trên thời khóa biểu là tối ưu hay không.
Có 10 tiêu chí đánh giá dịch chuyển tiết tối ưu như vậy:

1. Không vi phạm ràng buộc Nghỉ, Hạn chế, Bận

2. Không vi phạm ràng buộc không dạy theo tiết

3. Không vi phạm ràng buộc nghỉ các ngày cụ thể

4. Không vi phạm ràng buộc về số tiết dạy max trong ngày

5. Không vi phạm ràng buộc không dạy qua trưa

6. Không vi phạm ràng buộc dạy qua giờ nghỉ giải lao

7. Không vi phạm ràng buộc tính chất môn học

8. Không làm tăng tiết trống

9. Không làm giảm số buổi nghỉ

10. Không làm giảm số ngày nghỉ

- Công cụ đánh giá các thời khóa biểu GV. Có 12 tiêu chí đánh giá này, bao gồm:

6 tiêu chí định lượng thông tin TKB:

Số tiết trống trong một buổi học.

Tổng số tiết trống trong một tuần.

Số lượng buổi nghỉ và ngày nghỉ trong một tuần

Số lượng tiết dạy Max trong buổi

Có dạy qua trưa hay không?

6 tiêu chí đánh giá thỏa mãn ràng buộc TKB:

Số lượng các tiết bị phá vỡ ràng buộc Nghỉ, Bận, Hạn chế.

Số buổi vi phạm ràng buộc nghỉ theo tiết học.

Số buổi vi phạm ràng buộc nghỉ buổi học.

Có vi phạm ràng buộc số buổi nghỉ dạy hay không.

Số buổi vi phạm ràng buộc dạy Max trong buổi học.

Có vi phạm ràng buộc số ngày nghỉ dạy hay không.

3. Các công cụ tích hợp trong phần mềm hỗ trợ tối ưu hóa thời khóa biểu

Các công cụ có rất nhiều trong phần mềm TKB, tôi chỉ đưa ra ở đây 1 vài công cụ chức năng tiêu biểu.

- Trong tất cả các lệnh tinh chỉnh dữ liệu thời khóa biểu, trước khi thực hiện chính thức lệnh, người dùng sẽ được xem một báo cáo đặc biệt trong đó phân tích rõ sự thay đổi của từng GV trong lệnh này có là tối ưu hay không. Trong cửa sổ Report này sẽ xuất hiện các nút màu xanh, đỏ hoặc vàng để đánh giá từng giáo viên và đánh giá toàn bộ lệnh.

- Trên các thời khóa biểu giáo viên, nếu người dùng muốn thay đổi, muốn dịch chuyển 1 tiết nào đó sang vị trí khác (thao tác này được thực hiện bằng cách kéo thả chuột trên ô này), thì bây giờ người dùng sẽ nhấn giữ chuột trong một vài giây, phần mềm sẽ hiện ra các ô màu xanh là các ô mà tiết học này cần chuyển đến 1 cách tối ưu nhất. Công cụ này sẽ giúp ích rất nhiều cho các GV làm nhiệm vụ xếp thời khóa biểu.

Bên cạnh tất cả các công cụ vừa trình bày trên, cái cốt lõi nhất của bài toán tối ưu, làm đẹp thời khóa biểu nằm tại các thuật toán tinh chỉnh dữ liệu chính của phần mềm bao gồm CX, DPR và FPR. Trong bài viết sau tôi sẽ nói về quá trình nâng cấp các thuật toán này để hỗ trợ cho bài toán tối ưu thời khóa biểu của phần mềm TKB.

Bùi Việt Hà, Công ty Công nghệ Tin học Nhà trường

School@net