Cong ty Cong Nghe Tin hoc Nha truong http://www.vnschool.net
Lịch sử phần mềm xếp thời khóa biểu TKB (7): các thuật toán và lệnh tinh chỉnh dữ liệu
24/12/2012

thời khóa biểuSau khi hoàn thành phiên bản TKB 4.0, công ty School@net đã mở rộng tuyển thêm nhiều nhân viên lập trình cho dự án phần mềm TKB. Vào thời kỳ những năm 2000-2002 đội lập trình phần mềm TKB có 4-5 người.



Với phiên bản TKB 4.0 mới chỉ có các chức năng: xếp tự động (95-99%), dịch chuyển tiết trên thời khóa biểu bằng DPR hoặc FPR.

Như vậy vào thời điểm này vẫn còn có nhiều vấn đề lớn của bài toán xếp thời khóa biểu chưa được giải quyết:

- Sau khi đã xếp tự động được 95-99%, sẽ còn lại một vài tiết trống cần xếp nốt của thời khóa biểu. Làm thế nào để xếp nốt được các tiết này để hoàn thiện được 100% thời khóa biểu.

- Đó chính là bài toán xếp 100% thời khóa biểu mà vào năm 2000 phần mềm TKB chưa giải quyết được.

Chúng ta đều biết là việc xếp nốt một vài tiết còn lại đó bằng tay là rất khó.

Vì vậy nhiệm vụ tiếp theo của phần mềm TKB vào thời kỳ đó là tiếp tục tìm kiếm các chức năng, thuật toán để làm sao có thể xếp nốt được một vài tiết cuối cùng, còn lại của thời khóa biểu. Ở đây chưa nói đến bài toán tinh chỉnh, làm đẹp dữ liệu thời khóa biểu.

Thời kỳ này tôi đã tích cực cùng tham gia thiết kế và suy nghĩ về các công cụ mới này của phần mềm TKB.

Để chuẩn bị cho việc hoàn thành phiên bản tiếp theo TKB 4.5 vào tháng 6 năm 2001, tôi đã cùng đội lập trình dự án phần mềm TKB chốt lại được 3 lệnh tinh chỉnh dữ liệu quan trọng sau:

1. Lệnh Move To. Lệnh Di chuyển tiết.

2. Lệnh Push Out. Lệnh giải phóng 1 tiết.

3. Lệnh CX (Conditional eXecution). Lệnh xếp có điều kiện 1 tiết.

Đây là 3 lệnh, 3 chức năng quan trọng nhất của nhóm các lệnh tinh chỉnh dữ liệu thời khóa biểu được thiết kế từ năm 2001 và vẫn còn nguyên giá trị cho đến tận ngày hôm nay. Xin nhắc lại ở đây ý nghĩa chính của 3 lệnh này.

1. Move To. Lệnh này có chức năng dịch chuyển 1 tiết học trên thời khóa biểu (GV, Lớp) từ vị trí ban đầu P1 đến vị trí đích P2.

2. Push Out. Lệnh này có chức năng giải phóng 1 ô dữ liệu P trên thời khóa biểu. Lệnh sẽ chuyển tiết học đang có tại vị trí P đến 1 vị trí khác (không quan trọng là chuyển đến đâu, mà quan trọng là giải phóng ô hiện thời trên thời khóa biểu).

3. CX. Lệnh có chức năng xếp bằng được 1 tiết chưa xếp vào một thời khóa biểu cho trước, không quan trọng là xếp vào đâu, miễn là xếp được tiết này. Vì vậy lệnh được gọi là Xếp tiết có điều kiện.

Với hai lệnh Push Out, CX, việc xếp nốt một số tiết còn lại của một thời khóa biểu trở nên dễ dàng hơn bao giờ hết. Với lệnh Move To, việc tinh chỉnh dữ liệu sau khi xếp xong thời khóa biểu cũng được tiến hành chỉ bằng các thao tác kéo thả.

Với việc đưa ra các lệnh tinh chỉnh Move To, Push Out, CX, bài toán xếp thời khóa biểu bằng phần mềm TKB trở nên rất sáng sủa, rõ ràng. Tại thời điểm năm 2001, vẫn chỉ có hai thuật toán tinh chỉnh chính là DPR và FPR dùng chung cho cả 3 lệnh Move To, Push Out và CX. Phiên bản TKB 4.5 dừng lại ở các thuật toán này.

Sang năm 2002, tôi đã thiết kế thêm 1 thuật toán nữa đặt tên là CX (trùng với lệnh CX vừa nói ở trên). Thuật toán này là một thu gọn của thuật toán DPR trên 1 lớp học. Việc đưa thuật toán CX vào hoạt động đã làm phong phú hơn rất nhiều cho công việc tinh chỉnh dữ liệu của phần mềm. Đặc biệt trong thuật toán CX, người dùng có thể tương tác với phần mềm và lựa chọn nhiều phương án ngay trên màn hình máy tính. Thuật toán CX dễ hiểu, hiệu quả vì nó mô tả quá trình mà các giáo viên trên thực tế hay đổi tiết cho nhau.

Năm 2003, phiên bản TKB 4.8 ra đời đã hoàn thiện toàn bộ các công cụ tinh chỉnh dữ liệu thời khóa biểu và các thuật toán tinh chỉnh. Đó là:

- Các lệnh tinh chỉnh dữ liệu: CX, Push Out, Move To.

- Các thuật toán tinh chỉnh dữ liệu: DPR, FPR, CX.

Với bộ các công cụ này, cộng với một loạt các công cụ mạnh khác cùng đưa ra vào thời gian đó, đến năm 2003, TKB đã trở thành phần mềm rất nổi tiếng tại Việt Nam, được sử dụng tại gần 1000 trường phổ thông vào thời gian đó.

Vào khoàng thời gian mà phiên bản TKB 4.8 ra đời (2002), tôi đã bắt đầu hình thành một ý tưởng mới rất đặc biệt và quan trọng, đó là ý tưởng làm sao có thể có được một lệnh xếp tự động 100% dữ liệu thời khóa biểu. Vào thời kỳ đó ý tưởng này thật sự táo bạo vì lúc đó trên thế giới cũng chưa có bất cứ một phần mềm xếp thời khóa biểu nào đưa ra được thuật toán xếp trọn vẹn một thời khóa biểu. Bài toán xếp thời khóa biểu luôn được coi là bài toán cực khó và không bao giờ có một lời giải 100%. Xếp thời khóa biểu 100% là một ước mơ quá xa vời với những người nghiên cứu cũng như làm phần mềm thời khóa biểu.

Bùi Việt Hà, Công ty Công nghệ Tin học Nhà trường
URL của bài viết này::http://www.vnschool.net/modules.php?name=Sanpham&file=article&sid=6911
© Cong ty Cong Nghe Tin hoc Nha truong contact: sales@schoolnet.vn