Cong ty Cong Nghe Tin hoc Nha truong http://www.schoolnet.vn
Phần I. Về bài toán xếp Thời khóa biểu nhà trường
11/09/2006

Bùi Việt Hà, Công ty Công nghệ Tin học Nhà trường.
Email: habv@vnschool.net

Bài toán xếp Thời khóa biểu đã từ lâu trở thành một bài toán nổi tiếng và thu hút được sự quan tâm của rất nhiều nhà nghiên cứu, nhiều chuyên gia trong các lĩnh vực liên quan. Sự "nổi tiếng" của bài toán này không chỉ được đo bởi độ phức tạp của vấn đề, mà còn ở tính thực tiễn, khả năng áp dụng rất cao trên thực tế. Bất cứ một nhà trường nào, thời khóa biểu học tập của học sinh và giảng dạy của giáo viên đã và luôn là bộ xương sống cơ bản nhất kết nối hầu như toàn bộ các hoạt động của nhà trường. Chính vì lẽ đó bài toán xếp Thời khóa biểu trở thành một trong những vấn đề chính và quan trọng vào bậc nhất của mỗi nhà trường.


Vì sao bài toán xếp Thời khóa biểu lại trở thành một bài toán khó như vậy?

Cái gì là cốt lõi nhất tạo nên sự trở ngại và khó khăn của công việc xếp Thời khóa biểu trong một nhà trường?

Có phải độ phức tạp tính toán NP-đầy đủ là nguyên nhân chính của việc rất khó viết phần mềm mô phỏng việc xếp Thời khóa biểu trên máy tính?

Tư duy xếp Thời khóa biểu "bằng tay" là gì?

Cần hiểu rõ chính xác thế nào là một bài toán quản lý và hỗ trợ xếp Thời khóa biểu.

Những câu hỏi trên đây đã và đang đặt ra tại các Phòng Đào tạo của các nhà trường Việt Nam. Trong báo cáo này chúng tôi sẽ cố gắng phân tích mô hình bài toán xếp Thời khóa biểu tổng quát và các đặc thù chính của các nhà trường Việt Nam. Từ các phân tích đó sẽ đưa ra một cách tiếp cận chung cho việc viết phần mềm cho các nhà trường hỗ trợ công việc xếp Thời khóa biểu đồng thời thể hiện chúng trong các quan hệ tổng thể của công việc quản lý đào tạo nhà trường.

Phần mềm Thời khóa biểu tại Việt Nam

Năm 1986-1987, một nhóm các chuyên gia máy tính tại khoa Toán HVKTQS đã bắt đầu nghiên cứu bài toán xếp Thời khóa biểu mô hình trường Đại học. Mô hình được tiến hành thử nghiệm lúc bấy giờ là trường Đại học Bách khoa Hà Nội. Khi mới triển khai công trình này, toàn bộ việc lập trình được tiến hành trên FORTRAN và chạy trên các máy tính IBM lớn đặt tại Trung tâm máy tính quân đội thành phố HCM. Năm 1988, nhóm đã quyết định chuyển việc lập trình sang máy tính cá nhân. Tháng 8/1988 lần đầu tiên một phần mềm hỗ trợ xếp Thời khóa biểu đã xếp thành công một Thời khóa biểu cụ thể của trường Đại học Bách khoa Hà Nội. Thành công này đã được mời báo cáo tại Hội nghị Toán học toàn quốc tổ chức tại Đại học Bách khoa tháng 12/1988. Năm 1989, Phòng Huấn luyện HVKTQS đã giao cho một nhóm cán bộ thuộc khoa Toán viết một phần mềm hỗ trợ xếp Thời khóa biểu cho HVKTQS. Phần mềm này hoàn thành tháng 8/1989 và đã được sử dụng tại HVKTQS trong suốt hơn 10 năm sau đó. Năm 1991, nhóm tác giả của các công trình trên đã cho ra đời phiên bản phần mềm TKB 2.1 dùng cho các nhà trường phổ thông. Năm 1998, Công ty Công nghệ Tin học Nhà trường School@net được thành lập đã lập tức quay trở lại phát triển phần mềm TKB dành cho các nhà trường phổ thông và phiên bản thương mại đầu tiên của một phần mềm Thời khóa biểu tại Việt Nam ra đời tháng 12/1999. Phần mềm TKB đã được liên tục nâng cấp, bản hiện thời là 6.0 đã được hơn 1000 nhà trường phổ thông của Việt Nam sử dụng. Tháng 7-2006, công ty School@net sẽ công bố phiên bản mới nhất TKB 6.0 hỗ trợ hoàn toàn mô hình phòng học bộ môn và đa năng cho các nhà trường phổ thông của Việt Nam. Năm 2002, công ty School@net quyết định quay lại nghiên cứu và phát triển phần mềm hỗ trợ xếp Thời khóa biểu cho các trường Đại học, Cao đẳng và THCN. Phiên bản TKBU 1.0 đã hoàn thành và bắt đầu triển khai thực tế tại HVKTQS từ tháng 3-2004. Hiện tại công ty đang hoàn thiện phiên bản TKBU 2.0 phương án Thời khóa biểu tổng quát cho các nhà trường Đại học và Cao đẳng tại Việt Nam.

