Giải pháp tối ưu cho bài toán lập lịch tại Đại học Quốc gia Hà Nội

Tài liệu nghiên cứu Luận văn giải bài toán lập lịch theo tín chỉ sử dụng giải thuật tìm kiếm tabu, tổng hợp lý thuyết và thực hành, cung cấp kiến thức chuyên sâu về toán học.

• Người hướng dẫn: TS. Lê Nguyên Khôi
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Kỹ thuật phần mềm
• Đề tài: Giải pháp tối ưu cho bài toán lập lịch tại Đại học Quốc gia Hà Nội
• Loại tài liệu: luận văn
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH HIỆN NAY VÀ CÁC CÁCH TIẾP CẬN
• 1.1. Bài toán lập thời khóa biểu cho trường phổ thông (School timetable)
• 1.2. Bài toán lập thời khóa biểu cho trường đại học (University timetable)
• 1.3. Bài toán lập lịch thi (Examination timetabling)
• 1.4. Bài toán lập lịch theo tín chỉ
• 2. CHƯƠNG 2: TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP TÌM KIẾM
• 2.1. Thuật giải mô phỏng luyện kim (Simulated Annealing)
• 2.2. Thuật giải leo đồi (Hill-climbing)
• 2.3. Thuật giải di truyền (Genetic Algorithm)
• 3. CHƯƠNG 3: CƠ SỞ TÌM KIẾM TABU
• 3.1. Lược sử về Tabu Search
• 3.2. Tabu Search – Một dạng Meta-Heuristic
• 3.3. Giai đoạn phát triển của Tabu Search
• 3.4. Nguyên lý chung của Tabu Search
• 3.4.1. Một minh họa
• 4. CHƯƠNG 4: BÀI TOÁN LẬP LỊCH THEO TÍN CHỈ
• 4.1. Mô hình của bài toán
• 4.2. Ví dụ minh họa
• 4.2.1. Bước 1: Khởi tạo lời giải ban đầu ngẫu nhiên
• 4.2.2. Bước 2: Cải thiện chất lượng lời giải bằng giải thuật tìm kiếm Tabu
• 4.2.3. Định dạng tập tin dữ liệu SV đầu vào
• 4.2.4. So sánh kết quả thực nghiệm với kết quả của phần mềm Open Course Timetable
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về bài toán lập lịch tại Đại học Quốc gia

Bài toán lập lịch 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. Không chỉ Việt Nam mà trên toàn cầu từ lâu việc lập lịch đã 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. Bài toán lập thời khóa biểu là một nhánh của bài toán lập lịch trong đó đưa ra một chuỗi các sự kiện (thông thường là các môn học, bài giảng hoặc các môn thi) và bao gồm các giáo viên và học viên trong một khoảng thời gian định trước và thỏa mãn một tập hợp các ràng buộc của từng loại thời khóa biểu khác nhau. Mỗi bài toán có các tính chất riêng, khi xếp lịch thi bài toán đặt ra là phải đáp ứng được yêu cầu về thời gian (như không được trùng hay quá sát nhau) giữa các lần thi liên tiếp của cùng một học sinh, sinh viên. Còn khi xếp lịch cho trường phổ thông thì chúng ta cần quan tâm giờ rảnh mà giáo viên đăng ký và các tiết trống giữa giờ học của học sinh đóng vai trò rất quan trọng cho việc đánh giá kết quả của thời khóa biểu. Đối với đại học, bài toán cần giải quyết cũng là việc tránh xung đột giữa các thành phần tham gia trong thời khóa biểu (giáo viên, lớp học, phòng học và thiết bị). Vì thế, mục tiêu cuối cùng của người xếp thời khóa biểu là tạo ra một thời khóa biểu với ít xung đột nhất. Cũng đã có các khảo sát về bài toán xếp thời khóa biểu. Như việc đưa ra tổng quan các vấn đề về xếp thời khóa biểu thuộc ba dạng ta đã đề cập ở trên của Schaerf, 1995 [1]. Các khảo sát về xếp lịch thi Carter & Laporte, 1996 [2] và xếp lịch cho trường đại học Carter & Laporte, 1998 [3] Bardadym, 1996 [4].

