ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
ĐỒ ÁN MÔN HỌC

THUẬT TOÁN VÀ PHƯƠNG PHÁP
GIẢI QUYẾT VẤN ĐỀ
XÂY DỰNG GIẢI PHÁP
LẬP THỜI KHÓA BIỂU TẠI TRƯỜNG ĐẠI HỌC
TÀI NGUYÊN VÀ MÔI TRƯỜNG TP.HCM
GVHD : PGS. TS. Đỗ Văn Nhơn
HVTH : Lê Thành Nguyên
MSHV : CH1301102
TP HCM, Tháng 09 năm 2014
MỤC LỤC
2
DANH MỤC BẢNG
3
DANH MỤC HÌNH
4
GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên
PHẦN 1: MỞ ĐẦU
Nước ta đang thực hiện công cuộc công nghiệp hóa hiện đại hóa nhằm thúc đẩy
nền kinh tế phát triển mạnh mẽ. Trong quá trình này, vai trò nền tảng của giáo dục, đặc
biệt là giáo dục Đại học đã được xã hội ghi nhận và phát huy. Từ đó, nhiệm vụ giáo dục
và cấu trúc quản lý của hệ thống đào tạo đại học đang đối mặt với một thử thách to lớn
trước sự tăng trưởng theo cấp số nhân của số lượng sinh viên và yêu cầu ngày càng cao
của xã hội.
Để đáp ứng nhu cầu trên, hệ thống đào tạo theo tín chỉ đã ra đời và được hầu hết
các trường đại học trong cả nước áp dụng. Song song đó đã phát sinh hàng loạt những
thách thức trước yêu cầu thay đổi cơ sở hạ tầng quản lý. Trong đó, việc xếp thời khóa
biểu và chương trình xếp thời khóa biểu môn học là một trong những yêu cầu không thể

chuyên ngành lập bảng phân công giảng dạy học kỳ tiếp theo dựa vào kế hoạch đào tạo
và chương trình khung của từng ngành đã được Hiệu trưởng phê duyệt, gửi về Phòng Đào
tạo.
B2: Phòng Đào tạo tổng hợp bảng phân công giảng dạy nhận được.
B3: Dựa vào bảng phân công giảng dạy Phòng Đào tạo sẽ lập kế hoạch bố trí buổi
học cho từng ngành/ chuyên ngành nhằm phân phối đều tài nguyên vào từng buổi.
B4: Phòng Đào tạo tiến hành xếp thời khóa biểu dựa trên bảng phân công giảng
dạy và kế hoạch bố trí buổi.
B5: Phòng Đào tạo gửi thời khóa biểu đã lập về các khoa/ bộ môn lấy ý kiến giảng
viên.
B6: Điều chỉnh lịch dạy theo yêu cầu giảng viên (nếu có thể) và phát hành thời
khóa biểu chính thức.
6
Hình 1. Quy trình xếp TKB tại trường ĐH TNMT TP.HCM
GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên
Trong chuyên đề này sẽ tập trung giải quyết công việc tại bước 4, trong đó sẽ tìm
giải pháp cho các vấn đề gặp phải trong quá trình xếp thời khóa biểu tự động, tối ưu hóa
thời khóa biểu. Bài toán xếp thời khóa biểu có thể xem là bài toán tối ưu hóa nhằm thỏa
mãn các ràng buộc trong quá trình lập lịch.
2.1. Đặc điểm và khó khăn khi giải bài toán
Trong việc xếp thời khóa biểu có thể chia thành hai loại ràng buộc: ràng buộc
cứng và ràng buộc mềm. Ràng buộc cứng là các ràng buộc phải được thỏa mãn. Ràng
buộc mềm, tuy có thể vi phạm, nhưng càng thỏa mãn nhiều ràng buộc mềm càng tốt.
Như đã biết việc xếp thời khóa biểu theo phương pháp thủ công của con người
phải tốn rất nhiều thời gian và công sức,… nhưng hiệu quả đem lại không cao. Vì vậy,
nhiều nghiên cứu khoa học và thực tiễn đã tập trung nghiên cứu ứng dụng khoa học máy
tính vào việc xếp thời khóa biểu cho các trường đại học, cao đẳng, phổ thông…và đã đạt
được một kết quả nhất định. Nhưng do mỗi trường có những đặc thù về quy trình công
việc, cơ sở vật chất,…cần giải quyết khác nhau và hầu như không có ngoại lệ.
Do đó, để thực hiện được công việc này với kết quả khả thi, chúng ta phải dựa trên

