Cong ty Cong Nghe Tin hoc Nha truong http://www.vnschool.net

BÀI TOÁN THỜI KHOÁ BIỂU & PHẦN MỀM XẾP THỜI KHOÁ BIỂU
07/02/2006

Bài toán xếp Thời khóa biểu nói chung và vấn đề xếp Thời khóa biểu cho Nhà trường phổ thông nói riêng luôn là một bài toán khó, mang tính khoa học đồng thời tính thực tiễn cũng rất cao. Riêng đối với môi trường Việt Nam, đặc biệt trong nhà trường phổ thông, từ lâu việc xếp thời khóa biểu đã trở thành một vấn đề có tính thời sự, một bài toán gây được sự chú ý, quan tâm của nhiều người.
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ê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, ...

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 giáo viên không đặt ra thì bài toán Thời khóa biểu có lẽ đã không trở nên quá phức tạp và khó như hiện nay.

Phần mềm TKB của công ty School@net đượ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.

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.


URL của bài viết này::http://www.vnschool.net/modules.php?name=TKB&file=article&sid=35

© Cong ty Cong Nghe Tin hoc Nha truong contact: sales@schoolnet.vn