Tuy nhiên một trong những vấn đề quan trọng nhất của các phát triển này chính là các thuật toán tinh chỉnh dữ liệu thời khóa biểu chính của phần mềm. Đó là các thuật toán tinh chỉnh:

CX - Conditional eXecution - xếp có điều kiện.

DPR - Dynamic Position Replacement - dịch chuyển vị trí động.

FPR - Fix Position Replacement - dịch chuyển vị trí cố định.

Đây là 3 thuật toán tinh chỉnh dữ liệu chính của phần mềm TKB mà tôi đã từng nhắc đến trong các bài viết trước đây. Chúng đóng vai trò quan trọng không những trong chức năng xếp tự động 100% thời khóa biểu (lệnh SF) mà còn trong toàn bộ việc tinh chỉnh dữ liệu sau khi xếp xong thời khóa biểu.

Một trong những bài toán đặt ra chính của vấn đề tối ưu hóa thời khóa biểu là:

Khi cần tinh chỉnh, điều chỉnh dữ liệu cho một giáo viên A (việc này sẽ làm cho A tốt lên), sẽ có một số giáo viên khác bị thay đổi theo, ví dụ các giáo viên bị thay đổi là B, C, ..., Z. Có cách nào để kiểm soát được sự thay đổi dữ liệu thời khóa biểu của các giáo viên B, C, ..., Z này? Có hay không một thuật toán mà sau khi thay đổi giáo viên A nhưng các giáo viên B, C, ...., Z không bị xấu đi?

Như chúng ta đã biết bài toán trên thoạt đầu có vẻ như không tưởng và mâu thuẫn. Trong mô hình phức tạp của bài toán xếp thời khóa biểu luôn tuân theo nguyên tắc bù trừ: để giáo viên A tốt lên, các giáo viên B, C, ..., Z phải bị xấu đi để cân bằng. Vậy bài toán mà chúng tôi đặt ra ở trên liệu có khả thi hay không? Hay cần hiểu bài toán này theo một nghĩa khác?

Cách giải quyết của chúng tôi trong vấn đề này như sau:

- Chúng tôi đã xây dựng được các tiêu chí để đánh giá việc di chuyển 1 tiết trên thời khóa biểu có phải là tối ưu hay không. Có 10 tiêu chí để đánh giá như vậy.

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ỉ

Theo cách xây dựng của chúng tôi việc di chuyển 1 tiết học được coi là “tốt” hay “tối ưu” nếu thỏa mãn tất cả 10 tiêu chí trên. Nếu chỉ không thỏa mãn 1 trong 10 tiêu chí trên cũng sẽ bị đánh giá việc chuyến tiết này là “không tối ưu”.

- Khi thực hiện lệnh tinh chỉnh dữ liệu thời khóa biểu, ví dụ: dịch chuyển giáo viên A. Việc tinh chỉnh này sẽ được thuật toán hóa và kéo theo thực hiện N lệnh di chuyển tiết khác, ví dụ cụ thể như sau:

Thay đổi 1: ô thời khóa biểu p1 được dịch chuyển vị trí.

Thay đổi 2: ô thời khóa biểu p2 được dịch chuyển vị trí.
.....

Thay đổi N: ô thời khóa biểu pN được dịch chuyển vị trí.

Như vậy bài toán “tinh chỉnh tối ưu hóa” được đặt ra ở trên có thể phát biểu như sau: có hay không một thuật toán mà sau khi thay đổi giáo viên A theo ý muốn thì tất cả các thay đổi tương ứng của các vị trí p1, p2, ..., pN như trên vẫn là “tối ưu”? Như vậy bài toán được đặt ra rất rõ ràng, correct và hoàn toàn nằm trong phạm vi của ngôn ngữ thuật toán. Và chúng tôi đã tìm cách giải quyết theo hướng đi này.

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

School@net