ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

NGUYỄN TẤN TRẦN MINH KHANG
NGHIÊN CỨU ỨNG DỤNG CÁC GIẢI THUẬT
METAHEURISTIC CHO BÀI TOÁN XẾP THỜI
KHÓA BIỂU MÔN HỌC TRƯỜNG ĐẠI HỌC Chuyên ngành: Khoa học máy tính
Mã số chuyên ngành: 62 48 01 01
TÓM TẮT LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN
Tp.Hồ Chí Minh – Năm 2013

Luận án được hoàn thành tại:
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
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 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.
- Đề xuất một mô hình Toán học (unified framework) để 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.
- Phân tích, đánh giá các thuật toán nhƣ TabuSearch (TS), Simulated
Annealing (SA), thuật giải Variable Neighborhood Search (VNS),
thuật giải Genetic Algorithm (GA), thuật giải Memetic Algorithm
(MA), thuật giải Particle Swarm Optimization (PSO), thuật giải
Harmony Search (HS) và thuật giải Bees Algorithm (Bees) 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 2
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.
- Đề 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 TS, 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, MA. 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 độ

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.
Bài toán thời khóa biểu có thể phân 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)
- Bài toán xếp lịch thi (examination timetabling).

CHƯƠNG 2: MÔ HÌNH HÓA BÀI TOÁN THỜI KHÓA BIỂU MÔN
HỌC VÀ CÁC PHƯƠNG PHÁP TIẾP CẬN
2.1 Mô hình hóa bài toán
2.1.1 Các kí hiệu
Bài toán bao gồm các yếu tố cho sẵn sau:
- Tập  tập các tiết học trong một tuần. 4
- Tập : tập các ngày học trong một tuần.
- Tập 

: tập các tiết học của ngày thứ  trong tuần.
- Tập : tập các buổi học (ví dụ: buổi sáng, buổi chiều) trong một
tuần.
- Tập 



cho biết thời gian dạy mong muốn của giáo viên:







với .
- Ma trận 

cho biết giờ rảnh của lớp học:





 

với .
- Tập : tập các phòng học.
- 

: cho biết sức chứa của phòng học , với .
- Ma trận 

cho biết giờ rảnh của phòng học:





 khi và chỉ khi tiết bắt đầu
của BlockElement  đƣợc gán sẵn vào tiết  và phòng .
- Tập 

: tập các BlockElement thuộc về phân công , với .
- Tập 

: tổng số tiết học của BlockElement , với .
- Tập 

: tập các BlockElement do giáo viên  giảng dạy, với 
.
- Tập 

: tập các BlockElement mà lớp học  có tham gia học, với
.
- Tập : tập các nhóm học phần (curriculum) – mỗi nhóm học phần
là một tập các phân công mà không đƣợc xếp trùng giờ nhau do yêu
cầu của khoa quy định.
- Tập 

: các phân công thuộc thuộc nhóm học phần lớp học .

2.1.2 Các biến của mô hình
Tất cả các biến quyết định và các biến bổ trợ đều là các biến nhị phân -
chỉ nhận một trong hai giá trị là 0 hoặc 1.
- Biến quyết định (decision variable): 

với ,


nếu lớp học  tham gia học BlockElement  vào tiết  tại
phòng , 

 nếu ngƣợc lại.

2.1.3 Mô hình hóa các ràng buộc cứng
- Ràng buộc về tính liên tục của BlockElement và tính duy nhất của
phòng học của BlockElement: Tất cả các tiết học của cùng một
BlockElement phải diễn ra liền kề nhau và tại cùng một phòng.


  

 


- Ràng buộc đụng độ giáo viên: Một giáo viên không thể dạy nhiều
hơn một BlockElement tại cùng một thời điểm.
  



- Ràng buộc đụng độ lớp học: Một lớp học không thể tham gia học
nhiều hơn một BlockElement tại cùng một thời điểm.
  



- Ràng buộc đụng độ phòng học: Một phòng học chỉ đƣợc gán cho

các BlockElement của tất cả các phân công phải đƣợc gán vào một
và chỉ một tiết bắt đầu và một và chỉ một phòng học nào đó.
  



- Ràng buộc về buổi của BlockElement: Với mỗi BlockElement, tất
cả các tiết đƣợc gán đều phải thuộc cùng một buổi.
 












 


 

 
- Ràng buộc về ngày của phân công: Các BlockElement khác nhau
của cùng một phân công phải đƣợc gán vào các ngày khác nhau.
   