Phần mềm Thời khóa biểu trên Thế giới

Một thực tế rất ngạc nhiên rằng trên thế giới tồn tại không nhiều các phần mềm hỗ trợ xếp Thời khóa biểu như chúng ta vẫn nghĩ. Khoảng những năm 2000, khi chúng tôi lùng sục trên Internet để tìm kiếm, số lượng các phần mềm xếp Thời khóa biểu là dưới một bàn tay. Đến năm nay số lượng các phần mềm dạng này có tăng lên nhưng không nhiều, khoảng 20 phần mềm. Có lẽ rằng bài toán xếp Thời khóa biểu cho các nhà trường ở đâu cũng "khó" như nhau không phân biệt Việt Nam hay thế giới. Theo như chúng tôi được biết thông qua một số bạn bè đang giảng dạy tại các trường Đại học ở Mỹ thì đa số bên các nước này người ta vẫn xếp Thời khóa biểu bằng tay.

Tại Việt Nam, con số khoảng 1000 trường phổ thông đã và đang dùng phần mềm xếp Thời khóa biểu là quá nhỏ so với tổng số hơn 20,000 trường phổ thông trên toàn quốc. Còn tại các trường Đại học, Cao đẳng hay THCN, hầu hết vẫn xếp bằng tay! Sau đây là một vài phần mềm được giới thiệu là khá nổi tiếng trên Thế giới:

- Phần mềm Mimosa tại địa chỉ http://www.mimosasoftware.com (Đan mạch). Phần mềm này dành cho các trường Đại học, Cao đẳng và theo quảng cáo đã được sử dụng tại 49 quốc gia trên thế giới. Phần mềm này chỉ cho phép xếp Thời khóa biểu theo Lớp tín chỉ (Courses) và hầu như không thể áp dụng tại Việt Nam. Có thể download miễn phí bản thu gọn của phần mềm này tại địa chỉ trên.

- Phần mềm GP-UNTIS (CHLB Đức) có tại địa chỉ: http://www.grupet.at, phần mềm hỗ trợ xếp Thời khóa biểu chủ yếu cho các nhà trường phổ thông do công ty Gruber&Petters phát triển. Nhóm Gruber&Petters công bố rằng đây là phần mềm Thời khóa biểu số 1 Châu Âu, ra đời lần đầu tiên năm 1970. Hiện tại phần mềm này đang được dùng tại hơn 15,000 trường phổ thông trải rộng 60 quốc gia trên thế giới. Bản thân chúng tôi đã download phần mềm này về thử nghiệm và nhận thấy rằng phần mềm này có rất nhiều điểm chung với phần mềm TKB của School@net, tuy nhiên các chức năng hiện có của phần mềm này không hơn gì so với TKB phiên bản 6.0.