1.1. Bài toán lập lịch thi và lập lịch học khác nhau thế nào

Bài toán lập lịch thi có những đặc điểm khác sau đây: Chỉ có một kỳ thi cho mỗi một môn thi. Các điều kiện xung đột nói chung là hạn chế. Thực tế, chúng ta có thể chấp nhận một sinh viên có thể bỏ qua một bài giảng do sự chồng chéo các môn học; nhưng không có sinh viên nào được phép bỏ qua một kỳ thi hết môn đã học vì nếu sinh viên không qua được kỳ thi này coi như trượt môn đó. Và một số ràng buộc khác như hầu hết một sinh viên sẽ chỉ có một môn thi trong một ngày và không có nhiều quá các môn thi liên tiếp nhau với một sinh viên. Thời gian thi của các môn thi có thể khác nhau, ngược lại với bài toán lập thời khóa biểu cho trường đại học thì thời gian học được tính bằng tiết (45 – 50 phút tùy quy định của trường).

1.2. Tổng quan về bài toán lập lịch theo tín chỉ

II. Thách thức trong lập lịch thi tại Đại học Quốc gia

Việc lập lịch thi hiệu quả tại Đại học Quốc gia Hà Nội đối mặt với nhiều thách thức. Số lượng sinh viên lớn, đa dạng các môn học và chương trình đào tạo tạo ra một không gian tìm kiếm phức tạp. Các ràng buộc về phòng thi, giảng viên, và thời gian thi càng làm tăng độ khó của bài toán. Hơn nữa, việc đảm bảo tính công bằng, minh bạch và sự hài lòng của sinh viên cũng là một yếu tố quan trọng cần xem xét. Các phương pháp lập lịch truyền thống thường gặp khó khăn trong việc xử lý các ràng buộc phức tạp và tìm kiếm giải pháp tối ưu trong thời gian ngắn. Do đó, việc nghiên cứu và áp dụng các giải pháp lập lịch thông minh là vô cùng cần thiết.

2.1. Độ phức tạp của bài toán lập lịch và các ràng buộc

Bài toán lập lịch thuộc lớp bài toán NP-khó, có nghĩa là thời gian giải bài toán tăng theo cấp số nhân với kích thước của bài toán. Các ràng buộc cứng (hard constraints) như không có sinh viên nào thi hai môn cùng lúc, không có phòng thi nào được sử dụng cho hai môn cùng lúc, và các ràng buộc mềm (soft constraints) như tối thiểu hóa số lượng sinh viên phải thi hai môn liên tiếp trong cùng một ngày, tạo ra một không gian tìm kiếm khổng lồ. Việc tìm kiếm một giải pháp thỏa mãn tất cả các ràng buộc là một thách thức lớn.

2.2. Yêu cầu về tính công bằng và minh bạch trong lập lịch thi

Sinh viên mong muốn lịch thi được công bố sớm, không có sự thay đổi đột ngột, và không có sự ưu ái cho bất kỳ môn học hay khoa nào. Việc đảm bảo tính công bằng và minh bạch đòi hỏi quy trình lập lịch phải được chuẩn hóa, có sự tham gia của các bên liên quan, và có cơ chế phản hồi để giải quyết các khiếu nại. Các giải pháp lập lịch thông minh cần có khả năng tạo ra các lịch thi đa dạng, đánh giá các lịch thi dựa trên nhiều tiêu chí, và cho phép người dùng tùy chỉnh các ràng buộc để đáp ứng các yêu cầu cụ thể.

III. Giải thuật Tabu Search cho bài toán lập lịch hiệu quả

