Tổng quan nghiên cứu

Trong bối cảnh hệ thống giáo dục đại học và cao đẳng tại Việt Nam chuyển đổi mạnh mẽ từ hình thức niên chế sang học chế tín chỉ, khối lượng dữ liệu đăng ký môn học của sinh viên đã gia tăng nhanh chóng. Mỗi học kỳ, phòng đào tạo phải xử lý hàng nghìn lượt đăng ký với hàng trăm lớp học phần khác nhau. Việc lập lịch thủ công truyền thống thường tiêu tốn từ 2 đến 4 tuần làm việc của đội ngũ quản lý học vụ, đồng thời dễ phát sinh tỷ lệ xung đột lịch học lên tới khoảng 15% đến 20%.

Vấn đề cốt lõi là bài toán xếp thời khóa biểu (Timetabling Problem) đã được chứng minh thuộc lớp bài toán NP-đầy đủ (NP-Complete). Đặc trưng của lớp bài toán này là không có thuật toán đa thức nào tìm ra lời giải tối ưu tuyệt đối trong thời gian nhanh khi quy mô dữ liệu mở rộng. Cách xếp lịch thủ công hoặc bán tự động đơn giản không chỉ gây lãng phí từ 20% đến 30% công suất phòng học do tình trạng ghế trống, mà còn chưa thể cân bằng giữa bài toán chi phí thù lao giảng dạy và chất lượng chuyên môn của đội ngũ giảng viên.

Mục tiêu cụ thể của nghiên cứu là thiết kế và xây dựng một Hệ hỗ trợ ra quyết định (Decision Support System - DSS) nhằm tự động hóa quy trình xếp thời khóa biểu theo tín chỉ. Hệ thống hướng đến việc thỏa mãn 100% các ràng buộc cứng, tối thiểu hóa chi phí sử dụng phòng học, giảm thiểu tối đa các tiết học vào buổi tối hoặc ngày nghỉ cuối tuần, đồng thời cung cấp 4 phương án bố trí giảng viên để nhà quản lý lựa chọn thông qua giải thuật tối ưu đa mục tiêu.

Nghiên cứu được triển khai trong thời gian 10 tháng, từ ngày 21 tháng 01 năm 2013 đến ngày 22 tháng 11 năm 2013 tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh. Ý nghĩa thực tiễn của công trình thể hiện qua việc giảm hơn 80% thời gian xử lý lịch học, nâng cao hiệu suất khai thác phòng ốc lên trên 85% và mang lại công cụ tư vấn khách quan, khoa học cho nhà quản lý học vụ.

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 dựa trên sự giao thoa của ba nền tảng lý thuyết lớn trong khoa học máy tính và tối ưu hóa vận trù học:

Thứ nhất là Lý thuyết Hệ hỗ trợ ra quyết định (DSS). Hệ thống DSS bao gồm 4 thành phần cơ bản: hệ thống quản lý dữ liệu, hệ thống quản lý mô hình, hệ thống quản lý kiến thức và hệ thống giao tiếp người dùng. DSS không thay thế hoàn toàn con người mà đóng vai trò hỗ trợ người ra quyết định giải quyết các bài toán bán cấu trúc và phi cấu trúc thông qua phân tích kịch bản và tối ưu hóa định lượng.

Thứ hai là Lý thuyết đồ thị và bài toán tô màu đồ thị (Graph Coloring). Bài toán xếp thời khóa biểu được mô hình hóa bằng đồ thị vô hướng, trong đó mỗi đỉnh đại diện cho một môn học cần bố trí. Cạnh nối giữa hai đỉnh biểu diễn mối quan hệ xung đột khi có ít nhất 1 sinh viên đăng ký đồng thời cả hai môn học đó. Trọng số của cạnh là tổng số lượng sinh viên trùng lịch. Heuristic bậc lớn nhất của đỉnh (Largest Degree Heuristic) được áp dụng nhằm ưu tiên xếp trước các môn học có bậc xung đột lớn nhất, từ đó giảm thiểu tối đa khả năng bế tắc trong việc phân bổ tài nguyên thời gian và không gian.