Khác với các ràng buộc cứng, đối với các ràng buộc mềm, yếu tố đƣa
vào mô hình bài toán không phải là công thức biểu diễn ràng buộc, mà thay
vào đó là công thức biểu diễn số lƣợng vi phạm của ràng buộc nhằm đƣa vào
hàm mục tiêu.
- Ràng buộc di chuyển của giáo viên giữa các nhóm phòng học: Cần
hạn chế việc một giáo viên phải di chuyển giữa các nhóm phòng
học khác nhau trong cùng một ngày. Số vi phạm của ràng buộc này
đƣợc biểu diễn nhƣ sau:


       

 


















   

mà:


  





  








- Ràng buộc giờ lủng của giáo viên theo ngày: Hạn chế trƣờng hợp
một giáo viên phải dạy nhiều BlockElement trong cùng một ngày
mà lại phải nghỉ giữa các BlockElement này. Số vi phạm của ràng
buộc này (kí hiệu: 

 là số bộ











 9
- Ràng buộc tổng số tiết dạy tối đa của giáo viên: Hạn chế trƣờng
hợp một giáo viên phải dạy nhiều hơn 9 tiết một ngày. Số vi phạm
của ràng buộc này đƣợc tính bằng công thức sau:


      




 


- Ràng buộc thời gian dạy mong muốn của giáo viên: Hạn chế
trƣờng hợp các giáo viên phải dạy vào tiết mà họ không mong
muốn. Tổng số vi phạm của ràng buộc này đƣợc tính nhƣ sau:


 











- Ràng buộc di chuyển địa điểm học của nhóm học phần - lớp học
trong cùng 1 ngày: Cần hạn chế việc các phân công thuộc cùng một
nhóm học phần-lớp học nhƣng lại đƣợc phân vào các nhóm phòng
học khác nhau trong cùng một ngày. Số vi phạm của ràng buộc này
đƣợc biểu diễn nhƣ sau:


         















- Ràng buộc độ nén lịch học của lớp học theo buổi: Mục tiêu của
ràng buộc này là cực tiểu hóa số lƣợng buổi mà mỗi lớp học cần
học, giá trị cần cực tiểu hóa đƣợc biểu diễn bằng công thức sau:






Trong đó, 




  






- Ràng buộc giờ lủng của lớp học theo buổi: Hạn chế trƣờng hợp một
lớp học phải học nhiều BlockElement trong cùng một buổi mà lại
phải nghỉ giữa các BlockElement này. Số vi phạm của ràng buộc
này (kí hiệu: 

là số bộ



  









2.2 Hàm mục tiêu
Mục tiêu của bài toán là tìm cách gán các BlockElement vào các phòng,
các tiết (xác định giá trị của các biến 

) sao cho lời giải  thu đƣợc thỏa
tất cả các ràng buộc cứng và cho giá trị cực tiểu của hàm mục tiêu  sau
đây:











Trong đó:



2.3 Nhóm các hướng tiếp cận metaheuristics dựa trên tìm kiếm cục bộ
Bắt nguồn từ một lời giải ban đầu (lời giải này gọi là lời giải khởi tạo, có
thể đƣợc tạo thành từ nhiều phƣơng pháp khác nhau, chẳng hạn nhƣ ngẫu
nhiên, Greedy, GRASP), các thuật giải metaheuristic dựa trên tìm kiếm cục
bộ sẽ thực hiện lặp đi lặp lại việc tìm kiếm trong miền không gian tìm kiếm
của bài toán nhằm mục đích tìm ra lời giải tối ƣu, tại mỗi bƣớc lặp của mình,
thuật giải sẽ tìm kiếm và chỉ lựa ra một lời giải duy nhất để làm cơ sở cho
bƣớc lặp tiếp theo, đây chính là điểm khác biệt cơ bản nhất giữa nhóm thuật
giải Local Search so với nhóm các thuật giải dựa trên quần thể, ở nhóm các
thuật giải dựa trên quần thể, sau mỗi bƣớc lặp, kết quả thu đƣợc là cả một tập
các lời giải, trong khi nhóm Local Search chỉ chọn một lời giải duy nhất. Tại
mỗi bƣớc lặp, thuật giải sẽ lấy lời giải duy nhất thu đƣợc từ bƣớc lặp trƣớc
làm li gii hin ti, thuật giải sẽ duyệt trong miền không gian láng ging của
lời giải hiện tại để chọn ra lời giải thay thế cho lời giải hiện tại ở bƣớc lặp kế
sau. Mỗi lời giải trong không gian láng giềng của lời giải hiện tại đƣợc gọi là
một láng ging của lời giải hiện tại. Sự tác động lên lời giải hiện tại để biến
nó thành một lời giải láng giềng của nó gọi là một c chuyn(move). Trong
các local search, hai vấn đề quan trọng nhất cần quan tâm là tính tăng cƣờng
(intensification) và tính đa dạng (diversification) của quá trình tìm kiếm, tính
tăng cƣờng là khả năng tập trung tìm kiếm sâu ở những vùng không gian mà 12
ta dự đoán là sẽ chứa lời giải tối ƣu, tính đa dạng là khả năng tìm đến những
vùng không gian lời giải mới nhằm thoát ra khỏi các vùng chứa điểm tối ƣu
cục bộ. Các local search khác nhau sẽ đƣa ra các chiến lƣợc khác nhau để
đảm bảo sự tồn tại và cân bằng giữa hai yếu tố này.
Các thuật giải thuộc nhóm này mà đã đƣợc áp dụng cho bài toán xếp thời
khóa biểu gồm có: thuật giải Tabu Search, thuật giải tôi luyện thép

Độ đo 11: AvT là trung bình tỉ lệ % giờ rảnh của giáo viên. Đƣợc tính bằng
công thức








Với: PpD = 12 là tổng số tiết học trong 1 ngày, D = 6 là số ngày trong 1 tuần.
Độ đo 12: AvC là trung bình tỉ lệ % giờ rảnh của lớp học. Đƣợc tính bằng
công thức








Với: PpD = 12 là tổng số tiết học trong 1 ngày, D = 6 là số ngày trong 1 tuần.
Độ đo 13: AvR là trung bình tỉ lệ % giờ rảnh của phòng học. Đƣợc tính bằng
công thức










.
Bƣớc 03: Gán lời giải tốt nhất 



.
Bƣớc 04: Khởi tạo nhiệt độ ban đầu T
0
.
Bƣớc 05: Khởi tạo giá trị ban đầu cho các biến:
Bƣớc 05.1: T = T
0
.
Bƣớc 05.2: Iter = 0.
Bƣớc 05.3: IterMax.
Bƣớc 05.4: Niter = 0.
Bƣớc 05.5: NiterMax.
Bƣớc 05.6: Stop = False.
Bƣớc 05.7: MinorIterMax.
Bƣớc 06: While(Stop = False)
Bƣớc 06.1: Iter = Iter + 1.
Bƣớc 06.2: Niter = Niter + 1.
Bƣớc 06.3: MinorIter = 0.
Bƣớc 06.4: While(MinorIter≤MinorIterMax)
Bƣớc 06.4.1: MinorIter = MinorIter + 1.
Bƣớc 06.4.2: Phát sinh 


Bƣớc 06.4.5: If













Bƣớc 06.4.5.1: Cập nhật 



.
Bƣớc 06.4.5.2: Cập nhật Niter = 0.
Bƣớc 06.4.6: Else
Bƣớc 06.4.6.1: Tạo ngẫu nhiên giá trị 



.
Bƣớc 06.4.6.2: If




IterMax
500
2
Niter
100
3
MinorIterMax
200

Bảng 3.2 Bảng kết quả thực nghiệm cho thuật giải SA 16

Hình 3.1 Kết quả tốt nhất thuật giải SA 0
100
200
300
400
500
600
Data
01
Data
02
Data
03

Phiên bản
Kết quả
Phiên bản
Kết quả
Data 01
SA01
401
SA01
401
Data 02
SA01
400
SA01
400
Data 03
SA01
475
SA01
475
Data 04
SA01
420
SA01
420
Data 05
SA01
445
SA01
445
Data 06

SA01
415
SA01
415
Data 13
SA01
495
SA01
495
Data 14
SA01
410
SA01
410 17
CHƯƠNG 4: CÁC PHƯƠNG PHÁP KẾT HỢP
Luận án đã thực nghiệm 15 phƣơng pháp kết hợp giữa các thuật giải sau:
GA+SA, GA+VNS, GA+TS, HS+SA, HS+VNS, HS+TS, Bees+SA,
Bees+VNS, Bees+TS, Bees+GA, Bees+HS, PSO+SA, PSO+VNS,
PSO+TS, Bees+PSO.
Trong đó phƣơng pháp kết hợp thuật giải Bees và thuật giải Variable
Neighborhood Search cho kết quả tốt nhất.

4.1 Mã giả thuật giải Bees và VNS
Thuật giải: Kết hợp thuật giải Bees và thuật giải VNS
Bƣớc 01: Khởi tạo quần thể ong ngẫu nhiên ban đầu có kích thƣớc n (mỗi
cá thể ong là một lời giải của bài toán).
Bƣớc 02: Đánh giá độ thích nghi của từng cá thể trong quần thể ban đầu.

giải tốt nhất.
Bƣớc 06.2.3: Tạo ra nsp lời giải lân cận cho mỗi lời giải trong (m-e)
vùng còn lại trong m vùng.
Bƣớc 06.2.4: Đánh giá độ thích nghi cho từng lời giải lân cận đƣợc
tạo ra.
c 06.3: Chọn ong có độ thích nghi cao nhất trong mỗi vùng để xây dựng
quần thể mới.
c 06.4: Phân công (n-m) ong còn lại tìm kiếm ngẫu nhiên và thay thế
các cá thể ong này bằng các cá thể có đƣợc do tìm kiếm ngẫu nhiên.
// Thuật giải đơn lời giải
c 06.5: Chọn lời giải ngẫu nhiên 

trong quần thể.
c 06.6: Cải tiến lời giải 

bằng thuật giải đơn lời giải (TS, SA,
VNS).
c 06.7: Đƣa lời giải cải tiến thay cho lời giải 

đang có trong quần
thể.
c 06.8: Tìm lời giải tốt nhất trong quần thể hiện tại 

.
c 06.9:Tính 






c 06.15: If(

=0)
Bƣớc 06.15.1: Stop = True.
Bƣớc 07: Xuất cá thể ong có độ thích nghi tốt nhất 

.

4.2 Kết quả chạy thực nghiệm thuật giải Bees và VNS
Bảng 4.1 Bảng tham số thực nghiệm cho thuật giải Bees-VNS
STT
Tham số
Miền giá trị
1
N
6, 8, 10, 20, 30, 40
2
M
3, 5, 6, 7, 10, 15
3
E
1, 2, 4, 5, 7
4
Nep
2, 3, 4, 5, 7, 8, 10, 30, 35
5
Nsp
1, 2, 3, 4, 5, 10, 15
6
ngh

1
15

0.01, 0.02
16
k
min

1, 2
17
k
step

1, 2

Bảng 4.2 Bảng kết quả thực nghiệm cho thuật giải Bees-VNS
Data
Kết quả
tốt nhất
Kết quả
trung bình tốt nhất
Phiên bản
Kết quả
Phiên bản
Kết quả
Data 01
BV03
332
BV12
374

Data 08
BV10
383
BV10
503
Data 09
BV07
306
BV07
378
Data 10
BV07
306
BV07
378
Data 11
BV08
313
BV09
373
Data 12
BV08
313
BV08
394
Data 13
BV08
313
BV08
394


0
200
400
600
Data
01
Data
02
Data
03
Data
04
Data
05
Data
06
Data
07
Data
08
Data
09
Data
10
Data
11
Data
12
Data


CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ LIÊN QUAN ĐẾN LUẬN ÁN
Hội nghị, Tạp chí tại Việt Nam
[CT1] Minh Khang Nguyen Tan Tran, Hue Nuong Tran (2011),
"Automated Systems for Educational Timetabling Problems",
Journal of Technical Education Science 17(2011), Vietnam, pp 1-
10.
Hội nghị, Tạp chí quốc tế
[CT2] Khang Nguyen Tan Tran Minh, Nguyen Dang Thi Thanh, Khon
Trieu Trang and Nuong Tran Thi Hue (2010), "Using Tabu
Search for Solving a High School Timetabling Problem", Studies
in Computational Intelligence, 283, pp 305-313.
[CT3] Khang Nguyen, Nguyen Dang, Khon Trieu, Nuong Tran (2010),
"Automating a Real-World University Timetabling Problem with
Tabu Search Algorithm", in Proceedings of 2010 IEEE
International Conference on Computing and Communication
Technologies, Research, Innovation, and Vision for the Future
(RIVF2010), Hanoi, pp 1-6.
[CT4] Khang Nguyen, Tung Pham, Nga Le, Nguyen Dang, and Nuong
Tran (2010), "Simulated Annealing-Based Algorithm for a Real-
World High School Timetabling Problem", in Proceedings of
2010 Second International Conference on Knowledge and
Systems Engineering (KSE2010), Hanoi, Vietnam, pp 125-130.
[CT5] Khang Nguyen, Quang Nguyen, Hien Nguyen, Phuc Nguyen,
Nuong Tran (2011), "Variable Neighborhood Search for a Real-
World Curriculum-based University Timetabling Problem", 2011
Third International Conference on Knowledge and Systems
Engineering (KSE2011), 10/2011, Hanoi, Vietnam, p 157-162.
[CT6] Khang Nguyen, Nam Nguyen, Vi Pham, Phuc Nguyen and
Nuong Tran (2011), "Applications of Particle Swarm