Trên thế giới bài toán Thời khóa biểu (Time Table problem) đã được rất nhiều các nhà khoa học quan tâm. Đã có hơn 1000 bài báo khoa học được viết về đề tài này, trong đó có khoảng 300 luận án Tiến sĩ và Thạc sĩ được bảo vệ xung quanh bài toán Thời khóa biểu. Tại Việt Nam cũng đã có một số nhà khoa học nghiên cứu và bảo vệ thành công các luận án về bài toán thời khóa biểu. Các trường đại học có quan tâm và nghiên cứu nhiều đến bài toán này phải kể đến Đại học Bách khoa Hà Nội, Học viện KTQS, Đại học Tổng hợp TPHCM, Đại học Cần Thơ.

Nhưng có một thực tế rất "vui" là tại Việt Nam cũng như nhiều nước trên thế giới, việc xếp Thời khóa biểu phần lớn đều được thực hiện bằng.... tay!? Có rất ít các phần mềm xếp Thời khóa biểu được viết và sử dụng tại Việt Nam cũng như trên Thế giới. Về các phần mềm Thời khoa biểu của nước ngoài phải kể đến 2 phần mềm nổi tiếng nhất hiện nay là Mimoza (Đan Mạch) dùng cho các trường đại học và phần mềm gp-Utis dùng cho các trường phổ thông. Phần mềm gp-Utis của một nhóm các nhà khoa học CHLB Đức viết với lịch sử hơn 30 năm (từ 1970) và nay đã trở thành một trong các phần mềm hỗ trợ xếp Thời khóa biểu nổi tiếng nhất thế giới, đặc biệt là Châu Âu. Ví dụ tại riêng nước Anh, phần mềm này hiện đang được sử dụng tại gần 12 ngàn trường phổ thông.

Tại Việt Nam hiện tại cũng đang có một vài phần mềm Thời khóa biểu "trôi nổi" trên thị trường. Xin được nhắc đến ở đây: phần mềm Skola (phần hỗ trợ Thời khóa biểu chỉ là một chức năng nhỏ bé của Skola), phần mềm CITDTKB do trung tâm CITD viết, phần mềm Schedule do CadPro viết. Ngoài ra còn có khá nhiều các phần mềm xếp Thời khóa biểu được viết bởi các nhóm chuyên gia Tin học như Trung tâm Tin học Bộ Xây dựng, Đại học Văn Lang - TPHCM, Khoa CNTT - HVKTQS, Khoa CNTT - Đại Học Bách khoa Hà Nội,... Tuy nhiên tất cả các phần mềm này đều chưa (hoặc hầu như chưa) thực sự được sử dụng tại bất cứ một trường phổ thông nào tại Hà Nội, TPHCM, chưa nói đến các tỉnh thành phố khác.

Phần mềm Hỗ trợ xếp Thời khóa biểu TKB là một trong các phần mềm Thời khóa biểu đầu tiên xuất hiện ở Việt Nam. TKB là phần mềm chuyên nghiệp với hơn 15 năm kinh nghiệm: Năm 1989: phiên bản TKB 2.1 lần đầu tiên ra đời. Tháng 12/1999 phiên TKB 3.0 , tiếp theo là các phiên bản TKB 3.5 (2000), TKB 4.0 (2001), TKB 4.5 (2002), TKB 4.8 (2003), TKB 5.0 (2004) và tháng 3/2005 phiên bản TKB 5.5 đã được công bố với một loạt tính năng mới. Cho đến nay phần mềm TKB đã được hơn 1000 trường trên toàn quốc đang sử dụng, đặc biệt năm 2004 phần mềm TKB đã được trao giải sản phẩm ưa chuộng nhất năm 2004 do bạn đọc của tạp chí PC Word bình chọn.

II. Tính phức tạp của bài toán xếp Thời khóa biểu

