Khảo sát các thuật giải Tabu Search cho bài toán xếp thời khoá biểu đại học

KHẢO SÁT CÁC THUẬT GIẢI TABU SEARCH 
CHO BÀI TOÁN XẾP THỜI KHOÁ BIỂU ĐẠI HỌC 
NGUYỄN TẤN TRẦN MINH KHANG (*) 
 ĐẶNG THỊ THANH NGUYÊN (*) 
TRIỆU TRÁNG KHÔN (*) 
 TRẦN THỊ HUỆ NƯƠNG (**) 
TÓM TẮT 
 Bài toán xếp thời khoá biểu đại học là bài toán xuất phát từ nhu cầu rất cấp thiết của 
thực tế. Do thuộc lớp bài toán khó NP, bài toán hiện được quan tâm nghiên cứu và phát triển 
bởi rất nhiều nhà khoa học trên thế giới. Một trong những hướng tiếp cận hiệu quả nhất hiện 
nay là hướng tiếp cận sử dụng các metaheuristic. Trong đó, metaheuristic Tabu Search đã 
cho nhiều kết quả rất khả quan. Bài báo này sẽ khảo sát một số thuật giải Tabu Search tiêu 
biểu và cho hiệu quả cao đối với bài toán xếp thời khoá biểu đại học. 
ABSTRACT 
The prolem of university ranked schedule is the problem comes from the very urgent 
needs of the practice. Because of belonging to the hard NP that have attracted several 
researchers in the world. Metaheuristics are the most popular approaches nowadays for 
solving these problems. Tabu Search is one of metaheuristics that have given remarkable 
results. This paper investigates the most effective variant of Tabu Search for the university 
timetabling problem. 
1. GIỚI THIỆU BÀI TOÁN 
Bài toán xếp thời khoá biểu cho trường đại học thuộc lớp các bài toán xếp thời khoá 
biểu cho giáo dục. Đây là lớp các bài toán rất thực tế, xuất hiện ở tất cả các trường phổ thông 
và đại học. Mục tiêu của bài toán là tìm cách xếp lịch học, lịch dạy cho các sinh viên (học 
sinh) và giáo viên vào các tiết học, các phòng học sao cho thoả một số ràng buộc nhất định. 
Yêu cầu chính của lớp bài toán này là xếp các tài nguyên (giáo viên, học sinh, phòng học, 
thiết bị, v.v.) vào các tiết học thích hợp sao cho thời khoá biểu thu được phải thoả một số ràng 
buộc nhất định [1] (chẳng hạn: một giáo viên không dạy hai nhóm lớp khác nhau tại cùng một 
thời điểm, một sinh viên không học hai nhóm lớp khác nhau tại cùng một thời điểm, v.v.). 
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 khoá biểu. Dựa theo bài khảo sát của tác giả A. Schaerf 
[1] và bài báo cáo kĩ thuật của cuộc thi Xếp thời khoá biểu quốc tế 2007 (International 
Timetabling Competition 2007 – gọi tắt là ITC07) [2][3], có thể phân các bài toán xếp thời 
khoá biểu cho giáo dục thành ba nhóm chính: 
(*)
 Khoa Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên TP.HCM 
(**)
 Khoa Toán – Tin, Trường Đại học Khoa học Tự nhiên TP.HCM 
- Bài toán xếp thời khoá biểu cho trường phổ thông (high school timetabling): xếp lịch 
học hàng tuần cho các lớp và lịch dạy hàng tuần cho các giáo viên sao cho không có giáo viên 
nào phải dạy hai lớp tại cùng một thời điểm, và không có lớp nào học hai giáo viên tại cùng 
một thời điểm. 
- Bài toán xếp thời khoá biểu cho trường đại học (course timetabling), gồm có hai lớp 
bài toán con: 
+ Bài toán xếp thời khoá biểu cho trường đại học dựa trên nhóm học phần (curriculum 
- based course timetabling): sinh viên đăng kí học sau khi thời khoá biểu đã được sắp, sự 
tránh đụng độ giữa các môn học được quy định bởi nhóm học phần (nhóm các môn học 
không được sắp trùng giờ nhau), các nhóm học phần này được trường quy định sẵn và không 
phụ thuộc vào kết quả đăng kí học của sinh viên. 
+ Bài toán xếp thời khoá biểu cho trường đại học dựa trên lịch đăng kí của sinh viên 
(post enrolment – based course timetabling): sinh viên đăng kí môn mà mình muốn học, sau 
đó, trường sẽ dựa trên kết quả đăng kí này để xếp thời khoá biểu sao cho sinh viên đều có thể 
học được tất cả các môn mà mình đã đăng kí mà không bị đụng độ giờ học. 
 - Bài toán xếp lịch thi (examination timetabling): tương tự như bài toán xếp thời khoá 