Giải thuật Tabu Search là một phương pháp tìm kiếm meta-heuristic hiệu quả để giải quyết các bài toán tối ưu hóa tổ hợp, bao gồm bài toán lập lịch. Tabu Search hoạt động bằng cách di chuyển từ một giải pháp hiện tại sang một giải pháp lân cận tốt nhất, ngay cả khi giải pháp lân cận đó không tốt hơn giải pháp hiện tại. Để tránh lặp lại các giải pháp đã được xét, Tabu Search sử dụng một danh sách cấm (tabu list) để lưu trữ các thuộc tính của các giải pháp đã được xét gần đây. Các thuộc tính này bị cấm (tabu) trong một số lần lặp nhất định, ngăn chặn giải thuật quay lại các giải pháp đã được xét.

3.1. Cơ sở lý thuyết của giải thuật Tabu Search

Tabu Search dựa trên ý tưởng rằng việc khám phá không gian tìm kiếm một cách có hệ thống, thay vì chỉ tìm kiếm các giải pháp tốt hơn, có thể giúp giải thuật thoát khỏi các cực trị địa phương và tìm kiếm các cực trị toàn cục. Danh sách cấm giúp giải thuật tránh lặp lại các giải pháp đã được xét, nhưng cũng có thể ngăn chặn giải thuật tìm kiếm các giải pháp tốt trong vùng lân cận của các giải pháp đã được xét. Do đó, việc thiết kế danh sách cấm và các tiêu chí chấp nhận (aspiration criteria) là rất quan trọng để đảm bảo hiệu quả của Tabu Search.

3.2. Ưu điểm của Tabu Search so với các giải thuật khác

Tabu Search có nhiều ưu điểm so với các giải thuật tìm kiếm khác như giải thuật di truyền (Genetic Algorithm) và giải thuật mô phỏng luyện kim (Simulated Annealing). Tabu Search có khả năng thoát khỏi các cực trị địa phương tốt hơn, hội tụ nhanh hơn, và dễ dàng tùy chỉnh để phù hợp với các bài toán cụ thể. Tuy nhiên, Tabu Search cũng có một số nhược điểm như yêu cầu nhiều tham số, khó khăn trong việc thiết kế danh sách cấm và các tiêu chí chấp nhận, và có thể bị mắc kẹt trong các chu kỳ tìm kiếm.

IV. Ứng dụng Tabu Search để tối ưu hóa thời khóa biểu

Ứng dụng Tabu Search vào bài toán lập lịch tại Đại học Quốc gia Hà Nội mang lại nhiều lợi ích. Giải thuật có khả năng xử lý các ràng buộc phức tạp, tìm kiếm giải pháp tối ưu trong thời gian ngắn, và tạo ra các lịch thi đa dạng. Việc áp dụng Tabu Search giúp cải thiện hiệu quả lập lịch, giảm thiểu xung đột, và tăng sự hài lòng của sinh viên. Hơn nữa, giải thuật có thể được tích hợp vào các phần mềm quản lý đào tạo hiện có, giúp tự động hóa quy trình lập lịch và giảm tải cho cán bộ quản lý.

4.1. Mô hình hóa bài toán lập lịch cho Tabu Search

Để áp dụng Tabu Search, bài toán lập lịch cần được mô hình hóa một cách phù hợp. Các yếu tố như môn học, sinh viên, phòng thi, thời gian thi, và các ràng buộc cần được biểu diễn dưới dạng các biến và hàm mục tiêu. Hàm mục tiêu thường được thiết kế để tối thiểu hóa số lượng xung đột và vi phạm các ràng buộc mềm. Các giải pháp lân cận được tạo ra bằng cách thay đổi vị trí của các môn học trong lịch thi, và danh sách cấm được sử dụng để ngăn chặn việc quay lại các lịch thi đã được xét gần đây.

4.2. Cài đặt và thử nghiệm Tabu Search cho lập lịch thi

Việc cài đặt Tabu Search đòi hỏi kiến thức về lập trình và giải thuật. Các tham số của Tabu Search như kích thước danh sách cấm, số lần lặp, và các tiêu chí chấp nhận cần được điều chỉnh để đạt được hiệu quả tốt nhất. Các thử nghiệm cần được thực hiện trên các bộ dữ liệu thực tế để đánh giá hiệu quả của giải thuật so với các phương pháp lập lịch truyền thống. Kết quả thử nghiệm có thể được sử dụng để cải thiện mô hình hóa bài toán và các tham số của Tabu Search.

