Link tải luận văn miễn phí cho ae Kết nối
Tóm tắt
Luận án này tập trung giải quyết bài toán xếp thời khóa biểu dựa trên nhóm học
phần có mang đặc trƣng riêng của các trƣờng đại học Việt Nam, một bài toán có
nhiều ứng dụng trong thực tế.
Điểm khác biệt giữa bài toán xếp thời khóa biểu môn học tại các trƣờng đại học
của Việt Nam với các bài toán xếp thời khóa biểu đại học trên thế giới là sự đa dạng
hơn về mặt ràng buộc, ví dụ: một phân công khi đƣợc sắp thời khóa biểu có thể đƣợc
chia ra nhiều cụm (block element), một một cụm phải đƣợc gán vào một buổi và các
cụm của một phân công (activity) cần gán vào các ngày khác nhau; một buổi
dạy/học của giảng viên và lớp học cần đƣợc hạn chế số lƣợng tiết lủng; lịch
giảng dạy của giảng viên cần đƣợc cực tiểu hóa số lƣợng buổi dạy khi có yêu cầu.
Thách thức của bài toán xếp thời khóa biểu môn học là bài toán bùng nổ tổ hợp,
không gian tìm kiếm lớn, trong khi đó thời gian yêu cầu để thuật giải chạy cho ra lời
giải phải trong khoảng thời gian chấp nhận đƣợc.
Luận án này tập trung vào các phƣơng pháp theo hƣớng tiếp cận metaheuristic bởi
vì hƣớng tiếp cận này đƣợc sử dụng rất thông dụng để giải quyết các bài toán xếp thời
khóa biểu, một trong những lớp bài toán dạng NP-khó. Tuy nhiên việc áp dụng các
thuật toán theo hƣớng tiếp cận này là không đơn giản bởi vì việc áp dụng một thuật
giải metaheuristic vào một bài toán đặc thù cần sự tinh tế trong việc biểu diễn lời giải,
khởi tạo lời giải ban đầu, thực hiện việc tìm kiếm lời giải trong không gian lời giải.
Hơn nữa, với sự đa dạng của các thuật toán đã công bố, việc đánh giá để lựa chọn
thuật toán tối ƣu cho bài toán xếp thời khóa biểu với đặc thù Việt Nam là rất cần thiết.
Do đó luận án này tập trung làm rõ các vấn đề sau:
- Đánh giá, so sánh, và đề xuất một số cải tiến các thuật giải hiện có cho bài
toán xếp thời khóa biểu môn học của Việt Nam. Đóng góp của luận án bao
gồm:
o (i) đề xuất một mô hình Toán học (integer formulation for the course
timetabling problem)[CT12] để có thể đánh giá các thuật toán một cách
hiệu quả. Mô hình này là cần thiết bởi vì các thuật toán hiện có đƣợc
đánh giá ở nhiều ngữ cảnh, ràng buộc khác nhau dẫn đến sự không nhất
quán trong so sánh hiệu quả của các thuật toán.
o (ii) phân tích, đánh giá các thuật toán nhƣ TabuSearch [CT2][CT3],
thuật giải tui luyện thép (SA)[CT4], thuật giải Variable Neighborhood
Search [CT5], thuật giải Memetic [CT7], thuật giải Particle Swarm
Optimization [CT6] và thuật giải bầy ong (Bees Algorithm) [CT8] dựa
trên mô hình đã đề xuất cho tập dữ liệu thực tế thu thập tại trƣờng ĐH
Khoa Học Tự Nhiên Tp. HCM. Đây là tập dữ liệu có độ phức tạp cao
với 10 ràng buộc cứng, 10 ràng buộc mềm sát với thực tế triển khai.
o (iii) đề xuất một số cải tiến dựa trên các phân tích trên. Cụ thể, với thuật
toán Tabu Search, SA, VNS để tối ƣu bộ nhớ, khi khám phá không gian
lân cận, luận án đề xuất chỉ lƣu trữ các phép chuyển thay cho lƣu trữ
các lời giải lân cận. Kỹ thuật này đƣợc tiếp tục áp dụng cho các thuật
giải SA, VNS, Memetic. Với thuật toán PSO, luận án đề xuất khái niệm
vị trí, vận tốc trong việc ứng dụng thuật toán. Với các đề xuất mới này,
việc cài đặt các thuật toán đƣợc đơn giản hơn, và tốc độ xử lí đƣợc cải
tiến rất đáng kể.
- Nghiên cứu cách kết hợp các thuật toán hiện có sao cho đạt hiệu quả tối ƣu
hơn. Cụ thể luận án đã đề xuất các phƣơng pháp kết hợp giữa các thuật giải
GA-Bees[CT9], Harmony-Bees[CT10], GA-SA[CT11], Bees-VNS, Bee-PSO.
Ý tƣởng chính của việc kết hợp các thuật toán là nhằm tăng tính đa dạng và
mở rộng không gian tìm kiếm hết khả năng có thể. Kết quả thực nghiệm cho
thấy sự vƣợt trội của các phƣơng pháp kết hợp này so với các phƣơng pháp áp
dụng đơn thuần một thuật giải.
Chương 1
Giới thiệu bài toán
1.1 Dẫn nhập
Xếp thời khóa biểu là một trong những công việc quan trọng và thƣờng xuyên ở
các đơn vị nhƣ trƣờng đại học. Đây là một công việc khá cực nếu thực hiện bằng tay,
bởi vì ngƣời xếp lịch phải xử lí một khối lƣợng lớn các ràng buộc liên quan đến thời
khóa biểu bao gồm cơ sở vật chất (phòng học, máy chiếu, micro), lịch rảnh của giảng
viên, số môn học, số lớp học, và số lƣợng phân công.
Bên cạnh đó, với đặc thù của các trƣờng ĐH ở Việt Nam, các giảng viên cũng
thƣờng đặt ra những yêu cầu nhất định về mặt thời gian đối ngƣời xếp lịch, cộng với
việc lịch học phải cố gắng đƣợc sắp xếp làm sao để tiện cho sinh viên, tránh việc lãng
phí thời gian khi bắt sinh viên phải ngồi chờ quá lâu giữa các môn trong cùng một
buổi, một ngày. Việc sắp xếp lịch làm sao để có thể tận dụng đƣợc tối ƣu nguồn tài
nguyên mà vẫn đảm bảo đƣợc các yêu cầu rất cơ bản này là một công việc thật sự khó
khăn và vất vả cho ngƣời xếp lịch.
Chính vì lí do đó, bài toán xếp thời khoá biểu cho giáo dục từ lâu đã nhận đƣợc sự
quan tâm của các nhà nghiên cứu nhằm đề xuất ra các thuật giải giúp hỗ trợ giải quyết
bài toán một cách tự động bằng máy tính. Khởi đầu từ bài báo của tác giả Gotlieb vào
năm 1963[18], cho đến nay, đã có rất nhiều hƣớng tiếp cận đƣợc đƣa ra cho lớp bài
toán này. Trên thực tế, do sự đa dạng về nhu cầu và qui định của các trƣờng, đã xuất
hiện rất nhiều biến thể khác nhau của bài toán xếp thời khóa biểu. Dựa theo bài khảo
sát của tác giả A. Schaerf[5] và bài báo cáo kĩ thuật của cuộc thi Xếp thời khóa biểu
quốc tế 2007[10] (International Timetabling Competition 2007 – gọi tắt là ITC07), có
thể phân các bài toán xếp thời khóa biểu cho giáo dục thành ba nhóm chính:
Bài toán xếp thời khóa biểu cho trƣờng phổ thông (high school timetabling)
Bài toán xếp thời khóa biểu cho trƣờng đại học (course timetabling)
tMZsc3241Fgq0Z1
