Tổng quan nghiên cứu

Trong hệ thống giáo dục đại học vận hành theo học chế tín chỉ, công tác tổ chức thi kết thúc học phần luôn đối mặt với thách thức lớn về tối ưu hóa nguồn lực và kiểm soát xung đột lịch thi. Tại Trường Đại học Mở TP. Hồ Chí Minh, việc xếp lịch thi thủ công trước đây cho quy mô hơn 45.342 lượt đăng ký môn học thường tiêu tốn khoảng 30 ngày làm việc của cán bộ quản lý đào tạo. Quy trình trích xuất dữ liệu từ phần mềm Edusoft phiên bản Visual FoxPro 9 sang bảng tính Excel và sắp xếp theo kinh nghiệm cảm tính bộc lộ nhiều hạn chế nghiêm trọng, bao gồm nguy cơ trùng lặp ca thi của sinh viên học vượt hoặc học song ngành, phân bổ phòng thi mất cân đối tại cơ sở chính với 20 phòng học có tổng sức chứa gần 2.000 chỗ ngồi, cũng như kéo dài thời gian tổ chức thi vượt quá kế hoạch học kỳ.

Mục tiêu cốt lõi của đề tài là khảo sát hiện trạng, chuẩn hóa toàn diện hệ thống ràng buộc đặc thù và xây dựng hệ thống phần mềm hỗ trợ xếp lịch thi tự động dựa trên thuật toán tối ưu hóa đồ thị. Nghiên cứu tập trung giải quyết bài toán lịch thi học kỳ cho 15 ngành đào tạo thuộc các bậc Đại học và Cao đẳng chính quy, bao quát 6 khóa tuyển sinh từ năm 2008 đến 2013 trong phạm vi học kỳ 2 năm học 2013–2014. Kết quả nghiên cứu mang ý nghĩa thực tiễn to lớn khi chuyển đổi toàn bộ quy trình thủ công 720 giờ sang vận hành tự động trong thời gian tính bằng phút, đảm bảo thỏa mãn tuyệt đối 100% các ràng buộc học vụ bắt buộc và nâng cao hiệu suất khai thác tài nguyên phòng ốc tại các cơ sở đào tạo.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng lý thuyết xếp lịch trong cơ sở giáo dục đào tạo theo định nghĩa của Burke và Carter, mô hình hóa bài toán thông qua bốn tham số cốt lõi gồm tập thời gian $T$, tập nguồn lực $R$, tập các cuộc thi $M$ và tập ràng buộc $C$. Bài toán xếp lịch thi (Examination Timetabling) được tiếp cận chuyên sâu qua Lý thuyết đồ thị và Bài toán tô màu đồ thị (Graph Coloring Problem).

Trong mô hình này, ba khái niệm trọng tâm được xác lập chặt chẽ:

  1. Đồ thị xung đột $G = (V, E)$: Các đỉnh đại diện cho 226 môn học cần xếp lịch và các cạnh vô hướng nối giữa hai đỉnh biểu thị việc có ít nhất một sinh viên đăng ký đồng thời cả hai môn học đó.
  2. Hệ thống ràng buộc kép: Bao gồm 7 ràng buộc cứng (sinh viên không thi trùng ca, không thi quá 2 ca/ngày, khoảng cách ôn tập tối thiểu 2/3 ngày cho mỗi tín chỉ, đáp ứng phòng chuyên dụng, giới hạn sức chứa cơ sở) và 6 ràng buộc mềm (ưu tiên thi tại địa điểm học, gom chung đề thi cho môn học tương đương, cân bằng số lượng thí sinh giữa các ca).
  3. Chỉ số khoảng cách thời gian: Khoảng cách trong $D_1$ giữa các ca cùng ngày và khoảng cách ngoài $D_2$ giữa các ngày thi để đảm bảo lịch ôn tập tối ưu cho sinh viên.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm kết hợp tối ưu hóa thuật toán Heuristic trên nguồn dữ liệu thực tế trích xuất từ 8 phân hệ quản trị của hệ thống Edusoft. Cỡ mẫu nghiên cứu bao gồm 614 bản ghi dữ liệu thời khóa biểu thực tế, tương ứng với 604 nhóm môn học, 256 nhóm lớp của 15 ngành đào tạo và 45.342 lượt đăng ký của hơn 11.000 sinh viên trong học kỳ 2 năm học 2013–2014. Phương pháp chọn mẫu toàn bộ được áp dụng để đảm bảo tính toàn vẹn dữ liệu, không bỏ sót bất kỳ trường hợp ngoại lệ nào như sinh viên học trả nợ, học vượt hay các mã môn học tương đương giữa chương trình đào tạo cũ và mới.