Bài toán Thời khóa biểu là một trường hợp riêng của bài toán xếp lịch được xếp vào hàng các bài toán khó không có thuật giải hữu hiệu trong Tin học. Tuy nhiên xét riêng trong phạm vi nhà trường phổ thông Việt Nam với số lượng lớp và giáo viên không lớn (xấp xỉ 100) cộng với sức mạnh của các máy tính hiện đại, vấn đề phức tạp của bài toán Thời khóa biểu không nằm ở thuật toán.

Tính phức tạp của bài toán xếp Thời khóa biểu nói chung và tại Việt Nam nói riêng nằm ở các qui định, ràng buộc môn học chặt chẽ, ở các ràng buộc nghỉ và không nghỉ của giáo viên hết sức phức tạp, đa dạng, thậm chí mâu thuẫn lẫn nhau. Chính điều này đã làm cho việc xếp Thời khóa biểu tại các trường Phổ thông ngày càng trở nên thời sự.

Nếu như các vấn đề về tối ưu hóa Thời khóa biểu, về các điều kiện ràng buộc giáo viên không đặt ra thì bài toán Thời khóa biểu trường phổ thông có lẽ đã không trở nên quá phức tạp và khó như hiện nay. Chính vấn đề "tính người" trong bài toán Thời khóa biểu hiện nay đang là một cản trở rất lớn cho việc nghiên cứu và ứng dụng các phần mềm cụ thể cho bài toán này trong nhà trường.

III. Phần mềm TKB 5.5

Phiên bản TKB 5.5 ra đời tháng 3-2005 là phiên bản mới nhất, có nhiều đặc tính đột phá nhất so với tất cả các phiên bản TKB trước đây và so với tất cả các phần mềm Thời khóa biểu hiện có ở Việt Nam. Trong khi thiết kế tổng thể lại cho phiên bản TKB 5.5 và chuẩn bị cho các phiên bản tiếp theo, chúng tôi đã nghiên cứu tương đối kỹ các đặc thù và chức năng chính của các phần mềm Thời khóa biểu nổi tiếng thế giới như gp-Utis, Mimoza, TTmaker, NAK,... Bên cạnh đó sự đóng góp ý kiến chân thành và rất sâu sắc của hơn 100 trường đang sử dụng phần mềm TKB là một nguồn thông tin quí giá đối với chúng tôi.

1. Quan điểm thiết kế TKB

Phần mềm TKB được thiết kế và xây dựng dựa trên các quan điểm chính sau:

- TKB phải là một phần mềm chuyên nghiệp về Thời khóa biểu. Chúng tôi không dự định đưa kèm vào phần mềm TKB các chức năng quản lý khác của nhà trường như Nhân sự, Điểm học sinh, Vật tư,... Bản thân bài toán Thời khóa biểu đã quá phức tạp và riêng nó xứng đáng dành riêng một phần mềm nghiêm chỉnh.

- TKB chỉ là một công cụ hỗ trợ, giúp người lập Thời khóa biểu trong công việc của mình. Phần mềm không được thay thế con người, phần mềm chỉ đưa ra các phương án lựa chọn khác nhau của thời khóa biểu. Quyền quyết định cuối cùng bao giờ cũng thuộc về con người, tức người xếp thời khóa biểu của nhà trường. Đây là quan điểm xuyên suốt của chúng tôi khi thiết kế phần mềm TKB từ hơn 10 năm nay.

- Chúng tôi coi Thời khóa biểu là một tổng hòa, một thỏa hiệp giữa các điều kiện ràng buộc của giáo viên trong nhà trường. Hay nói cách khác TKB lấy ràng buộc giáo viên làm khâu đột phá chính trong thiết kế của mình. Các ràng buộc giáo viên vừa phong phú, đa dạng, mâu thuẫn lẫn nhau, không thống nhất và không chuẩn hóa được đã tạo nên đặc thù rất "thời khóa biểu", rất "con người" riêng biệt của Việt Nam.