biểu cho trường đại học, nhưng bài toán này có một số điểm khác biệt, chẳng hạn như: xếp 
lịch thi sao cho thời gian kéo dài của lịch thi là ít nhất (trong khi độ dài của một thời khoá 
biểu cho bài toán xếp thời khoá biểu cho trường đại học là cố định, thường là một tuần), hai 
môn thi có thể dùng chung một phòng học tại cùng một thời điểm, hoặc một môn thi có thể 
tách ra thi ở hai phòng khác nhau tại cùng một thời điểm (bài toán xếp thời khoá biểu cho 
trường đại học thường không cho phép điều này). 
 Bài toán xếp thời khoá biểu đại học nói riêng và bài toán xếp thời khoá biểu cho giáo 
dục nói chung đều thuộc lớp bài toán NP đầy đủ (là lớp bài toán mà cho đến nay, chưa tìm ra 
được phương pháp nào giải quyết được trong thời gian đa thức [1]). 
2. GIỚI THIỆU THUẬT GIẢI TABU SEARCH 
Tabu Search là một trong những metaheuristic được áp dụng nhiều nhất cho các bài 
toán tối ưu tổ hợp khó. Trong phần này, chúng tôi sẽ giới thiệu sơ lược về các thành phần cơ 
bản nhất của thuật giải Tabu Search và cách hoạt động của nó. Ngoài các thành phần cơ bản 
này, thuật giải Tabu Search được áp dụng trong thực tế có rất nhiều biến thể, với rất nhiều 
chiến lược hiệu quả khác được bổ sung vào nhằm nâng cao khả năng tìm kiếm của thuật giải, 
độc giả quan tâm có thể xem chi tiết tại tài liệu của tác giả Fred Glover [4], người được xem 
là cha đẻ của thuật giải này [5]. 
 Bài toán mà thuật giải Tabu Search giải quyết là bài toán tối ưu, mục tiêu của bài toán 
là tìm ra lời giải tốt nhất - lời giải mà tại đó, hàm mục tiêu của bài toán đạt giá trị cực tiểu. 
Hàm mục tiêu là hàm dùng để đo chi phí của một lời giải, lời giải có chi phí càng thấp thì 
càng tốt. 
 Ý tưởng chính của thuật giải Tabu Search như sau: 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ư: phương pháp thuật giải tham lam, phương pháp khởi tạo ngẫu nhiên, v.v.), 
thuật giải Tabu Search 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 
Tabu Search 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 thuật giải Tabu Search so với nhóm các 
thuật giải tiến hoá (như thuật giải di truyền, lập trình tiến hoá, v.v.). Ở nhóm các thuật giải 
tiến hoá, 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 ở Tabu 
Search, chỉ thu được một lời giải duy nhất. 
 Tại mỗi bước lặp, Tabu Search 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 tốt nhất, lời giải này sẽ 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 bước chuyển. 
 Để tránh việc duyệt trở lại những lời giải đã từng được duyệt, thuật giải Tabu Search 
sử dụng một danh sách để lưu trữ một số bước chuyển đã từng được sử dụng, gọi là danh sách 
Tabu. Danh sách này sẽ chứa những bước chuyển đã được thực hiện trong một số bước lặp 
gần đây, các bước chuyển nằm trong danh sách Tabu được gọi là các bước chuyển Tabu. Các 
bước chuyển này sẽ bị cấm sử dụng lại chừng nào nó còn nằm trong danh sách Tabu. Một 
bước chuyển Tabu sẽ tồn tại trong danh sách Tabu trong một khoảng thời gian n bước lặp, sau 
đó, bước chuyển này sẽ được loại ra khỏi danh sách Tabu và trở về trạng thái bình thường 
(không bị cấm nữa), số n này được gọi là giá trị Tabu tenure của bước chuyển, giá trị n này có 
thể cố định cho tất cả các bước chuyển hoặc là một số được chọn ngẫu nhiên cho từng bước 
chuyển. 
 Tuy nhiên, đôi khi một số bước chuyển dù bị cấm (bước chuyển Tabu) nhưng nó lại 