Một số đặc điểm chung của các phần mềm xếp Thời khóa biểu trên thế giới:

- Hầu hết mô hình các trường Đại học trên thế giới đều là mô hình lớp tín chỉ, trong khi đó tại Việt Nam mô hình chủ yếu là lớp niên chế.

- Các tiết học trong ngày được sắp xếp liên tục từ sáng đến tối, không phân biệt các buổi học kiểu Sáng-Chiều-Tối như chúng ta.

- Tất cả các phần mềm thời khóa biểu đều lưu trữ dữ liệu dưới dạng binary, đây là một đặc thù tổng quát của các phần mềm Thời khóa biểu nói chung, kể cả Việt Nam và thế giới.

- Tất cả các phần mềm đều có chức năng cho phép hiển thị, kiểm tra dữ liệu, xếp tiết, xếp tự động ngay trên màn hình. Các chức năng này tạo ra những công cụ tốt giúp người xếp thời khóa biểu hoàn thiện công việc của mình.

- Chức năng chuyển dữ liệu Thời khóa biểu sang HTML, đây là chức năng mà hầu như tất cả các phần mềm đều có. Với tính năng này các đối tượng thụ hưởng phần mềm (như học sinh, giáo viên) có thể xem thông tin thời khóa biểu từ xa qua mạng máy tính.

- Một điều nữa cần nhắc đến là trên thế giới các chuyên gia đều khẳng định rằng công việc xếp Thời khóa biểu mang ý nghĩa chuyên nghiệp rất cao, thậm chí có thể coi đây là một "nghề". Chỉ có những người trong "nghề" mới hiểu rõ ý nghĩa và những khó khăn đặc thù của công việc xếp thời khóa biểu, chỉ có những người trong nghề mới có những "tư duy" giúp cho việc xếp thời khóa biểu nhanh chóng và chính xác.

Phân loại mô hình xếp Thời khóa biểu

1 - Phân loại theo khuôn dạng thời gian Thời khóa biểu

Phân loại theo mẫu biểu của Thời khóa biểu được in ra. Trên thực tế có rất nhiều dạng Thời khóa biểu khác nhau, rất đa dạng và tuỳ thuộc vào hoàn cảnh, điều kiện của từng trường. Có thể liệt kê ra đây một vài kiểu (mẫu) thời khóa biểu như sau:

A. Thời khóa biểu TUẦN

Là mẫu dạng Thời khóa biểu cho một tuần và được dùng làm chuẩn cho tất cả các tuần của học kỳ hoặc năm học. Đa số các nhà trường của Việt Nam đều sử dụng khuôn mẫu này. Đây cũng là mô hình thời khóa biểu của đa số các phần mềm thời khóa biểu trên thế giới mà chúng tôi đã tham khảo.

B. Thời khóa biểu HỌC KỲ

Là mẫu khuôn dạng thời khóa biểu được biểu diễn chi tiết đến từng ngày trong suốt một học kỳ hoặc năm học. Một số các trường đại học, cao đẳng tại Việt Nam, đặc biệt là các trường quân đội sử dụng khuôn dạng này của Thời khóa biểu.

C. Thời khóa biểu 2 TUẦN liên tục

Là mẫu dạng Thời khóa biểu theo tuần nhưng phân biệt sự khác nhau giữa các tuần chẵn và lẻ trong học kỳ. Thời khóa biểu dạng này được áp dụng cho các loại trường có môn học, bài giảng được sắp xếp 2 tuần 1 lần trong học kỳ hoặc năm học. Thời khóa biểu của một tuần chẵn hoặc lẻ có dạng giống như loại A đã mô tả ở trên.

D. Thời khóa biểu (k) TUẦN/HỌC KỲ