Quy trình phân tích và xử lý thuật toán được thực hiện qua các giai đoạn:

  1. Trích xuất, làm sạch dữ liệu và lập bảng ma trận trọng số $W_{n \times n}$ thể hiện số lượng sinh viên trùng lặp giữa các môn học.
  2. Sắp xếp thứ tự ưu tiên các đỉnh đồ thị theo bậc giảm dần kết hợp trọng số cạnh lớn nhất.
  3. Áp dụng giải thuật tô màu cải tiến: Gán trực tiếp màu (đại diện cho ca thi và ngày thi cụ thể) kết hợp kiểm tra đồng thời sức chứa khả dụng của cơ sở $CL_k(R_i)$ tại thời điểm tô màu.

Lý do lựa chọn giải thuật tô màu trực tiếp kết hợp kiểm tra sức chứa thay vì quy trình 2 giai đoạn truyền thống nhằm rút ngắn tối đa thời gian tính toán, loại bỏ các bước ghi vết ngược phức tạp mà vẫn đáp ứng hoàn hảo yêu cầu quản lý thực tế của nhà trường.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình kiểm thử hệ thống trên cơ sở dữ liệu thực nghiệm học kỳ 2 năm học 2013–2014 đã ghi nhận những kết quả nổi bật:

  1. Thỏa mãn tuyệt đối các ràng buộc học vụ: Hệ thống xử lý thành công 604 nhóm môn học với tỷ lệ thỏa mãn 7 ràng buộc cứng đạt mức 100%. Không có bất kỳ sinh viên nào trong tổng số 45.342 lượt đăng ký bị trùng ca thi hoặc phải di chuyển giữa các cơ sở khác nhau khi thi 2 ca trong cùng một ngày.
  2. Rút ngắn vượt bậc thời gian xử lý: Thời gian lập lịch thi hoàn chỉnh giảm từ khoảng 30 ngày làm việc thủ công xuống dưới 15 phút xử lý thuật toán, tương đương mức cắt giảm thời gian hơn 99%.
  3. Chuẩn hóa tổ chức thi chung đề: Tự động nhận diện và gom nhóm thành công 10 cặp môn học tương đương (như PHYS1601/VL0301 môn Vật lý đại cương, CENG2401/TD2201 môn Trắc địa đại cương) vào cùng một ca thi, nâng tính khách quan trong đánh giá kết quả giảng dạy lên mức 100% đối với các môn chung chương trình.
  4. Phân bổ tối ưu 103 ca thi theo 2 đợt: Hệ thống phân chia khoa học thành 33 ca thi cho đợt 1 (các môn kết thúc sớm trong 7 tuần đầu) và 70 ca thi cho đợt 2 (các môn thi chính thức), giúp giảm tỷ lệ chênh lệch số lượng thí sinh giữa các ca liên tiếp xuống dưới 12%.

Thảo luận kết quả

Nguyên nhân chính mang lại hiệu quả vượt trội của hệ thống là việc cải tiến thuật toán tô màu đồ thị theo hướng tích hợp gán ca thi trực tiếp. Khác với mô hình của Timothy A. khi gán phòng thi chi tiết gây lãng phí bộ nhớ, hệ thống phân bổ theo sức chứa tổng thể của từng cơ sở đào tạo, rất phù hợp với mô hình phối hợp giữa Phòng Quản lý Đào tạo và Trung tâm Khảo thí.