V. Kết quả nghiên cứu và so sánh với phần mềm lập lịch

Nghiên cứu đã đạt được những kết quả khả quan trong việc áp dụng Tabu Search cho bài toán lập lịch tại Đại học Quốc gia Hà Nội. Giải thuật đã tạo ra các lịch thi có số lượng xung đột ít hơn so với các lịch thi được tạo ra bằng các phương pháp thủ công. So sánh với phần mềm lập lịch Open Course Timetable, Tabu Search cho thấy khả năng tùy chỉnh cao hơn và khả năng xử lý các ràng buộc phức tạp tốt hơn. Tuy nhiên, Tabu Search cũng đòi hỏi thời gian tính toán lâu hơn và yêu cầu kiến thức chuyên môn để cài đặt và điều chỉnh.

5.1. Đánh giá hiệu quả của Tabu Search trên dữ liệu thực tế

Hiệu quả của Tabu Search được đánh giá dựa trên các tiêu chí như số lượng xung đột, thời gian tính toán, và sự hài lòng của sinh viên. Các thử nghiệm được thực hiện trên các bộ dữ liệu thực tế từ Đại học Quốc gia Hà Nội, và kết quả cho thấy Tabu Search có khả năng tạo ra các lịch thi tốt hơn so với các phương pháp thủ công. Tuy nhiên, cần có thêm các nghiên cứu để đánh giá hiệu quả của Tabu Search trên các bộ dữ liệu lớn hơn và phức tạp hơn.

5.2. So sánh Tabu Search với phần mềm Open Course Timetable

So sánh Tabu Search với phần mềm Open Course Timetable cho thấy Tabu Search có khả năng tùy chỉnh cao hơn và khả năng xử lý các ràng buộc phức tạp tốt hơn. Open Course Timetable là một phần mềm lập lịch miễn phí và dễ sử dụng, nhưng nó có một số hạn chế trong việc xử lý các ràng buộc phức tạp và tùy chỉnh các tham số. Tabu Search đòi hỏi kiến thức chuyên môn để cài đặt và điều chỉnh, nhưng nó có khả năng tạo ra các lịch thi tốt hơn trong các trường hợp phức tạp.

VI. Hướng phát triển và ứng dụng lập lịch trong tương lai

Trong tương lai, việc nghiên cứu và phát triển các giải pháp lập lịch thông minh sẽ tiếp tục là một hướng đi quan trọng. Các giải thuật meta-heuristic như Tabu Search, giải thuật di truyền, và giải thuật mô phỏng luyện kim có thể được kết hợp với các kỹ thuật học máy và trí tuệ nhân tạo để tạo ra các hệ thống lập lịch tự động và thích ứng. Các hệ thống này có thể học hỏi từ dữ liệu lịch sử, dự đoán nhu cầu của sinh viên, và tự động điều chỉnh các tham số để đạt được hiệu quả tốt nhất.

6.1. Tích hợp trí tuệ nhân tạo vào hệ thống lập lịch

Tích hợp trí tuệ nhân tạo vào hệ thống lập lịch có thể giúp hệ thống học hỏi từ dữ liệu lịch sử, dự đoán nhu cầu của sinh viên, và tự động điều chỉnh các tham số để đạt được hiệu quả tốt nhất. Các kỹ thuật học máy như học sâu (deep learning) và học tăng cường (reinforcement learning) có thể được sử dụng để xây dựng các mô hình dự đoán và tối ưu hóa. Các mô hình này có thể được sử dụng để dự đoán số lượng sinh viên đăng ký mỗi môn học, tối ưu hóa việc phân bổ phòng thi, và tự động điều chỉnh các tham số của Tabu Search.

6.2. Phát triển hệ thống lập lịch thích ứng và cá nhân hóa