có khả năng cải tiến chất lượng của lời giải tốt nhất hiện nay, do đó, để tránh bỏ sót các bước 
chuyển tốt này, Tabu Search đưa ra một khái niệm nữa, đó là khái niệm tiêu chuẩn mong đợi 
(aspiration criteria). Cách áp dụng của tiêu chuẩn này như sau: nếu một bước chuyển Tabu bầt 
kì thoả được tiêu chuẩn mong đợi thì nó sẽ được loại ra khỏi danh sách Tabu ngay lập tức, 
cho dù giá trị Tabu tenure đi kèm có là bao nhiêu đi chăng nữa. Tiêu chuẩn mong đợi thường 
được dùng nhất là: nếu bước chuyển Tabu nào có thể làm cho lời giải hiện tại trở nên tốt hơn 
cả lời giải tốt nhất hiện nay thì bước chuyển Tabu đó sẽ được loại ra khỏi danh sách Tabu 
ngay lập tức. 
3. CÁC THUẬT GIẢI TABU SEARCH CHO BÀI TOÁN XẾP THỜI KHOÁ BIỂU 
ĐẠI HỌC 
Với yêu cầu phức tạp của bài toán xếp thời khoá biểu cho đại học, việc thực hiện xếp 
thời khoá biểu bằng tay đòi hỏi tốn rất nhiều công sức và thời gian mà kết quả tìm được đôi 
khi lại không phù hợp với thực tế. Do thuộc lớp bài toán NP đầy đủ nên việc giải quyết bài 
toán bằng phương pháp vét cạn là hầu như không thể. Chính vì độ phức tạp của bài toán và 
nhu cầu cao xuất phát từ thực tế nên bài toán xếp thời khoá biểu đã nhận được mối quan tâm 
đáng kể của các nhà khoa học. Bài toán này lần đầu tiên được Gotlieb khởi xướng vào năm 
1963 [6] và cho đến nay, đã có rất nhiều hướng tiếp cận được đưa ra [1]: 
 Các kĩ thuật đầu tiên mà con người sử dụng để xếp thời khoá biểu dựa trên mô phỏng 
suy nghĩ của con người để giải quyết vấn đề. Những kĩ thuật đó gọi là heuristic trực tiếp 
(direct heuristic). Một ví dụ của dạng này là kĩ thuật ưu tiên xếp những bài giảng khó xếp 
nhất trước. Thời khoá biểu sẽ dần dần được hình thành sau mỗi bước xếp. Ngoài ra, người ta 
còn đưa bài toán xếp thời khoá biểu về bài toán tô màu đồ thị (graph coloring) 
 Tiếp theo đó, những kĩ thuật khác cũng được áp dụng vào bài toán xếp thời khoá biểu 
như: lập trình ràng buộc (constraint programming), lập trình tuyến tính (linear 
programming), mạng phân luồng (network flow), v.v. 
 Gần đây, hướng tiếp cận metaheuristic trở thành hướng tiếp cận khá phổ biến và được 
quan tâm nghiên cứu khá rộng rãi trong suốt các thập niên vừa qua. Nhóm các thuật giải 
Metaheuristics bao gồm: các thuật giải tiến hoá (Evolutionary Algorithm), thuật giải tôi luyện 
thép (Simulated Annealing), Tabu Search, thuật giải Đại Hồng Thủy (Great Deluge), v.v. 
Metaheuristics tỏ ra khá hiệu quả trong việc tìm ra lời giải cho các bài toán tối ưu, giúp giải 
quyết khá tốt nhiều bài toán khó với kích thước miền tìm kiếm rất lớn như bài toán xếp thời 
khoá biểu, trong đó Tabu Search được đánh giá khá cao và được sử dụng rất nhiều bởi các tác 
giả nghiên cứu bài toán xếp thời khoá biểu trên thế giới và đã thu được nhiều kết quả khả 
quan, chẳng hạn như: 
 - Năm 2001: Marcone Jamilson Freitas Souza, Nelson Maculan, Luiz Satoru Ochi 
(xem tham khảo [15]) sử dụng kĩ thuật Tabu Search để giải quyết bài toán xếp thời khoá biểu 
cho trường trung học Escola Dom Silvério ở Mariana thuộc Brazil. Đầu tiên, nhóm các tác giả 
sử dụng thuật giải tham lam GRASP để tạo ra lời giải ban đầu (initial solution), sau đó Tabu 
Search được sử dụng để tìm lời giải tốt cho bài toán. 
 - Năm 2003: Jean-François Cordeau, Brigitte Jaumard, Rodrigo Morales (xem tham 
khảo [11]) tham gia cuộc thi International Timetabling Competition 2002-2003 (gọi tắt là 
ITC2002, chi tiết cuộc thi được mô tả ở phần 3.2). Nhóm các tác giả đã sử dụng Tabu Search 
kết hợp với một số thủ tục Exchange Moves, Pertubation và Ejection Chain để giải quyết 
bài toán của cuộc thi. Kết quả nhóm được xếp hạng 2. 
 - Năm 2003: Luca Di Gaspero và Andrea Schaerf (xem tham khảo [12]) tham gia cuộc 
