- 54 -
ỨNG DỤNG FRAMEWORK VÀ LẬP TRÌNH RÀNG BUỘC CHO BÀI
TOÁN LẬP THỜI KHÓA BIỂU

Đỗ Huy Thịnh Người hướng dẫn: PGS.TS. Nguyễn Văn Vỵ
MSV: 0220310
Email: [email protected]

1. Mở đầu
Bài toán lập thời khóa biểu từ lâu luôn thu
hút được sự quan tâm của nhiều tổ chức giáo
dục và các nhà nghiên cứu bởi tính ứng dụng
cao và độ phức tạp. Các bài toán lập thời
khóa biểu rất phong phú và đa dạng bởi các
ràng buộc và yêu cầu của từng tổ chức. Bài
toán đặc trưng bởi các ràng buộc và các ràng
buộc có thể được thêm vào với nhiều mức
khác nhau. Rất nhiều chương trình đã được
lập và đưa vào sử dụng. Phần lớn các chương
trình đó được phát triển dựa trên cơ sở một
mô hình toán học chặt chẽ và thuật toán xây
dựng là dành riêng cho mô hình đó. Vì vậy
khi áp dụng, nó chỉ thích hợp với một phạm
vi hẹp mà ở đó bài toán đặt ra đúng với mô
hình đã xây dựng. Ngay trong phạm vi đó,
khi xuất hiện thêm một vài ràng buộc mới thì
kết quả đã không hiệu quả, thậm chí không
cho lời giải. Một vấn đề đặt ra là, cần phát
triển một hệ thống thời khóa biểu có thể thích
nghi được với nhiều lớp bài toán lập thời

ứng của các sự kiện.
Bài toán xếp Thời khóa biểu có thể phân
loại theo loại khuôn dạng thời gian Thời khóa
biểu: thời khóa biểu TUẦN, HỌC KỲ, nhiều
TUẦN / HỌC KỲ, THÁNG, NĂM HỌC….
Hoặc phân loại theo đơn vị xếp Thời khóa
biểu theo mô hình lớp học niên chế nay lớp
học tìn chỉ.
Trong khóa luận này chỉ xét bài toán lập
thời khoá biểu cho trường đại học ở Việt
Nam mà cụ thể là trường Đại học Công Nghệ
- Đại học Quốc Gia Hà Nội ( có thể tổng quát
cho các trường vẫn giảng dạy theo hệ lớp-
môn- giáo viên giảng dạy).
Bài toán được phát biểu như sau:
Có một danh sách các lớp học học trong
học kỳ, danh sách các môn học tương ứng
cho từng lớp học và danh sách giảng viên
tương ứng với mỗi môn cho từng lớp. Giảng
đường cho mỗi lớp đã được xếp trước.
Một lời giải hay một thời khoá biểu chấp
nhận được là tất cả các môn học được chia
vào các tiết học trong một tuần thoả mãn
điều kiện là một số ràng buộc chặt ( tại một
thời điểm một lớp chỉ học một môn và một
giáo viên chỉ dạy tối đa một lớp….) và một
số ràng buộc mở rộng ( số buổi đến trường
của giáo viên càng ít càng tốt, ngày nghỉ của
lớp, giáo viên, số tiết chờ giảng trong ngày
của giáo viên…).

không có các ký hiệu toán học.
OCL thêm các thông tin làm mô hình
UML nhất quán, hoàn thiện và rõ ràng.
4. Giới thiệu khung làm việc
Trong những năm gần đây, sự cần thiết
của sử dụng lại phần mềm ngày càng trở nên
quan trọng. Hướng đối tượng làm tăng khả
năng sử dụng mã bằng cách cung cấp thừa kế
và các giao diện chuẩn. Các thư viện lớp
cung cấp các thành phần xây dựng sẵn có thể
dùng lại được, nhưng việc sử dụng các thư
viện lớp chủ yếu dẫn đến dùng lại mã nguồn
và chỉ một ít là dùng lại phân tích thiết kế. Để
tăng khả năng sử dụng lại của phân tích thiết
kế, các khung làm việc hướng đối tượng ra
đời.
Một khung làm việc hướng đối tượng là
một tập các lớp cộng tác tạo thành một thiết
kế có thể dùng lại được cho một lớp cụ thể
phần mềm.
Khung làm việc quyết định kiến trúc của các
ứng dụng dùng nó bằng cách chia thiết kế
thành các lớp trìu tượng và định nghĩa các
trách nhiệm, cộng tác và luồng điều khiển
giữa các lớp. Phát triển khung làm việc nhấn
mạnh tới dùng lại thiết kế hơn là dùng lại mã
nguồn. Các kỹ thuật hướng đối tượng như
thừa kế, đa hình cho phép xây dựng các
khung làm việc có thể thực thi bằng cách chia
nhỏ nó thành các lớp, cắm thêm các thành

[1] Nguyễn Việt Hùng, Nguyễn Văn Tuân - Xây dựng
thời khóa biểu bằng cách kết hợp phương pháp
Heuristics và tương tác người máy - Khóa luận tốt
nghiệp đại học 2005, Đại học Công nghệ - ĐHQGHN.
[2] Vũ Văn Thạch - Ứng dụng khung làm việc cho bài
toán lập lịch - Khóa luận tốt nghiệp đại học 2005, Đại
học Công nghệ - ĐHQGHN
[3] PGS.TS. Nguyễn Văn Vỵ - Bài gi
ảng Phân tích
thiết kế hệ thống phần mềm theo hướng đối tượng -
Bộ môn Công nghệ phần mềm, Đại học Công nghệ -
ĐHQGHN, Hà Nội, 2004. 109 tr.
- Tài liệu tham khảo tiếng Anh
[4] Michael Boggs, Wendy Boggs - Mastering UML
With Rational Rose 2002 - Sybex.
[5] Desmond Francis D’Souza, Alan Cameron Wills -
Objects, Components, and Frameworks with UML -
Addison Wesley, 1999.
[6] Anneke Kleppe, Jos Warmer - Object Constraint
Languate, The: Getting Your Models Ready for MDA,
Second Edition - Addision Wesley, 2003.