Phát triển hệ thống lập lịch thích ứng và cá nhân hóa có thể giúp sinh viên tạo ra các lịch thi phù hợp với nhu cầu và sở thích của mình. Hệ thống có thể cho phép sinh viên tùy chỉnh các ràng buộc, chọn các môn học ưu tiên, và xem các lịch thi khác nhau trước khi quyết định. Hệ thống cũng có thể cung cấp các gợi ý và khuyến nghị dựa trên dữ liệu lịch sử và thông tin cá nhân của sinh viên. Các hệ thống lập lịch thích ứng và cá nhân hóa có thể giúp tăng sự hài lòng của sinh viên và cải thiện hiệu quả học tập.

Nội dung chính

Tổng quan nghiên cứu

Theo khảo sát thực tế tại các trường đại học trên toàn quốc, công tác sắp xếp thời khóa biểu thủ công tiêu tốn từ 3 đến 5 ngày làm việc liên tục của cán bộ giáo vụ nhưng vẫn ghi nhận tỷ lệ trùng lịch hoặc bất cập phòng học khoảng 10% đến 15%. Vấn đề nghiên cứu cốt lõi của đề tài bắt nguồn từ tính chất phức tạp của bài toán lập lịch học phần theo học chế tín chỉ, một dạng bài toán tối ưu hóa tổ hợp kinh điển thuộc lớp bài toán NP-khó. Trong mô hình đào tạo hiện đại, số lượng ràng buộc gia tăng theo hàm số mũ khi phải đồng thời thỏa mãn thời gian biểu của hàng nghìn sinh viên đăng ký môn học tự do, lịch giảng dạy của giảng viên và năng lực tiếp nhận của hệ thống phòng ốc.

Mục tiêu cụ thể của luận văn là nghiên cứu sâu về kỹ thuật của giải thuật tìm kiếm Tabu, xây dựng mô hình toán học giải quyết trọn vẹn bài toán lập lịch tín chỉ và phát triển ứng dụng phần mềm tự động hóa quá trình phân bổ tài nguyên đào tạo. Phạm vi nghiên cứu tập trung vào mô hình đào tạo theo hệ thống tín chỉ chuẩn tại Trường Đại học Công nghệ thuộc Đại học Quốc gia Hà Nội trong giai đoạn năm 2014, với cấu trúc học kỳ 15 tuần liên tục.

Ý nghĩa khoa học và thực tiễn của công trình được chứng minh thông qua các chỉ số đo lường rõ rệt. Việc ứng dụng giải thuật tìm kiếm Tabu giúp giảm 90% thời gian tạo lập lịch trình học tập, triệt tiêu 100% các vi phạm ràng buộc cứng về xung đột phòng học, đồng thời cải thiện 35% hiệu suất sử dụng giảng đường và thiết bị giảng dạy so với quy trình xếp lịch bán tự động trước đây.

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 bài toán thỏa mãn ràng buộc (Constraint Satisfaction Problem) và lý thuyết độ phức tạp thuật toán. Đề tài vận dụng lý thuyết giải thuật tìm kiếm Meta-heuristic Tabu Search do Fred Glover đề xuất nhằm định hướng quy trình tìm kiếm cục bộ vượt qua các cực tiểu địa phương để tiếp cận vùng tối ưu toàn cục.

Khung lý thuyết của luận văn tích hợp 4 khái niệm trọng tâm:

• Bộ nhớ thích nghi (Adaptive Memory): Cơ chế lưu trữ thông tin tìm kiếm gồm 4 chiều đánh giá là tính mới xảy ra (Recency), tính thường xuyên (Frequency), chất lượng (Quality) và tầm ảnh hưởng (Influence).
• Danh sách cấm (Tabu List) và Thời hạn cấm (Tabu Tenure): Cơ chế ngăn chặn việc quay lại các trạng thái lời giải đã duyệt qua trong một số bước lặp nhất định nhằm loại bỏ hiện tượng lặp vô hạn.
• Tiêu chuẩn tham vọng (Aspiration Criteria): Quy tắc cho phép bỏ qua trạng thái cấm nếu bước chuyển đó mang lại giá trị hàm mục tiêu tốt hơn kỷ lục hiện tại.
• Chiến lược Tăng cường (Intensification) và Đa dạng hóa (Diversification): Hai trụ cột cân bằng giữa việc đào sâu khai thác vùng lời giải chất lượng cao và mở rộng khảo sát các không gian lời giải tiềm năng chưa khám phá.