Đây là loại thời khóa biểu khuôn dạng tuần tuy nhiên thời gian phân bổ cho thời khóa biểu được chia làm nhiều kỳ trong một học kỳ hoặc năm học. Rất nhiều trường đại học, cao đẳng tại Việt Nam sử dụng mô hình này. Với mô hình này, các môn học được sắp xếp không dàn đều trong một học kỳ mà thường co giãn trong những khoảng thời gian nhỏ hơn. Các trường đại học, cao đẳng với chương trình đào tạo đa dạng, kết hợp chặt chẽ giữa lý thuyết và thực tế thường hay sử dụng mô hình này. Chúng tôi sẽ phân tích kỹ mô hình này trong các phần tiếp theo của báo cáo này.

E. Thời khóa biểu cho mỗi TUẦN

Là loại thời khóa biểu mô hình tuần nhưng mỗi tuần lại có một Thời khóa biểu riêng. Như vậy ví dụ trong một học kỳ có 25 tuần thì mỗi lớp học sẽ có đúng 25 thời khóa biểu!. Đây là mô hình rất phức tạp và về bản chất chính là mô hình Thời khóa biểu Học kỳ (loại B), điểm khác duy nhất là khuôn dạng in ra của Thời khóa biểu là TUẦN.

2 - Phân loại theo đơn vị xếp Thời khóa biểu

Phân loại theo các đối tượng trực tiếp liên quan đến dữ liệu thời khóa biểu. Các đối tượng chính của Thời khóa biểu bao gồm:

Giáo viên: người trực tiếp giảng dạy theo các học phần môn học được qui định chặt chẽ về thời lượng, kiến thức và hình thức học.

Hội trường: địa điểm học các môn học và bài giảng do giáo viên đảm nhiệm.

Học sinh: đối tượng học tập trực tiếp của giáo viên giảng dạy. Học sinh được phân công vào các lớp học. Chính việc phân công lớp học theo các kiểu khác nhau tạo ra sự khác biệt cơ bản của mô hình Thời khóa biểu. Trên thực tế tại Việt Nam cũng thế giới có 2 loại lớp học sau đây:

Mô hình lớp học niên chế: Học sinh nhập học và các năm học được phân công cố định vào các lớp học được gọi là lớp niên chế.

Mô hình lớp học tín chỉ: Học sinh được tự do đăng ký vào các bài giảng đã được chuẩn bị trước của Thời khóa biểu. Các lớp học này thực chất là các Bài giảng (Course) được thiết kế thời khóa biểu giảng dạy chi tiết. Thông thường, sau khi thời khóa biểu của các lớp học này đã được lên kế hoạch thì học sinh mới căn cứ vào thời khóa biểu cụ thể để đăng ký học. Cũng có thể xếp thời khóa biểu các lớp học tín chỉ sau khi học sinh đã đăng ký học. Việc sắp xếp này phải đảm bảo sự không trùng giờ học của các sinh viên đã đăng ký. Tuy nhiên cách làm này sẽ vô cùng phức tạp và trên thực tế không có nhà trường nào tổ chức xếp Thời khóa biểu theo mô hình này.

Một số so sánh giữa 2 mô hình lớp niên chế và lớp tín chỉ.

Từ bảng trên ta thấy việc tổ chức Thời khóa biểu theo lớp tín chỉ sẽ đơn giản hơn cho công việc xếp Thời khóa biểu nhưng lại rất phức tạp cho công việc quản lý chuyên môn đào tạo nhà trường. Mô hình lớp niên chế là đơn giản hơn về mặt tổ chức và quản lý nhưng lại rất phức tạp trong việc xếp Thời khóa biểu. Đặc biệt đối với các nhà trường có nhiều đặc thù đào tạo riêng biệt phải thực hiện việc ghép và tách lớp, công việc xếp Thời khóa biểu càng trở nên rắc rối hơn.

Tại Việt Nam, cho tới thời điểm hiện tại, đa số các nhà trường Đại học, Cao đẳng và THCN đều được tổ chức theo mô hình lớp niên chế.