Thứ ba là Phương pháp phân tích thứ bậc AHP (Analytic Hierarchy Process) do Thomas L. Saaty phát triển. AHP phân rã bài toán quyết định đa mục tiêu phức tạp thành cây phân cấp gồm: mục tiêu tổng quát tại đỉnh, nhóm 3 tiêu chí đánh giá (Chi phí, Chất lượng, Rủi ro) ở tầng trung gian và nhóm 4 phương án bố trí ở tầng cơ sở. Bằng cách sử dụng ma trận so sánh cặp (Pairwise Comparison Matrix) với thang điểm từ 1 đến 9 và giải thuật tính vector riêng (Eigenvector) chuẩn hóa về thang đo 1, AHP giúp định lượng hóa chính xác các nhận định chủ quan của nhà quản lý.

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

Nghiên cứu kết hợp phương pháp nghiên cứu lý thuyết mô hình hóa toán học với thực nghiệm phần mềm định lượng:

Về nguồn dữ liệu và cỡ mẫu: Dữ liệu thực nghiệm được xây dựng mô phỏng theo cấu trúc đào tạo tín chỉ thực tế tại các trường đại học lớn. Cỡ mẫu thực nghiệm bao gồm 15 phòng học với sức chứa biến thiên từ 30 đến 120 chỗ ngồi, danh mục hơn 50 giảng viên với các trình độ học vị khác nhau, cùng dữ liệu đăng ký môn học của trên 1.000 sinh viên phân bổ qua hàng chục lớp học phần. Phương pháp chọn mẫu là chọn mẫu ngẫu nhiên phân tầng kết hợp mẫu điển hình nhằm bao phủ đầy đủ các mức độ xung đột từ thấp (dưới 20%) đến cao (trên 60%).

Về phương pháp phân tích: Nghiên cứu chia quy trình giải toán thành hai giai đoạn rõ rệt. Giai đoạn 1 sử dụng giải thuật tô màu đồ thị kết hợp Heuristic bậc lớn nhất và thuật toán tham lam (Greedy) để gán môn học vào thứ, tiết và phòng. Giai đoạn 2 sử dụng thuật toán tham lam để sinh 4 phương án phân công giảng viên và áp dụng thuật toán AHP để giải bài toán tối ưu đa mục tiêu. Lý do lựa chọn phương pháp này là nhằm bảo đảm tính khả thi về thời gian tính toán thực tế (thời gian chạy dưới 10 giây trên máy tính cá nhân thông thường), khắc phục nhược điểm bùng nổ tổ hợp của các phương pháp quy hoạch nguyên truyền thống.

Công nghệ phát triển hệ thống sử dụng ngôn ngữ Visual Basic .NET để xây dựng giao diện tương tác và thuật toán lõi, kết hợp hệ quản trị cơ sở dữ liệu MS Access để lưu trữ và MS Excel để xử lý, xuất báo cáo thời khóa biểu. Toàn bộ tiến trình nghiên cứu và thực nghiệm hoàn thành trong khoảng thời gian từ tháng 01 đến tháng 11 năm 2013.

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

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

Quá trình mô phỏng và thực nghiệm số trên nhiều bộ dữ liệu khác nhau đã mang lại 4 phát hiện quan trọng:

Thứ nhất, việc kết hợp giải thuật tô màu đồ thị với Heuristic bậc lớn nhất đã triệt tiêu hoàn toàn 100% tình trạng xung đột thời gian học của sinh viên. Các môn học có tổng lượng xung đột lớn (từ 40 đến 80 sinh viên trùng lịch) luôn được thuật toán ưu tiên cấp phát khung giờ và phòng học trước, giúp các môn học không xung đột có thể xếp học song song cùng một thời điểm mà không vi phạm ràng buộc.

Thứ hai, hàm mục tiêu tối ưu thứ tiết trong thuật toán tham lam đã phân bổ thành công hơn 90% các lớp môn vào khung giờ ban ngày (từ tiết 0 đến tiết 11) và các ngày làm việc trong tuần (từ thứ Hai đến thứ Sáu với hệ số ưu tiên bằng 1). Tỷ lệ các lớp phải học vào ban đêm (tiết 12 đến tiết 14) hoặc ngày nghỉ cuối tuần giảm xuống dưới 10%. Đồng thời, hàm chi phí phòng kết hợp ghế trống đã giúp giảm lãng phí diện tích phòng học từ mức 28,5% xuống còn khoảng 8,2%.

