Năm 2007, phiên bản TKB 6.5 đã đưa vào được khái niệm các tiêu chí đánh giá thay đổi dữ liệu GV (12 tiêu chí dã nói trong các phần trước). Từ phiên bản này trở đi các lệnh tinh chỉnh dữ liệu chính như CX, Push Out, Move To sẽ có thêm bảng đánh giá kết quả thực hiện lệnh bằng các tiêu chí trên cho từng GV bị thay đổi của lệnh.

Năm 2008, phiên bản TKB 7.0 đã đưa thêm vào các tiêu chí đánh giá một TKB GV bằng cách đưa vảo tiêu chí đánh giá 1 tiết học là xấu hay tốt (10 tiêu chí) và 12 tiêu chí đánh giá định lượng và yêu cầu của GV. Cũng trong TKB 7.0 đã đưa ra khái niệm các tiêu chí Chuyển tiết tối ưu (10 tiêu chí, đã nói trong phần trước). Như vậy phải đến 2 năm sau đó, năm 2009, các công việc chuẩn bị cho việc thiết kế chính thức một thuật toán tinh chỉnh tối ưu mới được đặt ra cụ thể. Thuật toán mà chúng tôi chọn để thiết kế là thuật toán CX và DPR.

Hai thuật toán CX và DPR có nhiều điểm chung, thực chất CX là một trường hợp riêng của DPR.

Mô hình đơn giản của thuật toán DPR như sau:

Giả sử cần chuyển 1 tiết học trên thời khóa biểu của một giáo viên A từ vị trí này sang vị trí khác (do yêu cầu của A). Việc chuyển này được viết thành mô hình như sau:

P0 ---> P1 (1)

Nếu vị trí tiết học tại P1 (môn học, lớp, giáo viên) có thể chuyển ngay về P0 thì quá trình (1) sẽ kết thúc ngay:

P0 --> P1 --> P0 (2)

Nhưng thực tế không bao giờ xảy ra như vậy, do đó thể thực hiện được bài toán (1) sẽ phải kéo theo thực hiện một dây biến đổi:

P0 --> P1 --> P2 --> .... --> PN (3)

Chính xác hơn ở đoạn cuối của (3) phải viết đầy đủ là PN --> P0, tuy nhiên tôi sẽ bỏ qua cách viết này.

Như vậy bản chất của một thuật toán tinh chỉnh dữ liệu thời khóa biểu là muốn có (1) phải thực hiện (3).

Thuật toán này được gọi là "tối ưu" nếu toàn bộ các dịch chuyển trung gian Pi-1 --> Pi phải là tối ưu.

Sau một thời gian mò mẫm thử nghiệm, năm 2009, chúng tôi đã thành công trong việc thiết kế một thuật toán tinh chỉnh tối ưu như vậy. Thuật toán này là một mở rộng trực tiếp của 2 thuật toán CX, DPR và chúng tôi đặt tên thuật toán mới là OpCX/OpDPR.

Tháng 7 năm 2009, phiên bản TKB 7.5 ra đời với một thuật toán tinh chỉnh tối ưu mới: OpCX/OpDPR. Thật là kỳ diệu vì khi sử dụng thuật toán này, trên các bảng đánh giá tiêu chí mà chúng tôi đưa ra, hầu hết các đánh giá giáo viên trung gian là "Xanh" tức là Tốt lên.
OpCX/OpDPR là thuật toán tinh chỉnh tối ưu đầu tiên của Công ty School@net cũng như của Việt Nam đã thực hiện được yêu cầu sau:

- Khi thực hiện thuật toán này thành công cho 1 GV A, tất cả các giáo viên bị thay đổi thời khóa biểu khác B, C, ..., Z sẽ không bị "xấu đi", chỉ có thể bằng hoặc tốt lên.

Phần mềm TKB 7.5 ra đời với thuật toán tinh chỉnh tối ưu OpCX/OpDPR đã gây 1 tiếng vang lớn và được các nhà trường đón nhận.

Tuy nhiên hãy còn 1 thuật toán nữa chưa tối ưu được, đó là thuật toán FPR.

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

School@net