3 - Các đối tượng liên quan đến Thời khóa biểu

Các đối tượng liên quan trực tiếp đến Thời khóa biểu bao gồm Giáo viên, Phòng học và Môn học (học phần) giảng dạy. Các đối tượng này tuy có vai trò thứ yếu trong việc phân loại mô hình thời khóa biểu tuy nhiên những đặc thù riêng biệt của các đối tượng này có ảnh hưởng rất lớn đến mô hình chung của bài toán xếp thời khóa biểu. Chúng ta sẽ xem xét chúng nhanh tại đây.

a) Giáo viên: Trong mô hình của bài toán xếp thời khóa biểu vai trò các giáo viên là ngang nhau. Mỗi giáo viên về nguyên tắc sẽ có một Thời khóa biểu lịch giảng dạy riêng của mình trong học kỳ hoặc năm học hiện thời. Những đặc thù sau cần chú ý khi xem xét dữ liệu thời khóa biểu liên quan đến giáo viên:

- Trong mô hình xếp thời khóa biểu 2 mức (mức sơ bộ - chi tiết) thông tin phân bổ việc xếp thời khóa biểu sơ bộ về Khoa hay Bộ môn là rất quan trọng.

- Việc phân công giảng dạy của giáo viên theo từng môn học hoặc từng hình thức học của môn học sẽ tạo ra sự khác biệt rất lớn giữa các mô hình xếp thời khóa biểu khác nhau.

- Cho phép gán phân công giảng dạy không phải cho 1 giáo viên mà là cho một nhóm giáo viên.

- Phân công giáo viên cho các lớp ghép và tách.

b) Phòng học: Phòng học chuyên môn đóng vai trò rất quan trọng trong mọi bài toán xếp thời khóa biểu. Các đặc thù sau của phòng học cần chú ý khi xếp thời khóa biểu:

- Có phân biệt rõ ràng hay không giữa các phòng học lý thuyết và thực hành theo các môn học.

- Các đặc thù chuyên môn đặc biệt của phòng học (ví dụ đối với các trường thể dục thể thao, nghệ thuật múa, hát, hội họa, thiết bị đặc chủng quân sự, ....)

c) Môn học: Môn học hay học phần là một đơn vị quản lý chính của chương trình đào tạo và là đối tượng xếp thời khóa biểu chính của cả 2 mô hình lớp niên chế và lớp tín chỉ. Chính vì vậy môn học đóng vai trò quan trọng trong mô hình bài toán xếp Thời khóa biểu các nhà trường đại học, cao đẳng của Việt Nam. Các đặc thù sau cần lưu ý khi mô tả dữ liệu môn học:

- Quan hệ giữa môn học trong Chương trình đào tạo chi tiết và phân bổ giảng dạy cho thời khóa biểu hiện thời.

- Thông tin về mã môn học (học phần). Đây là thông số rất quan trọng của dữ liệu môn học trong mô hình dữ liệu thời khóa biểu. Theo chúng tôi quan sát thấy, hiện tại mỗi nhà trường tại Việt Nam có một hệ thống mã hóa môn học rất khác nhau và không thống nhất. Tuy vậy có thể tóm tắt lại những thông tin thường thấy có mặt trong mã hóa môn học:

(a) Thông tin về Khoa hay Bộ môn trực tiếp phụ trách học phần môn học này.

(b) Thông tin liên quan đến Môn học KHUNG có trong chương trình đào tạo khung của Bộ Giáo dục & Đào tạo.

(c) Thông tin về phân ngành của môn học (cơ bản, đại cương, cơ sở ngành hay chuyên ngành).

(d) Thông tin về hình thức học, đặc thù hội trường, số đơn vị học trình.

(e) Thông tin liên quan đến khóa học và học kỳ được phân bổ của môn học này.

(g) Thông tin liên quan đến phân bổ giảng dạy theo lớp học (ví dụ ghép hay tách) của môn học này.