Thứ ba, hệ thống đã thiết lập thành công 4 phương án bố trí giảng viên rõ rệt ở Giai đoạn 2: Phương án 1 tối ưu chi phí thấp nhất (giúp tiết kiệm từ 15% đến 25% ngân sách thù lao); Phương án 2 đạt độ rủi ro thấp nhất (chỉ số an toàn lịch học đạt trên 90%); Phương án 3 phản ánh kịch bản chấp nhận rủi ro cao để tối ưu tiêu chí khác; và Phương án 4 đạt chất lượng giảng dạy cao nhất với điểm chất lượng trung bình của đội ngũ giảng viên đạt từ 7,0 đến 9,0 điểm trên thang đánh giá học vị.

Thứ tư, thuật toán AHP đã lượng hóa thành công mức độ ưu tiên toàn cục cho từng phương án. Khi kiểm tra độ nhạy với trường hợp ưu tiên tiêu chí rủi ro là 0,5584, chất lượng là 0,3196 và chi phí là 0,1220, hệ thống đã chỉ ra phương án rủi ro thấp nhất đạt trọng số tổng hợp cao nhất là 0,3280, vượt trội so với các phương án còn lại (lần lượt đạt 0,3060; 0,2720 và 0,0940).

Thảo luận kết quả

Kết quả đạt được chứng minh tính đúng đắn của việc chia bài toán lớn thành hai giai đoạn độc lập có liên kết dữ liệu. Sự kết hợp giữa thuật toán tham lam đơn mục tiêu và AHP đa mục tiêu đã giải quyết thỏa đáng mối quan hệ đánh đổi (trade-off) giữa tính kinh tế và chất lượng giáo dục trong quản trị đại học. Khi ngân sách nhà trường hạn hẹp, nhà quản lý có thể chọn Phương án 1; ngược lại, với các môn học chuyên ngành mũi nhọn đòi hỏi trình độ Tiến sĩ hoặc Giáo sư, Phương án 4 sẽ được ưu tiên kích hoạt.

So sánh với các nghiên cứu trước đây như mô hình giải thuật di truyền của Ulrich Derigs (năm 2005) hay mô hình quy hoạch nguyên tích hợp ràng buộc của Botsali (năm 2004), phương pháp của tác giả Nguyễn Thị Giang cho tốc độ thực thi nhanh hơn, giao diện thân thiện và dễ sử dụng trực tiếp trên môi trường Windows mà không đòi hỏi phần cứng tính toán chuyên dụng đắt tiền.

Trong thực tế ứng dụng, toàn bộ kết quả phân tích độ nhạy của hệ thống có thể được trực quan hóa qua biểu đồ đường biểu diễn sự thay đổi độ ưu tiên của 4 phương án theo từng tiêu chí, cùng biểu đồ cột thể hiện chi phí phòng ghế và chi phí giảng viên theo quy mô số lớp môn. Ma trận so sánh cặp cũng được xuất dưới dạng bảng hai chiều trong MS Excel, giúp hội đồng đào tạo dễ dàng theo dõi và đối chiếu trước khi ban hành thời khóa biểu chính thức.

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

Để ứng dụng hiệu quả hệ hỗ trợ ra quyết định xếp thời khóa biểu vào thực tế quản lý giáo dục, bốn giải pháp cụ thể được đề xuất như sau:

Thứ nhất, chuẩn hóa và số hóa 100% cơ sở dữ liệu học vụ trước mỗi học kỳ. Phòng Đào tạo cùng Phòng Quản trị Công nghệ Thông tin cần phối hợp cập nhật đầy đủ danh mục phòng học, sức chứa chuẩn, đơn giá vận hành và biểu mẫu đánh giá giảng viên. Các hệ số về chất lượng giảng viên (1 điểm cho Cử nhân, 3 điểm cho Thạc sĩ, 5 điểm cho Tiến sĩ, 7 điểm cho Phó Giáo sư và 9 điểm cho Giáo sư) cùng chỉ số rủi ro (thang điểm 10) cần được cập nhật hoàn tất trước thời điểm xếp lịch ít nhất 15 ngày.