Dữ liệu kết quả có thể được trực quan hóa hiệu quả thông qua hai dạng biểu đồ:

  • Ma trận nhiệt (Heatmap Matrix) kích thước $226 \times 226$ thể hiện mật độ xung đột giữa các môn học, trong đó các điểm giao có trọng số lớn được giải tỏa triệt để bằng các màu sắc đại diện cho các ca thi cách biệt.
  • Biểu đồ cột chồng so sánh (Stacked Bar Chart) thể hiện tải lượng thí sinh trên 103 ca thi, chứng minh sự đồng đều về mật độ sinh viên và nhu cầu cán bộ coi thi giữa phương pháp thủ công và hệ thống tự động.

So với các nghiên cứu trước đây như báo cáo của Chu Thị Hạnh (2013) chỉ ra tính năng phần mềm chiếm 52,2% mức độ thành công khi triển khai tự động hóa, giải pháp của luận văn đã giải quyết triệt để rào cản tính năng nhờ thiết kế linh hoạt, bám sát đặc thù vận hành của trường đại học đào tạo đa ngành theo tín chỉ.

Đề xuất và khuyến nghị

  1. Chuẩn hóa danh mục môn học tương đương định kỳ: Phòng Quản lý Đào tạo cần rà soát và cập nhật 100% bảng mã môn học tương đương trước khi bắt đầu học kỳ mới ít nhất 15 ngày làm việc, đảm bảo thuật toán nhận diện chính xác các nhóm lớp cần thi chung đề ngay từ khâu nạp dữ liệu đầu vào.
  2. Nâng cấp giải thuật tích hợp Meta-Heuristic: Bộ phận phát triển phần mềm cần nghiên cứu tích hợp thuật toán tìm kiếm Tabu (Tabu Search) hoặc Giải thuật Di truyền (Genetic Algorithm) trong quý 4 năm 2014 nhằm tối ưu hóa sâu hơn 6 ràng buộc mềm, hướng tới mục tiêu nâng tỷ lệ sinh viên được dự thi tại đúng cơ sở học tập ban đầu đạt trên 95%.
  3. Ban hành quy chế phối hợp chuẩn hóa dữ liệu liên phòng ban: Ban Giám hiệu nhà trường cần phê duyệt quy trình vận hành chuẩn giữa Phòng Quản lý Đào tạo và Trung tâm Khảo thí & Kiểm định chất lượng trong vòng 30 ngày, thiết lập thời hạn bàn giao dữ liệu phân bổ ca thi theo cơ sở trước thời điểm tổ chức thi ít nhất 3 tuần.
  4. Mở rộng phạm vi tự động hóa cho các hệ đào tạo bổ sung: Trung tâm Công nghệ Thông tin cần triển khai nhân rộng hệ thống cho 100% các lớp thuộc hệ Cao học, Đào tạo từ xa và Văn bằng 2 trong năm học 2014–2015, giảm thiểu ít nhất 70% khối lượng công việc điều phối thủ công tại cơ sở Võ Văn Tần và các điểm thi liên kết.

Đối tượng nên tham khảo luận văn

  1. Cán bộ quản lý đào tạo và chuyên viên khảo thí: Tiếp cận quy trình công nghệ chuẩn hóa dữ liệu để lên kế hoạch tổ chức 103 ca thi học kỳ khoa học, loại bỏ hoàn toàn sai sót thủ công và rút ngắn thời gian lập lịch từ 1 tháng xuống vài giờ.
  2. Kỹ sư phát triển phần mềm và chuyên gia hệ thống thông tin: Tham khảo giải thuật tô màu đồ thị cải tiến viết trên nền tảng Visual FoxPro và C#, nắm bắt kỹ thuật xử lý ma trận trọng số $W_{n \times n}$ và cấu trúc truy xuất dữ liệu từ các hệ thống ERP giáo dục tương tự Edusoft.
  3. Học viên cao học và nghiên cứu sinh ngành Khoa học Máy tính: Sử dụng đề tài làm tài liệu nghiên cứu chuyên sâu về bài toán lập lịch NP-hard, khai thác tập dữ liệu thực nghiệm 45.342 lượt đăng ký làm bộ dữ liệu chuẩn (benchmark) cho các thuật toán tối ưu hóa mới.
  4. Ban giám hiệu các cơ sở giáo dục đại học chuyển đổi sang tín chỉ: Tham khảo mô hình hoạch định chính sách phân bổ cơ sở vật chất, tối ưu hóa công năng của 20 phòng học cơ sở chính và các cơ sở thuê ngoài nhằm tiết kiệm chi phí vận hành.