nhau (Trường ĐH Tài nguyên và Môi trường có hai cơ sở đào tạo, trụ sở tại địa
chỉ 236B Lê Văn Sỹ, Phường 1, Quận Tân Bình TP.HCM và cơ sở 2 tại ấp
Long Đức 3, xã Tam Phước, TP. Biên Hòa, Đồng Nai).
2.1.2. Ràng buộc mềm
Ràng buộc mềm được hiểu như là các yêu cầu, điều kiện hạn chế vi phạm trong
quá trình lập thời khóa biểu. Ràng buộc mềm cho thời khóa biểu tại trường Đại học Tài
nguyên và Môi trường TP.HCM có thể được liệt kê như sau:
Ràng buộc về thời gian:
− Lịch dạy/học của một giảng viên/sinh viên phải liên lục trọn trong một buổi,
không có ca trống xen giữa.
− Hạn chế bố trí những ca đơn trong nhiều ngày.
− Hai ca học của một một môn học dành cho một lớp không nên bố trí trong
cùng một ngày.
− Lịch học của một sinh viên hạn chế những ngày học cả hai buổi.
− Nhằm tối ưu về thời gian rãnh của giảng viên cũng như sinh viên, nên bố trí
lịch mới sao cho thời gian bận chung thay đổi ít nhất.
Ràng buộc về không gian:
− Hạn chế di chuyển xa khi giảng viên/sinh viên đổi ca.
− Hạn chế những ngày giảng viên dạy xen kẽ ở hai cơ sở.
− Phòng học phải được sử dụng với tần suất cao nhất và tối ưu sức chứa.
− Hạn chế bố trí phòng ở tầng cao cho giảng viên lớn tuổi.
8
GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên
9
GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên
PHẦN 3: GIẢI PHÁP LẬP THỜI KHÓA BIỂU
3.1. Dữ liệu cho trước
− Tập hợp học kỳ:
SM = {(id, startWeek, numberWeek, numberDay, numberSession)}.
− Tập hợp khu giảng đường:

gian và phòng học đầy đủ.
MT = {(id, assignment, startWeek, numberWeek, day, session, room) | room ∈
RM ∧ day < assignment.semester.numberDay ∧ session < assignment.semester.
numberSession}
Tập MT được gọi là thời khóa biểu hợp lệ khi:
− ∀mt ∈ MT, mt đã được bố trí thời gian và phòng học sao cho:
+ Có duy nhất một ca được bố trí tại phòng được xếp cho mt trong khoảng
thời gian ca mt diễn ra.
+ Các giảng viên/lớp liên quan có duy nhất một ca trong khoảng thời gian ca
mt diễn ra.
3.4. Giải thuật lập thời khóa biểu
Đối với bài toán lập thời khóa biểu, giải pháp thông thường là xem xét tất cả các
trường hợp có xảy ra của một ca học và thiết lập thời gian, phòng học cho chúng. Quá
trình này nhanh hay chậm phụ thuộc số lượng ràng buộc của bài toán. Chính quá trình
này dẫn đến độ phức tạp của giải thuật có dạng O(n
k
* numberDay * numberSession),
trong đó, n = |MT| và k =|CT|. Tuy nhiên, giải thuật vét cạn cho kết quả không tốt.
Tuy nhiên, nếu quá trình trên được thực hiện theo một định hướng tốt, kết quả đạt
được có nhiều thay đổi đáng kể nâng cao chất lượng lời giải. Do đó, chuyên đề này sẽ
ứng dụng giải thuật heuristic xây dựng giải pháp xếp thời khóa biểu cho trường Đại học
Tài nguyên và Môi trường.
3.4.1. Các định hướng
Ưu tiên xếp lịch cho các ca có thời gian dài trước, thời gian ngắn sau.
Ưu tiên xếp lịch cho các ca bắt đầu sớm trước, muộn sau.
11
GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên
Ưu tiên xếp lịch cho các ca có giảng viên/ lớp có thời gian rãnh ít trước, nhiều sau.
Ưu tiên xếp lịch cho các ca có số lượng sinh viên lớn trước nhỏ sau.
Ưu tiên xếp lịch cho các ca có độ xung đột về giảng viên/lớp cao trước, thấp sau.