Thứ hai, thiết lập quy trình họp đánh giá trọng số đa mục tiêu định kỳ giữa Ban Giám hiệu và lãnh đạo các Khoa. Nhà quản lý cần áp dụng ma trận so sánh cặp AHP để xác định rõ chiến lược ưu tiên của từng học kỳ (ví dụ: gán trọng số 60% cho chất lượng đào tạo đối với chương trình chất lượng cao và 50% cho tối ưu chi phí đối với hệ đào tạo đại trà), hướng tới mục tiêu cắt giảm ít nhất 15% chi phí lãng phí tài nguyên phòng học toàn trường.

Thứ ba, nâng cấp kiến trúc phần mềm từ ứng dụng máy tính cục bộ sang nền tảng web trực tuyến trong lộ trình 6 đến 12 tháng. Đội ngũ kỹ sư phần mềm của nhà trường cần chuyển đổi hệ thống trên nền tảng .NET sang mô hình dịch vụ đám mây, cho phép tự động đồng bộ hóa kết quả thời khóa biểu với cổng thông tin cá nhân của hơn 10.000 sinh viên và giảng viên, giảm thiểu thời gian tra cứu và điều chỉnh lịch học.

Thứ tư, mở rộng thuật toán tối ưu hóa đa mục tiêu nâng cao trong giai đoạn 18 đến 24 tháng tới. Ban đề án công nghệ thông tin nhà trường nên nghiên cứu tích hợp thêm các giải thuật tìm kiếm vùng lân cận như Tìm kiếm Tabu (Tabu Search) hoặc Giải thuật Di truyền (Genetic Algorithm) để xử lý các ràng buộc phức tạp phát sinh tại các phòng thí nghiệm, xưởng thực hành chuyên dụng có quy mô trên 500 lớp môn cùng lúc.

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

Nội dung và kết quả nghiên cứu của luận văn mang lại giá trị ứng dụng và tham khảo thiết thực cho 4 nhóm đối tượng sau:

Nhóm cán bộ quản lý học vụ và chuyên viên xếp thời khóa biểu: Luận văn cung cấp quy trình phân bổ tài nguyên khoa học, giúp tự động hóa khâu lập lịch tín chỉ, giảm hơn 80% thời gian lao động thủ công và loại bỏ hoàn toàn các sai sót trùng lịch phòng hoặc trùng giờ giảng viên.

Nhóm sinh viên, học viên cao học và nhà nghiên cứu ngành Khoa học Máy tính: Tài liệu này là nguồn tài khảo học thuật giá trị về cách giải quyết bài toán NP-đầy đủ trong thực tế, minh họa chi tiết kỹ thuật ánh xạ lý thuyết đồ thị, giải thuật Heuristic tô màu và phương pháp tính vector riêng trong giải thuật AHP.

Nhóm kỹ sư phát triển phần mềm và các công ty công nghệ giáo dục (EdTech): Các chuyên gia có thể khai thác mô hình cơ sở dữ liệu quan hệ, cấu trúc dữ liệu dẫn xuất và logic lập trình thuật toán trong luận văn để tích hợp vào các phân hệ quản lý đào tạo (ERP đại học) và hệ thống hỗ trợ ra quyết định quy mô lớn.

Nhóm lãnh đạo trường đại học, cao đẳng và nhà hoạch định chính sách giáo dục: Công trình mang lại khung tư duy định lượng để quản trị tài chính và nhân sự sư phạm, giúp ban giám hiệu có cơ sở khoa học để cân đối ngân sách chi trả thù lao giảng dạy với mục tiêu nâng cao chuẩn đầu ra và chất lượng đội ngũ cán bộ giảng dạy.

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

Bài toán xếp thời khóa biểu tín chỉ có điểm gì phức tạp hơn so với đào tạo niên chế truyền thống? Trong đào tạo tín chỉ, sinh viên tự do lựa chọn tổ hợp môn học và tiến độ học tập riêng biệt, khiến ma trận xung đột môn học giữa hàng nghìn sinh viên trở nên vô cùng phức tạp. Xếp lịch tín chỉ là bài toán NP-đầy đủ với hơn 5 nhóm ràng buộc cứng và mềm về thời gian, phòng học và giảng viên.