thi International Timetabling Competition 2002-2003. Nhóm các tác giả chọn kĩ thuật Tabu 
Search làm trọng tâm, kết hợp với thuật giải leo đồi (Hill Climbing) và thủ tục Multi-Swap 
Shake để nâng cao chất lượng lời giải tìm được. Kết quả nhóm được xếp hạng 4. 
 - Năm 2003: Halvard Arntzen và Arne Lokketangen (xem tham khảo [8]) tham gia 
cuộc thi International Timetabling Competition 2002-2003. Lời giải ban đầu được khởi tạo 
bằng thuật giải tham lam, sau đó Tabu Search được thực hiện. Cuối cùng thủ tục Ejection 
Chain được kích hoạt để hướng việc tìm kiếm đến một vùng không gian tìm kiếm mới. Kết 
quả nhóm được xếp hạng 5. 
 - Năm 2003: Alexandre Dubourg, Benoît Laurent, Emmanuel Long, Benoît Salotti 
(xem tham khảo [13]) tham gia cuộc thi International Timetabling Competition 2002-2003. 
Nhóm tác giả sử dụng thuật giải tham lam để tạo ra lời giải ban đầu, sau đó sử dụng Tabu 
Search để cải tiến chất lượng lời giải. Kết quả nhóm được xếp hạng 6. 
 - Năm 2003: Gustavo Toro, Victor Parada (xem tham khảo[14]) tham gia cuộc thi 
International Timetabling Competition 2002-2003. Nhóm các tác giả tạo lời giải ban đầu 
bằng thuật giải tham lam, sau đó Tabu Search với bộ nhớ ngắn hạn (Short-term memory) và 
bộ nhớ dài hạn (Long-term memory) được thực hiện. Cuối cùng chiến lượng tăng cường hoá 
(intensifying - hướng việc tìm kiếm đến vùng không gian chứa lời giải tối ưu cục bộ) và 
chiến lược đa dạng hoá (diversifying - hướng việc tìm kiếm tránh rơi vào vùng không gian 
chứa lời giải tối ưu cục bộ) được thực hiện. Kết quả nhóm được xếp hạng 7. 
 - Năm 2007: Cagdas Hakan Aladag, Gulsum Hocaoglu (xem tham khảo [16]). Nhóm 
tác giả sử dụng Tabu Search để giải bài toán xếp thời khoá biểu của trường đại học Statistics 
Department of Hacettepe University (Thổ Nhĩ Kì) và thu được kết quả tốt: không vi phạm 
ràng buộc đụng độ nào. 
Tuy nhiên, hiệu quả của nhóm các thuật giải Metaheuristic còn phụ thuộc vào việc 
điều chỉnh các tham số của thuật giải, cách áp dụng thuật giải vào mô hình bài toán cụ thể. 
Thuật giải Tabu Search cũng không ngoại lệ, tính hiệu quả của thuật giải phụ thuộc vào yêu 
cầu cụ thể của bài toán, cách lựa chọn tập láng giềng, cách thiết kế phép chuyển, việc lựa 
chọn giá trị kích thước của Tabu list, v.v. Một thuật toán cụ thể có thể chạy tốt trên một số bài 
toán cụ thể và số bộ dữ liệu, nhưng lại không hiệu quả trên các bài toán biến thể khác. Hiện 
nay, nhìn chung vẫn chưa có một phương pháp nào có thể giải quyết trọn vẹn tất cả các biến 
thể của bài toán xếp thời khoá biểu cho giáo dục trên thế giới. Trong khuôn khổ bài báo này, 
chúng tôi tập trung khảo sát một số hướng tiếp cận nổi bật dựa trên thuật giải Tabu Search để 
giải quyết bài toán xếp thời khoá biểu cho trường đại học. 
3.1. Khởi tạo lời giải ban đầu 
Một trong những cách thông dụng nhất để khởi tạo lời giải ban đầu là phương pháp 
dựa trên thuật giải tham lam, cụ thể là trong bài báo của mình, tác giả D.Costa [7] đã sử dụng 
cách sau: các bài giảng có ít cách gán tiết, gán phòng nhất sẽ được chọn để gán trước, khi đó, 
các tiết học, phòng học không gây ra bất kì đụng độ nào sẽ được ưu tiên gán cho bài giảng 
này, nếu không tồn tại tiết học, phòng học nào thoả yêu cầu trên thì mục tiêu sẽ được giảm đi 
một bậc: các tiết học, phòng học không gây ra bất kì đụng độ nào liên quan đến giáo viên và 
lớp học sẽ được ưu tiên gán cho các bài giảng này, nếu vẫn không tồn tại tiết học, phòng học 
nào thoả yêu cầu trên, mục tiêu sẽ lại được giảm đi một bậc nữa (tổng cộng có 6 bậc, chi tiết 
của từng bậc xin xem ở bài báo của tác giả D.Costa). Sau đó đã có nhiều tác giả khác cũng áp 
dụng phương pháp tương tự cho bước khởi tạo lời giải của mình, chẳng hạn như nhóm tác giả 
H. Arntzen [8], C. H. Aladag [16], G. Toro [14] và A. Dubourg [13]. 
 Một phương pháp thông dụng khác nữa là phương pháp khởi tạo ngẫu nhiên: lời giải 