Bên cạnh đó, nghiên cứu cụ thể hóa quy định đào tạo tín chỉ với định mức chuẩn: 1 tín chỉ lý thuyết tương đương 1 tiết lên lớp 50 phút kết hợp 2 tiết tự học ở nhà, kéo dài đều đặn trong 15 tuần của học kỳ.

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

Luận văn sử dụng nguồn dữ liệu thực nghiệm gồm 120 lớp môn học, 45 giảng viên, 25 phòng học đa năng và thời khóa biểu của hơn 1500 sinh viên trong một học kỳ hoàn chỉnh. Phương pháp chọn mẫu là chọn mẫu có chủ đích kết hợp phân tầng từ cơ sở dữ liệu đào tạo thực tế, bảo đảm đại diện đầy đủ các tình huống xung đột môn học tiên quyết, giờ thực hành phòng máy và các ca học đặc thù trong tuần.

Phương pháp phân tích dựa trên việc mô hình hóa toán học các ràng buộc cứng và ràng buộc mềm vào hàm phạt chi phí, sau đó lập trình kiểm thử giải thuật tìm kiếm Tabu và đối chuẩn với các thuật toán như Leo đồi (Hill-Climbing) hay Mô phỏng luyện kim (Simulated Annealing). Lý do lựa chọn phương pháp Tabu Search là nhờ khả năng ghi nhớ thích nghi và khả năng thoát khỏi các bẫy cực trị địa phương xuất sắc mà các phương pháp heuristic trực tiếp không làm được. Quá trình nghiên cứu được thực hiện theo lộ trình 12 tháng, từ khâu khảo sát thực trạng, đặc tả yêu cầu, thiết kế kiến trúc thuật toán đến thử nghiệm trên tập dữ liệu định dạng CSV chuẩn hóa.

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

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

Quá trình chạy thực nghiệm và kiểm thử hệ thống đã mang lại những phát hiện có giá trị kỹ thuật và thực tiễn cao:

• Thuật toán Tabu đạt tốc độ hội tụ nhanh chóng, tìm ra lời giải tối ưu thỏa mãn toàn bộ các điều kiện đào tạo chỉ sau khoảng 250 đến 300 bước lặp, tương đương thời gian thực thi trung bình 45 giây trên máy tính cá nhân tiêu chuẩn.
• Tỷ lệ xung đột ràng buộc cứng được triệt tiêu hoàn toàn về mức 0%, không xuất hiện bất kỳ trường hợp nào trùng giảng viên, trùng phòng học hoặc trùng môn học bắt buộc của cùng một nhóm đối tượng sinh viên.
• Đối với các ràng buộc mềm, thuật toán giúp giảm thiểu 85% các tiết trống cách quãng không hợp lý giữa các buổi dạy của giảng viên, đồng thời tối ưu hóa khoảng 92% nguyện vọng thời gian đăng ký ca học của các đơn vị chuyên môn.
• Ứng dụng xử lý mượt mà tệp dữ liệu đầu vào định dạng CSV với dung lượng xử lý đạt trên 1000 bản ghi dữ liệu phân công mỗi giây mà không xảy ra tình trạng tràn bộ nhớ hay suy giảm hiệu năng.

Thảo luận kết quả

Nguyên nhân chính giúp giải thuật tìm kiếm Tabu vượt trội là nhờ cơ chế kết hợp giữa bộ nhớ ngắn hạn và danh sách thuộc tính cấm. Khi thuật toán rơi vào vùng cực tiểu cục bộ, thay vì dừng lại như thuật toán Leo đồi, Tabu Search chấp nhận các bước chuyển làm tăng nhẹ hàm chi phí tạm thời để khám phá lối thoát khả dĩ sang vùng giải pháp tối ưu hơn.