Các đặc thù của công việc xếp Thời khóa biểu tại Việt Nam

Mô hình của bài toán xếp Thời khóa biểu cho các nhà trường Việt Nam có những đặc thù quan trọng sau đây:

- Phân biệt rõ ràng buổi học SÁNG, CHIỀU, TỐI. Đây là một đặc thù rất riêng biệt của Việt Nam do tính chất của thời tiết vùng nhiệt đới. Tại Việt Nam, hầu hết việc học tập chỉ diễn ra trong một buổi học, các tiết học đánh số từ đầu cho mỗi buổi học.

- Phần lớn các nhà trường Việt Nam có mô hình thời khóa biểu theo lớp niên chế. Tuy nhiên trong một số mô hình có kết hợp cả hai loại hình lớp học niên chế và tín chỉ.

- Do mô hình chương trình KHUNG đào tạo của Bộ Giáo dục & Đào tạo được mô tả rất sơ sài và tổng quát, mỗi nhà trường hầu như lại có một mô hình quản lý Chương trình Đào tạo CHI TIẾT khác nhau, dẫn đến việc mô hình xếp Thời khóa biểu cũng rất khác nhau. Theo quan sát của chúng tôi tại Việt Nam hầu như không có 2 nhà trường đại học, cao đẳng nào có mô hình thời khóa biểu giống nhau. Hay nói một cách khác không thể xây dựng một phần mềm hỗ trợ xếp Thời khóa biểu chung cho tất cả các nhà trường. (Trong khi đó chú ý rằng mô hình thời khóa biểu trường phổ thông của Việt Nam là gần như thống nhất trên toàn quốc!).

- Công việc xếp thời khóa biểu tại các nhà trường đại học, cao đẳng của Việt Nam thông thường theo một trong 2 cách sau:

(1) toàn bộ công việc xếp thời khóa biểu tập trung tại Phòng đào tạo, hay cách xếp thời khóa biểu 1 bước duy nhất.

(2) việc xếp thời khóa biểu được chia thành 2 giai đoạn, giai đoạn 1 xếp sơ bộ, việc xếp thời khóa biểu sơ bộ thường được tiến hành tại các khoa hoặc bộ môn. Sau khi đã xếp sơ bộ, phòng đào tạo sẽ tiến hành tinh chỉnh và hoàn thiện thời khóa biểu. Cũng có thể ngược lại, công việc xếp sơ bộ thực hiện tại phòng đào tạo, phân bổ chi tiết thời khóa biểu được thực hiện tại các Khoa hoặc Bộ môn.

Các tính năng tối thiểu cần phải có của phần mềm hỗ trợ xếp Thời khóa biểu?

Theo chúng tôi các tính năng sau đây tối thiểu cần phải có của mỗi phần mềm hỗ trợ xếp Thời khóa biểu:

1. Chức năng xem, truy vấn thời khóa biểu theo nhiều khuôn dạng khác nhau trên màn hình. Các thời khóa biểu phải được thể hiện đẹp, rõ ràng, sáng sủa và dễ hiểu.

2. Việc thể hiện thông tin Thời khóa biểu phải hiện trong thời gian tức thời. Không được phép có thời gian trễ lớn khi truy nhập thông tin thời khóa biểu.

3. Có nhiều chức năng điều chỉnh, tinh chỉnh dữ liệu thời khóa biểu. Hay nói cách khác cần kiến tạo các công cụ mô phỏng tư duy xếp thời khóa biểu bằng tay ngay trên màn hình view thời khóa biểu chính.

4. Có chức năng bảo mật dữ liệu thời khóa biểu.

5. Chức năng ghi dữ liệu thời khóa biểu ra dạng HTML để đưa lên mạng cho phép truy nhập thông tin thời khóa biểu từ xa.
URL của bài viết này::http://www.schoolnet.vn/modules.php?name=Sanpham&file=article&sid=428
© Cong ty Cong Nghe Tin hoc Nha truong contact: sales@schoolnet.vn