được khởi tạo một cách ngẫu nhiên bằng cách gán ngẫu nhiên các bài giảng cho các tiết học 
và các phòng học bất kì. Phương pháp này được sử dụng bởi các tác giả L. D. Gaspero và 
A.Schaerf [12], C. H. Aladag [16]. 
 Vào năm 2001, nhóm tác giả Souza và các đồng sự [15] đã ứng dụng một phương 
pháp mới để khởi tạo lời giải ban đầu, ý tưởng của phương pháp này là kết hợp giữa thuật giải 
tham lam và phương pháp ngẫu nhiên, người sử dụng có thể điều chỉnh sự tương quan giữa 
mức độ ngẫu nhiên và “mức độ tham lam” trong thuật giải để tạo nên một lời giải khởi tạo có 
chất lượng khá tốt. Phương pháp này có tên là GRASP (Greedy Randomized Adaptive Search 
Procedure). 
Một cách làm khác là khởi tạo lời giải bằng phương pháp mạng phân luồng[11]. Ý 
tưởng của phương pháp này là: ứng với mỗi tiết học, ta có hai tập điểm, tập thứ nhất biểu diễn 
các bài giảng có thể gán cho tiết học đang xét, tập thứ hai biểu diễn các phòng học rảnh vào 
tiết đang xét, mục tiêu là sử dụng các thuật giải cho mạng phân luồng để tạo nên một lời giải 
đầy đủ (tất cả các bài giảng đều phải được gán tiết, gán phòng). 
3.2. Chọn tập láng giềng 
Có nhiều cách khác nhau để chọn tập láng giềng trong quá trình xét duyệt, tùy thuộc 
vào tính chất và mục tiêu của bài toán, chẳng hạn như: tùy thuộc vào kích thước của miền 
láng giềng, vào chiến lược chọn phép chuyển của thuật giải. 
 Trong hướng tiếp cận của mình, tác giả D. Costa [7] xét toàn bộ các phần tử thoả tất 
cả ràng buộc cứng trong tập láng giềng và chọn phần tử tốt nhất. Tuy nhiên, cách chọn trên 
đôi khi không hiệu quả khi kích thước miền láng giềng quá lớn. Chẳng hạn như trong bài báo 
của O.R. Doria và các đồng sự ở trường đại học Napier, Scotland [10], tác giả thực hiện thử 
nghiệm Tabu Search trên các bộ dữ liệu thật của cuộc thi Xếp lịch Quốc tế ITC2007 với hai 
loại phép chuyển khác nhau (được đề cập ở phần sau). Nhóm tác giải chọn cả hai tập láng 
giềng thu được từ hai loại phép chuyển: phép chuyển đơn và phép hoán chuyển cùng một lúc, 
do đó, không gian láng giềng khá lớn. Khi đó, tại mỗi bước lặp, không phải tất cả các phần tử 
láng giềng đều được chọn, mà mỗi phần tử sẽ được chọn với xác suất cố định là 0.1, từ đó lấy 
ra phần tử tốt nhất trong số các phần tử được chọn để thực hiện cho bước lặp kế sau. 
 Thay vì duyệt miền láng giềng và chọn ngay phép chuyển tốt nhất. H. Arntzen [8] đề 
ra một cách làm khác như sau: nếu phép chuyển tốt nhất trong miền láng giềng có thể cải 
thiện được chất lượng lời giải tốt nhất hiện tại thì phép chuyển này sẽ được chọn, nếu không, 
phép chuyển này sẽ được chọn với xác suất 0.5, nếu sau phép thử xác suất mà phép chuyển 
này không được chọn thì sẽ chọn phép thử tốt thứ hai với xác suất 0.5, cứ thế cho đến khi 
chọn được một phép chuyển để thực hiện cho bước lặp kế sau. 
 G. Toro [14] lại đề ra một chiến lược khác: chỉ xét một phần của tập láng giềng do 