Câu hỏi thường gặp

Hệ thống xử lý bài toán trùng lịch của sinh viên học vượt và học song ngành như thế nào?
Hệ thống thiết lập ma trận xung đột $W_{n \times n}$ dựa trên 45.342 lượt đăng ký thực tế. Khi phát hiện một sinh viên đăng ký cả 2 môn học, trọng số $w_{ij} > 0$ sẽ kích hoạt cạnh nối trên đồ thị, buộc thuật toán phải gán 2 môn học này vào 2 màu (ca thi) hoàn toàn khác nhau, ngăn ngừa 100% hiện tượng trùng lịch.

Tại sao hệ thống chỉ phân bổ lịch thi theo cơ sở thay vì phân chi tiết từng phòng thi cụ thể?
Quy trình quản lý của trường phân định rõ: Phòng Quản lý Đào tạo lập khung lịch thi tổng thể theo cơ sở, sau đó Trung tâm Khảo thí sẽ bố trí phòng thi chi tiết theo sức chứa gần 2.000 chỗ ngồi. Cách tiếp cận này giúp giảm độ phức tạp thuật toán và tăng tính chủ động khi phòng ốc có sự thay đổi đột xuất.

Thuật toán đảm bảo khoảng cách thời gian ôn thi giữa các môn học ra sao?
Hệ thống chuẩn hóa ràng buộc khoảng cách ngoài $D_2 \ge 2$ ngày đối với các môn học thuộc cùng một Khóa - Ngành đào tạo. Quy chuẩn này đảm bảo sinh viên luôn có tối thiểu 2/3 ngày ôn tập cho mỗi tín chỉ theo đúng quy chế đào tạo tín chỉ hiện hành của nhà trường.

Dữ liệu thực nghiệm của hệ thống được kiểm thử trên quy mô lớn đến mức nào?
Chương trình được kiểm thử toàn diện trên dữ liệu thực của học kỳ 2 năm học 2013–2014, bao gồm 614 mẫu tin thời khóa biểu, 604 nhóm môn học, 226 môn học độc lập của 15 ngành đào tạo và 6 khóa học với tổng cộng 45.342 lượt sinh viên dự thi.

Hệ thống mang lại lợi ích kinh tế và quản lý trực tiếp gì so với phương pháp Excel truyền thống?
Hệ thống giúp tiết kiệm hơn 99% thời gian nhân sự (từ 30 ngày xuống dưới 15 phút), giảm thiểu nhu cầu in ấn đề thi riêng lẻ nhờ gom 10 cụm môn tương đương thi chung đề, đồng thời tối ưu hóa chi phí thuê mướn phòng ốc ngoài cơ sở chính Võ Văn Tần.

Kết luận

  • Luận văn giải quyết triệt để bài toán xếp lịch thi tín chỉ phức tạp với quy mô 45.342 lượt đăng ký và 604 nhóm môn học tại Trường Đại học Mở TP. Hồ Chí Minh.
  • Đề xuất thành công thuật toán tô màu đồ thị cải tiến, kết hợp kiểm tra đồng thời sức chứa cơ sở $CL_k(R_i)$ và gán ca thi trực tiếp trong quá trình duyệt đỉnh.
  • Rút ngắn thời gian lập lịch thi từ 30 ngày làm việc thủ công xuống dưới 15 phút tính toán tự động, đạt độ chính xác 100% đối với 7 ràng buộc cứng.
  • Tối ưu hóa hiệu quả 103 ca thi chia làm 2 đợt, gom nhóm hoàn hảo 10 cặp mã môn học tương đương để tổ chức thi chung đề đánh giá chất lượng đào tạo.
  • Định hướng phát triển tiếp theo là tích hợp giải thuật meta-heuristic và mở rộng triển khai cho 100% các hệ đào tạo sau đại học và đào tạo từ xa trong năm học 2014–2015.

Hãy áp dụng ngay mô hình quản lý thông tin và giải thuật xếp lịch thi tự động để chuẩn hóa quy trình học vụ và tối ưu hóa toàn diện nguồn lực giáo dục tại đơn vị của bạn!