Tại sao luận văn lại kết hợp giải thuật tô màu đồ thị với Heuristic bậc lớn nhất? Giải thuật tô màu đồ thị giúp nhóm các môn học không có sinh viên đăng ký trùng vào cùng một khung giờ. Heuristic bậc lớn nhất ưu tiên xếp trước các môn có tổng số xung đột cao nhất (từ 40 đến 80 sinh viên), giúp hạn chế tình trạng bế tắc tài nguyên và giảm số lượng màu cần sử dụng.

Hệ thống định lượng tiêu chí Chất lượng và Rủi ro của giảng viên như thế nào? Chất lượng giảng viên được định lượng theo thang điểm lẻ từ 1 đến 9 căn cứ vào học hàm và học vị (từ Cử nhân đến Giáo sư). Mức độ rủi ro được chấm theo thang điểm 10 dựa trên tỷ lệ vắng dạy trong quá khứ, tính chất cơ hữu hay thỉnh giảng và mức độ kiêm nhiệm công tác quản lý.

Phương pháp AHP đóng vai trò gì trong việc chọn phương án thời khóa biểu cuối cùng? AHP tổ chức bài toán thành cây phân cấp và sử dụng ma trận so sánh cặp để chuyển các đánh giá định tính thành định lượng. Thông qua thuật toán tính Eigenvector chuẩn hóa về thang đo 1, AHP xác định chính xác độ ưu tiên toàn cục của 4 phương án giảng viên theo đúng định hướng quản lý của nhà trường.

Phần mềm trong luận văn có thể triển khai trên quy mô lớn hơn không? Hệ thống được thiết kế theo mô hình dữ liệu quan hệ chuẩn hóa trên Visual Basic .NET và MS Access, xử lý nhanh các bộ dữ liệu với 15 phòng học trong vài giây. Kiến trúc này hoàn toàn có thể mở rộng cơ sở dữ liệu và nâng cấp lên môi trường máy chủ đám mây để phục vụ quy mô trên 500 lớp môn.

Kết luận

  • Luận văn đã mô hình hóa thành công bài toán xếp thời khóa biểu tín chỉ phức tạp thành quy trình tối ưu hai giai đoạn khoa học và khả thi.
  • Áp dụng hiệu quả giải thuật tô màu đồ thị kết hợp Heuristic bậc lớn nhất, triệt tiêu 100% xung đột lịch học của sinh viên và giảm tỷ lệ lãng phí ghế trống phòng học xuống khoảng 8,2%.
  • Thuật toán tham lam ở Giai đoạn 1 đã bố trí hơn 90% số tiết học vào khung giờ ban ngày của các ngày làm việc trong tuần, tối ưu hóa chi phí vận hành phòng học.
  • Xây dựng thành công 4 phương án bố trí giảng viên đa chiều, định lượng hóa chính xác các chỉ số chất lượng học vị (từ 1 đến 9 điểm) và rủi ro thời khóa biểu (thang điểm 10).
  • Ứng dụng xuất sắc phương pháp phân tích thứ bậc AHP để giải bài toán tối ưu đa mục tiêu, cung cấp công cụ trợ giúp đắc lực cho nhà quản lý học vụ lựa chọn kịch bản tối ưu.

Đóng góp chính của luận văn là đã hoàn thiện một giải pháp Hệ hỗ trợ ra quyết định toàn diện từ mô hình toán học, thuật toán kết hợp đến phần mềm thực thi, giải quyết triệt để sự mất cân bằng giữa chi phí tài chính và chất lượng giáo dục trong quản lý đào tạo đại học.

Kế hoạch phát triển tiếp theo là hoàn thiện việc nâng cấp giao diện sang nền tảng ứng dụng Web trong vòng 6 đến 12 tháng, tiếp tục thử nghiệm với các bộ dữ liệu quy mô lớn trên 500 lớp học phần và tích hợp thêm các giải thuật Meta-heuristic trong giai đoạn 18 đến 24 tháng tới.

Các nhà quản trị giáo dục, chuyên viên học vụ và các nhà phát triển hệ thống thông tin đào tạo hãy chủ động áp dụng khung mô hình toán học và giải pháp DSS này nhằm nâng cao hiệu quả xếp lịch và thúc đẩy tiến trình chuyển đổi số học vụ toàn diện tại đơn vị của mình.