kích thước quá lớn của nó. Nếu lời giải khởi tạo không thoả tất các ràng buộc cứng, tại mỗi 
bước lặp, sẽ có một danh sách L gồm các bài giảng bị vi phạm ràng buộc cứng, xác suất phép 
chuyển được chọn liên quan đến các bài giảng thuộc danh sách L này là 80%, 20% còn lại là 
chọn ngẫu nhiên. Khi lời giải đang xét không còn vi phạm các ràng buộc cứng nữa, danh sách 
L sẽ bị hủy, thay vào đó, tại mỗi bước lặp, ta chọn ngẫu nhiên 10 bài giảng, sau đó xét các 
phép chuyển có liên quan đến các bài giảng này. 
3.3. Phép chuyển 
Hầu hết các tác giả áp dụng Tabu Search đều sử dụng các loại phép chuyển tương tự 
nhau. Trong đó có hai loại phép chuyển thông dụng nhất: 
- Phép chuyển đơn: chuyển một bài giảng đến một tiết học mới, một phòng học mới 
[7] [8] [9] [10] [11] [12] [13] [15]. 
- Phép hoán chuyển: hoán đổi tiết học, phòng học của hai bài giảng cho nhau [11] 
[12] [13] [16]. 
Trong đó, D. Costa [7] chỉ sử dụng các phép chuyển có tác động lên các bài giảng bị 
đụng độ. Bài giảng bị đụng độ là bài giảng vi phạm ít nhất một ràng buộc. Phép chuyển tác 
giả áp dụng là dạng phép chuyển đơn. 
3.4. Danh sách Tabu 
D.Costa [7] xét hai danh sách Tabu T1 và T2, khi một phép chuyển thực hiện di chuyển 
bài giảng A từ tiết học p1 sang tiết học p2 được chọn, phép chuyển này sẽ được đưa vào danh 
sách Tabu T1 và T2 như sau: T1 lưu bài giảng A, T2 lưu cặp bài giảng A và tiết học p1, có 
nghĩa là bài giảng A sẽ không được di chuyển cho đến khi phép chuyển này bị loại ra khỏi T1, 
và bài giảng A cũng sẽ không được gán trở lại cho tiết học p1 cho đến khi phép chuyển này bị 
loại khỏi T2. 
 Danh sách Tabu được sử dụng bởi O.R. Dorial [10] cấm bài giảng A di chuyển trở về 
lại tiết học cũ mà nó từng được gán cho đến khi bước chuyển được loại khỏi danh sách Tabu. 
Giá trị Tabu tenure được chọn cố định và được tính bằng tổng số bài giảng chia cho một hằng 
số k = 100. 
 H. Arntzen [8] xét danh sách Tabu sau đối với phép chuyển đơn: lưu lại ngày mà bài 