2. Phần mềm TKB là một công cụ hỗ trợ

Phần mềm TKB được viết trên một ngôn ngữ bậc cao với mục đích tạo ra một công cụ hỗ trợ thật sự cho các nhà trường trong công việc xếp Thời khóa biểu. Phần mềm TKB được chạy độc lập không phụ thuộc vào bất cứ một phần mềm có bản quyền nào khác (ví dụ như Foxpro hay Access). Khi đã cài đặt phần mềm TKB vào máy tính, nó hoạt động như một công cụ và ta có thể khởi tạo, làm việc đồng thời với nhiều Thời khóa biểu của nhiều trường cùng một lúc. Đã có nhiều giáo viên sử dụng phần mềm TKB để chuyên đi "xếp TKB thuê" cho các trường khác.

3. Tính năng mạnh

Phần mềm TKB 5.5 có những tính năng mạnh đặc biệt sau đây:

- Chương trình nhỏ, gọn (chương trình khoảng 2 MB), chạy trên mọi platform 32-bit của Microsoft như Windows 95/98/NT/2000. Yêu cầu bộ nhớ chỉ là 16M, ổ đĩa cứng 5M rỗng.

- Cho phép làm việc với các trường có 600 lớp học (300 sáng và 300 chiều), 500 giáo viên với hai ca học Sáng, Chiều.

- Chương trình hỗ trợ mạnh các yêu cầu sư phạm môn học (15) và ràng buộc giáo viên (20). Trong phiên bản TKB 5.5, các điều kiện này được tăng lên đáng kể so với các phiên bản trước đây của TKB và vượt xa tất cả các phần mềm khác hiện có trên thị trường.

- Các lựa chọn in của chương trình thật sự phong phú: phiên bản TKB 5.5 có thể in kết quả TKB toàn trường, lớp và giáo viên theo hàng trăm mẫu in đa dạng khác nhau. Không những thế các mẫu kết quả này có thể chuyển ngay sang dạng Excel, HTML và đưa lên mạng Intranet/Internet để quản lý từ xa. Phiên bản TKB 5.5 cho phép có thể in được trên 13000 dạng, mẫu TKB khác nhau theo 5 dạng: TKB toàn trường theo lớp, TKB toàn trường theo giáo viên, TKB từng lớp, TKB từng giáo viên và Bảng Phân công giảng dạy giáo viên.

- Bộ công cụ hỗ trợ xếp Thời khóa biểu của TKB 5.5 hết sức phong phú bao gồm các công cụ hiệu chỉnh dữ liệu bằng tay, các công cụ tìm kiếm, tra cứu thông tin, kiểm tra mâu thuẫn dữ liệu, phân tích, thống kê, đánh giá và lựa chọn các thời khóa biểu. Và đặc biệt các công cụ mô phỏng tư duy xếp Thời khóa biểu lần đầu tiên được thiết kế thử nghiệm trong bản 5.5 sẽ làm cho TKB trở nên vô cùng hữu ích trong việc hỗ trợ để tạo ra các sản phẩm hợp lý cho các nhà trường.

- Chức năng xếp tự động hoàn toàn thời khóa biểu của TKB được coi là khá mạnh. Trên thực tế với hầu hết các dữ liệu thật, chức năng này (Auto Execute) đã hoàn thiện được 100% dữ liệu Thời khóa biểu. Đây là một con số hết sức cao theo đánh giá của các chuyên gia Tin học cũng như các nhà trường.

4. Công cụ mạnh

Các công cụ hỗ trợ xếp Thời khóa biểu có thể được phân loại như sau:

- Các công cụ nhập dữ liệu gốc bao gồm: Danh sách các Lớp, Môn học, Giáo viên, Bảng PCGD, ràng buộc Môn và Giáo viên và các dữ liệu hệ thống khác của chương trình.