Khi so sánh với phần mềm mã nguồn mở Open Course Timetable, phần mềm thử nghiệm vTimeTabler của luận văn cho tốc độ xử lý nhanh hơn khoảng 30% đối với cùng một quy mô dữ liệu và thể hiện tính tương thích vượt trội với mô hình tổ chức phân nhóm lớp tín chỉ tại Việt Nam.

Dữ liệu kết quả nghiên cứu có thể được trực quan hóa sinh động thông qua biểu đồ đường biểu diễn sự suy giảm liên tục của hàm mục tiêu theo số vòng lặp, kết hợp cùng bảng ma trận đối sánh tài nguyên phòng học trước và sau khi tối ưu. Kết quả này chứng minh rằng việc kết hợp cấu trúc bộ nhớ thích nghi vào bài toán lập lịch không chỉ có giá trị lý thuyết sâu sắc mà còn hoàn toàn đủ độ chín muồi để đưa vào vận hành thực tế tại các trường đại học.

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

Nhằm phát huy tối đa kết quả nghiên cứu vào thực tiễn quản lý giáo dục, luận văn đưa ra 4 đề xuất trọng tâm:

• Chuẩn hóa và đồng bộ cấu trúc dữ liệu đào tạo: Ban Đào tạo và Phòng Công nghệ Thông tin cần hoàn thành việc số hóa 100% dữ liệu môn học, danh mục phòng học và định mức giảng viên sang định dạng tệp chuẩn trong quý 1 nhằm tạo đầu vào đồng nhất cho thuật toán.
• Tích hợp mô-đun tìm kiếm Tabu vào cổng thông tin đào tạo trực tuyến: Đội ngũ kỹ thuật phần mềm cần tiến hành tích hợp lõi thuật toán vào hệ thống quản lý tín chỉ của nhà trường trong thời hạn 6 tháng, đặt mục tiêu tự động hóa hoàn toàn quy trình xếp lịch và giảm 95% công tác can thiệp thủ công.
• Xây dựng cơ chế tự điều chỉnh tham số Tabu Tenure động: Các chuyên viên phát triển cần lập trình bổ sung tính năng tự động hiệu chỉnh độ dài danh sách cấm linh hoạt từ 7 đến 15 bước lặp dựa trên quy mô dữ liệu từng học kỳ, hoàn thành kiểm thử trong 3 tháng.
• Đào tạo tập huấn nghiệp vụ cho cán bộ giáo vụ: Đơn vị quản lý phối hợp với Khoa Công nghệ Thông tin tổ chức 4 đợt tập huấn chuyên sâu trong vòng 2 tháng trước thềm năm học mới, giúp người dùng nắm vững cách thiết lập trọng số hàm phạt và vận hành phần mềm hiệu quả.

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

• Cán bộ quản lý đào tạo và chuyên viên giáo vụ tại các trường đại học, cao đẳng: Giúp nắm bắt quy trình tự động hóa phân bổ lịch học tín chỉ, giảm thiểu áp lực công việc và tiết kiệm hơn 80% thời gian xây dựng thời khóa biểu mỗi đầu kỳ học.
• Kỹ sư phát triển phần mềm và các công ty công nghệ giáo dục: Cung cấp tài liệu thiết kế hệ thống chi tiết, phương pháp xử lý dữ liệu tệp CSV và thuật toán cốt lõi có thể tái sử dụng để xây dựng các giải pháp xếp lịch thương mại.
• Giảng viên, học viên cao học và nghiên cứu sinh ngành Khoa học Máy tính: Cung cấp cơ sở học thuật vững chắc về giải thuật Meta-heuristic, phương pháp giải bài toán tối ưu tổ hợp NP-khó và cách vận dụng cấu trúc bộ nhớ thích nghi.
• Sinh viên chuyên ngành Kỹ thuật Phần mềm và Công nghệ Thông tin: Là tài liệu tham khảo thực tế về mô hình hóa bài toán thực tiễn, phân tích thuật toán tối ưu và kỹ thuật cài đặt chương trình ứng dụng.

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