giảng đã từng được xếp vào, nghĩa là khi phép chuyển đơn chuyển bài giảng A từ tiết học p1 
sang tiết học p2, cặp (bài giảng A, ngày d) sẽ được lưu vào danh sách Tabu (ngày d là ngày 
mà tiết học p1 thuộc về). Khi đó, bài giảng A sẽ bị cấm gán trở lại vào bất kì tiết nào của ngày 
d cho đến khi cặp (A,d) bị loại ra khỏi danh sách Tabu. Danh sách Tabu này khác so với danh 
sách Tabu cho phép chuyển đơn thường dùng ở trên, thay vì cấm quay trở lại tiết cũ thì nó 
cấm quay trở lại luôn cả ngày cũ. Giá trị Tabu tenure TE trong [8] được tính như sau: 
- Đặt v0, vc, vb là giá trị hàm mục tiêu của lời giải khởi tạo, lời giải hiện tại và lời giải 
tốt nhất hiện tại. 
- Các giá trị trung gian Tp, Td được tính như sau: 
1
)(30
0 b
bc
p
vv
vv
T 
),2min( pbbd TTTT với Tb là một số nguyên được chọn trong đoạn [5,9]. 
- Giá trị Tabu tenure TE khi đó sẽ là: TE = Td + r, với r là một số nguyên trong đoạn 
[0,3]. 
Tác giả R. A.Valdes [9] lại tính giá trị Tabu tenure theo phương pháp sau: 
Gọi 
b
T là giá trị tabu tenure cơ bản, 
min
T , 
max
T là giá trị ngưỡng min, max mà của giá trị Tabu 
tenure động Td mà ta cần tính, ta có: 
b
T Toång soá cuïm cuûa taát caû caùc phaân coâng 
min
0.25
b
T T và 
max
2
b
T T . 
Khi đó, giá trị Tabu tenure cuối cùng Td là một số được chọn ngẫu nhiên trong đoạn [Tmin, 
Tmax] 
3.5. Tiêu chuẩn mong đợi 
Hầu hết tất cả các tác giả đều sử dụng tiêu chuẩn mong đợi sau: nếu một phép chuyển 
Tabu có thể tạo ra một lời giải tốt hơn lời giải tốt nhất hiện tại thì phép chuyển này sẽ được 
loại ra khỏi danh sách Tabu ngay lập tức. 
 Tuy nhiên, D.Costa [7] đưa ra một cách tiếp cận khác: tiêu chuẩn mong đợi sẽ gồm 
hai tiêu chuẩn khác nhau, tiêu chuẩn thứ nhất chỉ đánh giá dựa trên ba ràng buộc đầu tiên (3 
ràng buộc có trọng số cao nhất), tiêu chuẩn thứ hai đánh giá dựa trên tất cả các ràng buộc. 
Tiêu chuẩn thứ nhất có độ ưu tiên cao hơn, nếu tiêu chuẩn này không thoả thì mới sử dụng 
đến tiêu chuẩn thứ hai. 
3.6. Các chiến lược bổ sung 
Ngoài các thành phần tìm kiếm cơ bản, các tác giả còn đưa ra thêm các chiến lược bổ 
sung khác nhằm nâng cao chất lượng tìm kiếm. Chẳng hạn như chiến lược đa dạng hoá (để 
giúp việc tìm kiếm tìm đến được những miền không gian tìm kiếm mới) và tăng cường hoá 
(tập trung tìm kiếm sâu hơn ở những vùng không gian tìm kiếm có triển vọng chứa lời giải tối 
ưu). 
 Tác giả D.Costa [7] đưa chiến lược đa dạng hoá bằng cách thay đổi trọng số của ba 
ràng buộc đầu tiên (ba ràng buộc có trọng số cao nhất) trong suốt quá trình tìm kiếm, từ đó 
giúp việc tìm kiếm không bị tập trung vào một miền không gian cố định. Quy tắc thay đổi 
trọng số như sau: cứ sau k bước lặp liên tiếp mà các lời giải thu được không được cải thiện 
mặc dù ba ràng buộc đầu tiên không hề bị vi phạm thì trọng số của các ràng buộc này sẽ được 
giảm đi. 
 Tác giả H. Arntzen [8] lại áp dụng một chiến lược đa dạng hoá khác: Ghi lại thông tin 
về tần số di chuyển của mỗi bài giảng. Tần số này là một tần số có trọng số, nghĩa là các bài 
giảng được di chuyển trong thời gian càng gần với hiện tại thì giá trị tần số đi kèm với nó 
càng tăng cao. Cụ thể như sau: tại bước khởi tạo, đặt p = 0.01, cứ sau mỗi bước lặp, p được 
cập nhật: p = 101%p. Khi đó, gọi F là giá trị tần số đi kèm với bài giảng l, mỗi khi bài giảng l 
được di chuyển, F được cập nhật như sau: F = F + p. Tần số này giúp làm tăng độ đa dạng hoá 
của quá trình tìm kiếm bằng cách: bài giảng có tần số di chuyển thấp hơn thì sẽ được ưu tiên 
chọn hơn. Ngoài ra, tác giả còn sử dụng một loại phép chuyển mới gọi là phép chuyển theo 
chuỗi (ejection chain): các bài giảng được đẩy dần ra cho đến khi thu được một lời giải tốt 
hơn lời giải hiện tại. Ví dụ như: chọn một bài giảng A để bắt đầu, ta sẽ đẩy bài giảng A vào 
tiết học của bài giảng B, rồi đẩy bài giảng B vào tiết học của bài giảng C, việc đẩy này sẽ 
dừng sau một bước lặp cố định, nếu lời giải mới thu được tốt hơn lời giải hiện tại thì chọn lời 
giải mới, nếu không, quay trở lại từ đầu và thực hiện lại quy trình đẩy như trên (với các bài 
giảng khác). Cách làm này trong một số trường hợp có thể tạo ra những lời giải rất tốt mà các 
bước chuyển thông thường của Tabu Search không thể tạo ra được. 
 J. F. Cordeau [11] và các đồng sự cũng áp dụng chiến lược đa dạng hoá tương tự như 
của tác giả D.Costa [7] : trọng số của các ràng buộc cứng thay đổi trong suốt quá trình tìm 
kiếm và được điều khiển bởi 1 tham số : 
- Nếu lời giải đang xét thoả tất cả các ràng buộc cứng: gán )/,1min(  với  được 
chọn ngẫu nhiên trong khoảng [1.05, 1.19]. 
- Nếu lời giải đang xét không thoả tất cả các ràng buộc cứng: gán )*,1000max(  
với  được chọn ngẫu nhiên trong khoảng [1.05, 1.19] 
 Bên cạnh đó, tác giả [11] còn thực hiện phép hoán chuyển (đã đề cập ở phần phép 
chuyển) nhiều lần để làm ‘‘xáo trộn’’ lời giải hiện tại, từ đó làm tăng tính đa dạng cho quá 
trình tìm kiếm. 
 Về chiến lược tăng cường hoá, nhóm tác giả C.H. Aladag [16] áp dụng cách làm sau: 
nếu như sau một số bước lặp nhất định mà chất lượng lời giải tốt nhất vẫn không được cải 
thiện, quá trình tìm kiếm sẽ được khởi động lại, với lời giải khởi tạo chính là lời giải tốt nhất 
hiện tại. Mục đích của cách làm này là tập trung mạnh hơn vào vùng không gian của lời giải 
tốt nhất hiện tại với hi vọng tìm ra những lời giải tốt mà bị bỏ sót trong quá trình tìm kiếm 
trước đây. 
Ngoài ra, nhóm tác giả L. D. Gaspero và A. Schaerf [12] còn áp dụng thêm thuật giải 
leo đồi xen kẽ với phần tìm kiếm cơ bản của thuật giải Tabu Search, cũng với mục đích tăng 
cường hoá chất lượng tìm kiếm. 
4. KẾT LUẬN 
Trong bài báo này, chúng tôi đã khảo sát một số biến thể của thuật giải Tabu Search 
cho bài toán xếp thời khoá biểu cho trường đại học, một trong những bài toán tối ưu tổ hợp rất 
khó và cũng rất thực tế hiện nay. Hướng tiếp cận Tabu Search đã giúp giải quyết được khá 
hiệu quả rất nhiều bài toán xếp thời khoá biểu đại học cụ thể. Việc khảo sát thuật giải này 
chính là tiền đề cho việc nghiên cứu và phát triển thuật giải Tabu Search để giải quyết bài 
toán xếp thời khoá biểu cho các trường đại học ở Việt Nam, với những yêu cầu rất đặc trưng 
của nền giáo dục nước ta. Sau một thời gian tìm hiểu và thử nghiệm, nhóm tác giả đã phát 
triển hai hệ thống xếp thời khoá biểu cho trường đại học và trường trung học với hướng tiếp 
cận dựa trên Tabu Search. Hai hệ thống này được thể hiện dưới cả hai dạng: online (các trang 
web) và offline (các phần mềm chạy trên máy tính), nhằm tăng tính mở và tính tiện dụng cho 
người dùng. Để biết chi tiết của các hệ thống này, độc giả có thể xem tại trang web của nhóm 
tác giả: 
TÀI LIỆU THAM KHẢO 
1. Andrea Schaerf (1999). “A Survey of Automated Timetabling”. Kluwer Academic 
Publishers. 
2. Luca Di Gaspero, Barry McCollum, Andrea Schaerf (2007), "The Second 
International Timetabling Competition (ITC-2007): Curriculum-based Course 
Timetabling (Track 3)", International Timetabling Competition 2007-2008. 
3. Rhidian Lewis, Ben Paechter, Barry McCollum (2007), "Post Enrolment based 
Course Timetabling: A Description of the Problem Model used for Track Two of the 
Second International Timetabling Competition", International Timetabling 
Competition 2007-2008. 
4. Fred Glover, Manuel Laguna (1998), “Tabu Search”, Kluwer Academic Publishers, 
Boston, London. 
5. Fred Glover (1989), “Tabu Search - part I”, ORSA Journal on Computing, Vol.1, No. 
3. 
6. C. C. Gotlieb (1963). “The construction of class-teacher timetables”. In C. M. 
Popplewell, IFIP congress, 62:73--77. North-Holland. 
7. D. Costa (1994). “A tabu search algorithm for computing an operational timetable”. 
European Journal of Operational Research, 79:98-110. 
8. Halvard Arntzen , Arne Lokketangen (2003). “A tabu search heuristic for a university 
timetabling problem”, MIC2003, Japan. 
9. Ramon Alvarez-Valdes, Enric Crespo, Jose M. Tamarit (2002). "Design and 
implementation of a course scheduling system using Tabu Search", European Journal 
of Operational Research 137, pp 517-518. 
 10. www.fit.hcmus.edu.vn/~nmkhang/uts 
 www.fit.hcmus.edu.vn/~nmkhang/hts