- Các công cụ cho phép xem, hiển thị thông tin Thời khóa biểu theo các dạng, màn hình, bảng biểu khác nhau.

- Các chức năng cho phép hiệu chỉnh, điều chỉnh trực tiếp vào từng ô của Thời khóa biểu một cách thuận tiện chỉ bằng cách gõ phím nóng, kích và rê chuột trên màn hình,... Công việc điều chỉnh này lại được thực hiện trên những màn hình dữ liệu khác nhau tạo nên sự đa dạng và phong phú giúp người sử dụng có nhiều lựa chọn tuỳ thuộc vào thói quen và khả năng tư duy của họ. Ví dụ riêng các thao tác điều chỉnh trực tiếp tại một ô (Cell) của Thời khóa biểu trong TKB có thể thực hiện dưới 5 dạng màn hình khác nhau.

- Các công cụ kiểm tra mâu thuẫn ràng buộc ban đầu của Thời khóa biểu. TKB có 4 lệnh kiểm tra rất mạnh: Kiểm tra bảng PCGD, kiểm tra dữ liệu từng Giáo viên, kiểm tra từng Lớp và kiểm tra Toàn trường. Với các công cụ này, người xếp Thời khóa biểu có khả năng phát hiện những mâu thuẫn ràng buộc rất sâu sắc tồn tại trong Thời khóa biểu trường mình, kịp thời điều chỉnh và loại bỏ chúng (đồng thời thông báo cho giáo viên và Ban giám hiệu biết). Trong nhiều trường hợp, chính các mâu thuẫn TKB này đã làm cho việc xếp TKB khó lên rất nhiều và không thể thực hiện được.

- Nhóm các công cụ tự động xếp Thời khóa biểu. Các lệnh này bao gồm việc xếp tự động ở qui mô Toàn trường hoặc tại một TKB Lớp hoặc một TKB Giáo viên.

- Các công cụ "tư duy" xếp Thời khóa biểu. Nhóm các công cụ này là đặc biệt mới và chúng tôi hy vọng sẽ còn phát triển nhiều hơn nữa theo hướng này trong tương lai. Xem kỹ hơn về các công cụ này trong phần sau.

- Các công cụ đánh giá Thời khóa biểu. Đây cũng là một đặc điểm mới nổi bật của phần mềm TKB. Lần đầu tiên, phần mềm TKB sẽ đưa ra các tiêu chuẩn để đánh giá một TKB Lớp hoặc Giáo viên là "tốt" hay "xấu".

- Các công cụ cho phép cài đặt lựa chọn và in kết quả Thời khóa biểu ra máy in hoặc ra file dưới dạng HTML. Có 4 dạng TKB chính cho phép in là TKB từng Lớp, TKB từng Giáo viên, TKB toàn trường theo lớp và TKB toàn trường theo giáo viên. Mỗi dạng TKB như vậy lại có rất nhiều phương án lựa chọn cách thể hiện dữ liệu khi in ra làm cho lệnh in Thời khóa biểu của phần mềm TKB trở nên rất mạnh.

Nắm được thành thạo các công cụ trên của phần mềm TKB, người xếp Thời khóa biểu với sự trợ giúp của máy tính, cụ thể là TKB sẽ tự nhiên tạo cho bản thân một kiểu "tư duy" mới khi xếp Thời khóa biểu. "Tư duy" mới này sẽ khác biệt so với kiểu "tư duy xếp bằng tay" cũ, sẽ đơn giản hơn, tiện dụng hơn, tốt hơn và điều quan trọng nhất, nó làm giảm nhẹ công sức lao động của người xếp Thời khóa biểu và với thời gian nhanh hơn. Đó chính là mục đích duy nhất của phần mềm hỗ trợ xếp Thời khóa biểu TKB.
Bài toán Thời khóa biểu và phần mềm hỗ trợ xếp Thời khóa biểu - Định huớng sản phẩm Tin học trong nhà trường

School@net