12.Chọn tuần bắt đầu w tiếp theo trong tập MT.
12
GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên
Trở về bước 2.
//Tính độ xung đột giảng viên, lớp
function computeConflict(MT){
for(i= 0, i < |MT|, i++){
for(j =0; j < |MT|, j++){
if(I <> j){
if(M[i].lecturer = M[j].lecturer){
conflictLecturer[i][j] = true;
conflictLecturer[j][i] = true;
}
if(M[i].clazz == M[j].clazz){
conflictClazz[i][j] = true;
conflictClazz[j][i] = true;
}
}
}
}
}
//Tính độ ưu tiên cho mt
function computeScore(mt, day, session){
//Duyệt tập ràng buộc cứng
for(hct in HCT){
score *= hct(mt, day, sesion) * w
hct
;
}
//Duyệt tập ràng buộc mềm

tìm kiếm mt trên M, 1 phép xóa và 10 phép tìm ca xung đột với mt và 10 phép
xóa: 13 + 11lg|M| (10 là số ca tối đa xung đột với mt).
Giải thuật thực hiện 1 lần dòng 1, numberDay * numberSession lần các dòng 2, 3,
4, 5 và |MT| lần các dòng 6, 7, 8, 9, 10, 11. Trong đó, numberDay = 5 và
numberSession = 6.
Suy ra: T = lg54 + 30 * (|MT| + |M|
2
+ |M||CT| + |M|lg|M|)
+ |MT| (2|RM| + 14 + 11lg|M|)
= lg54 + 44|MT| + 30|M|
2
+ 30|M|(|CT| +lg|M|)
+ 2|MT||RM| + 11|MT|lg|M|
< |MT|
2
+ 44|MT|
2
+ 30|MT|
2
+ 30|MT|
2
+ 2|MT|
2
+ 11|MT|
2

< 118|MT|
2
Kết luận, độ phức tạp thời gian của thuật toán xếp thời khóa biểu áp dụng heuristic
có độ phức tạp O(n

Name Tên giảng đường Chuỗi No
Bảng 3. Cấu trúc bảng dữ liệu building
Lưu trữ thông tin phòng học
15
GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên
Tên trường Mô tả Kiểu dữ liệu Tự phát sinh
ID Trường khóa chính Số nguyên dương Yes
Name Tên phòng học Chuỗi No
Capacity Sức chứa Số nguyên dương No
Type Loại phòng học LT/TH Boolean No
Building Mã giảng đường Số nguyên dương No
Floor Tầng cao Số nguyên dương No
DeptID Mã khoa quản lý phòng Số nguyên dương No
Bảng 4. Cấu trúc bảng dữ liệu room
Lưu trữ thông tin môn học
Tên trường Mô tả Kiểu dữ liệu Tự phát sinh
ID Khóa chính Chuỗi No
Name Tên môn học Chuỗi No
LT Số tín chỉ lý thuyết Số nguyên dương No
BT Số tín chỉ bài tập Số nguyên dương No
TH Số tín chỉ thực hành Số nguyên dương No
Level Hệ đào tạo Số nguyên dương No
DeptID Mã khoa quản lý môn học Số nguyên dương No
Bảng 5. Cấu trúc bảng dữ liệu course
Lưu trữ thông tin giảng viên
Tên trường Mô tả Kiểu dữ liệu Tự phát sinh
ID Khóa chính Chuỗi No
Name Họ tên giảng viên Chuỗi No
BirthYear Năm sinh Số nguyên dương No
Sex Giới tính Boolean No

Mã phân công giảng dạy Số nguyên dương No
StartWeek Tuần bắt đầu học Số nguyên dương No
Day Thứ trong tuần Số nguyên dương No
Session Ca trong ngày Chuỗi No
RoomID Mã phòng học Số nguyên dương No
Bảng 9. Cấu trúng bảng meeting
Do chương trình được sử dụng trong xếp và quản lý lịch giảng dạy của toàn
trường. Dữ liệu này được lưu trữ phục vụ công tác tra cứu khối lượng giảng dạy của
giảng viên và các yêu cầu quản lý khác. Do đó, dữ liệu liên tục tăng trong thời gian thực
sẽ ảnh hưởng tốc độ thực thi của toàn hệ thống và khó khăn trong bảo trì và cập nhật dữ
liệu.
17
GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên
Nhằm cải thiện hiệu suất của chương trình, cơ sở dữ liệu được chia thành 2 phần:
phần dữ liệu dùng chung cho các năm học (dữ liệu có trước) sẽ được lưu trữ trong
schema public gồm các bảng dữ liệu chứa thông tin của dữ liệu có trước được mô tả
trong phần 3, phần dữ liệu phân công giảng dạy và thời khóa biểu sẽ được lưu trong các
schema khác nhau – mỗi schema chứa dữ liệu xếp thời khóa biểu của một năm học.
4.2. Giao diện chương trình
Chương trình lập thời khóa biểu tại trường Đại học Tài nguyên và Môi trường TP.
HCM đã phát triển dựa trên ngôn ngữ lập trình Java, cơ sở dữ liệu được quản lý bởi hệ
quản trị cơ sở dữ liệu mã nguồn mở PostgreSQL. Chương trình đã cung cấp khá đầy đủ
các chức năng quản lý dữ liệu và thời khóa biểu bao gồm các chức năng nhập liệu, xuất
dữ liệu, lọc và sắp xếp dữ liệu theo yêu cầu tác nghiệp của người dùng. Ngoài ra, thời
khóa biểu có thể được xuất theo nhiều mẫu gồm: thời khóa biểu toàn bộ, thời khóa biểu
theo khoa/Bộ môn, thời khóa biểu theo lớp hay thời khóa biểu cá nhân dành cho giảng
viên,…
Hình 2. Giao diện quản lý giảng đường
18
GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên

Ngoài ra, hệ thống có thể đáp ứng các yêu cầu quản lý khác: cung cấp lịch bận
phòng học, lớp quản lý, kê khai khối lượng giảng dạy,… đã giảm được khối lượng lớn
công việc thủ công.
4.3.3. Hạn chế
Dữ liệu phục vụ quá trình xếp thời khóa biểu tương đối lớn, không thể nạp toàn bộ
vào bộ nhớ máy tính. Do đó, hầu hết các kiểm tra luật trong thời gian thực thi phải truy
xuất vào cơ sở dữ liệu là nguyên nhân chính ảnh hưởng đến tốc độ chương trình.
Trong quá trình xếp thời khóa biểu, người dùng phải tính toán thủ công để lập kế
hoạch phân buổi học cho từng ngành.
Thời khóa biểu lập được vẫn còn một lượng nhỏ ca học không thể xếp lịch, phần
này phải được điều thủ công.
22
GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên
TÀI LIỆU THAM KHẢO
[1] Bài giảng Thuật toán và phương pháp giải quyết vấn đề – PGS. TS Đỗ Văn
Nhơn - Đại học Quốc Gia Thành Phố Hồ Chí Minh.
[2] Nguyễn Chí Trung, Nguyễn Thị Thu Thủy(2010), “Phân tích thiết kế thuật
toán và đánh giá độ phức tạp giải thuật”, Đại học sư phạm Hà Nội.
23
GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên
PHỤ LỤC
Phụ lục 1. Danh sách phòng ban/ Khoa/ BM
MÃ KHOA/BM TÊN KHOA/BM MÃ KHOA/BM TÊN KHOA/BM
2 Phòng Tổ chức Cán bộ 3 Phòng Đào tạo
4 Phòng Khảo thí & ĐBCL 5 Phòng Thanh tra
6 Phòng Quản lý NCKH 7 Phòng Kế hoạch tài chính
8 Phòng Công tác học sinh sinh viên 9 Phòng Quản trị vật tư
11 Khoa Khoa học Đại cương 12 Khoa Lý luận chính trị
13 Khoa Khí tượng thủy văn – Tài nguyên nước 14 Khoa Môi trường
15 Khoa Quản lý đất đai 16 Khoa Trắc địa – Bản đồ

14.20 Nguyễn Đình Đức 1980 Nam 14
16.02 Nguyễn Hữu Đức 1980 Nam 16
11.22 Nguyễn Thành Đức 1980 Nam 11
11.33 Nguyễn Thị Như Dung 1980 Nữ 11
11.31 Nguyễn Lương Tuấn Dũng 1980 Nam 11
24
GVHD: PGS. TS. Đỗ Văn Nhơn HVTH: Lê Thành Nguyên
MÃ GV HỌ TÊN NĂM SINH GIỚI KHOA/BM
05.01 Nguyễn Tiến Dũng 1980 Nam 5
17.16 Võ Văn Tuấn Dũng 1980 Nam 17
16.14 Đào Mạnh Dũng 1980 Nam 16
11.40 Hồ Chí Dũng(TG) 1980 Nam 11
11.44 Phạm Tiến Dũng(TG) 1980 Nam 11
16.12 Đặng Văn Em 1980 Nam 16
14.41 Phạm Thị Thanh Hà 1980 Nữ 14
14.30 Đinh Thị Thu Hà 1980 Nữ 14
14.42 Hoàng Ngọc Hà 1980 Nam 14
14.02 Nguyễn Thị Vân Hà 1980 Nữ 14
16.19 Trịnh Ngọc Hà 1980 Nam 16
18.08 Đặng Bắc Hải 1980 Nam 18
11.46 Nguyễn Minh Hải(TG) 1980 Nam 11
14.19 Huỳnh Thị Ngọc Hân 1980 Nữ 14
14.05 Huỳnh Thị Ngọc Hân 1980 Nữ 14
11.23 Nguyễn Thị Thúy Hằng 1980 Nữ 11
11.13 Nguyễn Thanh Hằng 1980 Nữ 11
11.25 Nguyễn Thị Hằng 1980 Nữ 11
15.05 Huỳnh Thị Thanh Hạnh 1980 Nữ 15
19.14 Hoàng Thị Hồng Hạnh 1980 Nữ 19
15.03 Trần Mỹ Hảo 1980 Nam 15
20.07 Nguyễn Tiến Hảo 1980 Nam 20