Bài toán lập lịch theo học chế tín chỉ có điểm gì phức tạp hơn bài toán thời khóa biểu niên chế truyền thống? Trong học chế niên chế, sinh viên học theo lớp cố định với danh mục môn học định sẵn. Ngược lại, học chế tín chỉ cho phép sinh viên đăng ký linh hoạt theo nhu cầu cá nhân, dẫn đến hiện tượng một sinh viên tham gia nhiều lớp môn học khác nhau, làm phát sinh hàng nghìn mối liên kết ràng buộc chéo và tăng nguy cơ trùng lịch lên gấp nhiều lần.

Giải thuật tìm kiếm Tabu khắc phục nhược điểm của thuật toán Leo đồi như thế nào? Thuật toán Leo đồi thường dừng lại và thất bại khi gặp điểm cực tiểu cục bộ vì chỉ chấp nhận các bước chuyển cải thiện hàm mục tiêu. Giải thuật tìm kiếm Tabu giải quyết triệt để vấn đề này bằng cách cho phép bước chuyển xấu hơn khi cần thiết, đồng thời sử dụng danh sách Tabu để cấm quay lại vết cũ, giúp thuật toán thoát khỏi vùng bẫy cục bộ.

Thời hạn cấm Tabu Tenure ảnh hưởng như thế nào đến chất lượng lời giải của bài toán? Nếu giá trị Tabu Tenure quá lớn, không gian tìm kiếm bị thu hẹp nghiêm trọng khiến thuật toán bỏ qua nhiều lời giải triển vọng. Nếu Tabu Tenure quá nhỏ, thuật toán dễ bị rơi vào chu kỳ lặp lại các trạng thái vừa duyệt. Do đó, việc xác lập Tabu Tenure hợp lý từ 7 đến 15 bước lặp là yếu tố then chốt để bảo đảm hiệu năng tối ưu.

Định dạng dữ liệu đầu vào của ứng dụng có dễ dàng kết nối với các hệ thống quản lý sẵn có không? Ứng dụng sử dụng cấu trúc tệp dữ liệu CSV chuẩn hóa để lưu trữ và nạp thông tin về lớp học, giảng viên, phòng ốc và ca học. Định dạng này hoàn toàn tương thích với hầu hết các cơ sở dữ liệu phổ biến như SQL Server, MySQL hay Oracle, cho phép trích xuất và đồng bộ dữ liệu nhanh chóng mà không cần thay đổi hạ tầng sẵn có.

Giải thuật tìm kiếm Tabu trong luận văn có thể mở rộng sang các bài toán quản lý giáo dục khác không? Mô hình thuật toán hoàn toàn có thể điều chỉnh linh hoạt để áp dụng cho bài toán lập lịch thi học kỳ, phân công hội đồng chấm khóa luận hoặc phân bổ ca làm việc cho nhân viên y tế và vận tải. Người quản trị chỉ cần định nghĩa lại tập biến số và cấu trúc các ràng buộc trong hàm mục tiêu tương ứng.

Kết luận

• Luận văn đã mô hình hóa thành công bài toán lập lịch học phần theo học chế tín chỉ thành bài toán tối ưu tổ hợp thỏa mãn hệ thống ràng buộc chặt chẽ.
• Cài đặt hoàn chỉnh giải thuật tìm kiếm Tabu với cơ chế bộ nhớ thích nghi, đạt hiệu năng giải quyết triệt để 100% ràng buộc cứng và tối ưu hóa vượt bậc các ràng buộc mềm.
• Xây dựng phần mềm vTimeTabler chạy trên dữ liệu thực nghiệm, cho tốc độ xử lý nhanh hơn 30% so với phần mềm Open Course Timetable và đáp ứng tốt điều kiện đào tạo tại Việt Nam.
• Đề xuất lộ trình 4 bước cụ thể giúp các cơ sở giáo dục chuyển đổi số toàn diện công tác xếp lịch học tập trong khung thời gian 12 tháng.
• Luận văn là tài liệu tham khảo giá trị cao cho các nhà quản lý giáo dục và chuyên gia công nghệ; các đơn vị đào tạo nên sớm áp dụng mô hình này để nâng cao chất lượng vận hành đào tạo ngay trong năm học tới.