- 42 -
XÂY DỰNG THỜI KHOÁ BIỂU BẰNG CÁCH KẾT HỢP PHƯƠNG
PHÁP HEURISTICS VÀ TƯƠNG TÁC NGƯỜI MÁY
Nguyễn Việt Hùng Người hướng dẫn: PGS.TS. Nguyễn Văn Vỵ
MSV: 0122197
Email:
Nguyễn Văn Tuân
MSV:0122216
Email:mailto:
1. Giới thiệu
Lập thời khoá biểu là bài toán có
ứng dụng thực tế cao và được nhiều
người quan tâm trong vận trù học. Tuy
vậy, nó thuộc loại bài toán NP-khó với
nhiều loại ràng buộc phức tạp, nên khó
giải bằng các thuật toán truyền thống.
Đến nay, các thuật toán mô phỏng tự
nhiên tỏ ra là phương pháp hữu hiệu hơn
cả nhưng vẫn bị hạn chế vì thời gian
chạy chương trình khá lâu và không linh
hoạt khi ta thay đổi các ràng buộc.
Để giải quyết bài toán, chúng tôi đề
xuất một cách giải quyết bài toán này
bằng cách kết hợp phương pháp
Heuristics và tương tác người máy.
Theo cách tiếp cận này, thời khoá biểu
sẽ được xây dựng theo cách đánh giá
kinh nghiệm và tìm giải pháp qua thử
nghiệm và rút tỉa khuyết điểm kết hợp
với phương pháp gắp thả.


Việt Nam mà cụ thể là trường Đại học
Công Nghệ - Đại học Quốc Gia Hà Nội.
3.2. Các cách tiếp cận hiện nay
Có rất nhiều thuật toán đươc đề
xuất để giải gần đúng các bài toán NP-
khó. Các thuật toán này tìm được lờ
i
giải gần tối ưu và là một trong những xu
thế phát triển hiện nay đối với các bài
toán chưa thể tìm ra lời giải tối ưu thực
sự trong đó các thuật toán mô phỏng
theo tự nhiên như thuật toán luyện kim,
thuật toán di truyền, thuật toán hệ kiến
…Trong đó thuật toán di truyền và thuật
toán hệ kiến tỏ ra là phương pháp khá
hiệu quả.

4.Phương pháp heuristics trong
bài toán
4.1. Ý tưởng
- 43 -
Từ thực tế cho thấy, mỗi giảng viên
trong một kì chỉ dạy một hoặc vài lớp,
mỗi lớp chỉ giảng dạy một môn, cho nên
tập nghiệm cho bài toán là rất lớn. Cho
nên sử dụng phương pháp heuristics kết
hợp với gắp thả sẽ tiết kiệm được rất
nhiều thời gian và sẽ cho kết quả chấp
nhận đuợc. Nhưng sử dụng phương
pháp heuristics như thế nào cho đạt hiệu


4.2. Thử nghiệm và kết quả
Chúng tôi đã cài đặt và chạy thử
nghiệm trên cơ sở dữ liệu của 3 năm gần
đây trong trường Đại Học Công Nghệ.
Kết quả đạt được là khá khả quan.
Trong tổng số lớp của trường Công
Nghệ, số giảng viên, và các môn học.
Thời gian chạy của chương trình là < 1
giây, kết quả đạt được bước dầu là khá
khả quan: tổng số tiết phải đợi trong một
kì của tất cả các giảng viên ~ 4.

4.3. Đánh giá chung
Chương trình đã chạy khá tốt với
bài toán lập thời khoá biểu cho trường
ĐH Công Nghệ.
Chương trình có thể chạy tốt trong
bài toán mà có tập nghiệm lớn. Ràng
buộc càng ít thì kết quả sẽ càng khả
quan. Khi ràng buộc nhiều, kết quả s
ẽ
không được tốt như một số các phương
pháp khác. Bài toán này phụ thuộc nhiều
vào các ràng buộc hơn là phụ thuộc vào
kích cỡ của dữ liệu.

5.Kết luận
Trong khoá luận này chúng tôi đã
sử dụng phương pháp Heuristics để giải