LỜI CẢM ƠN
Sau một thời gian học tập và nghiên cứu, em đã hoàn thành đồ án tốt
nghiệp với đề tài: “Nghiên cứu giải thuật, áp dụng cho bài toán lập lịch tín
chỉ cho Trường Đại học Công nghệ thông tin và truyền thông Thái
Nguyên”. Trước tiên em xin bày tỏ lòng kính trọng và biết ơn chân thành
đến thầy giáo ThS. Trần Hải Thanh là người trực tiếp hướng dẫn đã tận tình
chỉ bảo cũng như tạo điều kiện giúp đỡ em để hoàn thành đồ án tốt nghiệp.
Qua thời gian được thầy hướng dẫn, em đã học hỏi được nhiều kiến thức bổ
ích và kinh nghiệm quý báu làm nền tảng cho quá trình học tập, làm việc và
nghiên cứu sau này.
Em cũng xin chân thành cảm ơn các thầy cô giáo giảng dạy tại bộ
môn Khoa học máy tính và các thầy cô giáo giảng dạy tại Khoa công nghệ
thông tin – Trường ĐH Công nghệ thông tin và truyền thông – ĐH Thái
Nguyên trong suốt thời gian 5 năm học tập tại trường đã trang bị cho em
những kiến thức cơ bản cần thiết và bổ ích giúp em hoàn thành đồ án tốt
nghiệp. Với vốn kiến thức được tiếp thu trong quá trình học không chỉ là
nền tảng cho quá trình nghiên cứu thực tâp mà còn là hành trang quí báu để
em phát triển các công việc thực tiễn trong tương lai.
Cuối cùng em kính chúc quý Thầy, Cô dồi dào sức khỏe và thành
công trong sự nghiệp cao quý. Đồ án tuy hoàn thành nhưng không tránh
khỏi nhiều thiếu sót và những vấn đề chưa xử lý được. Em rất mong nhận
được sự thông cảm và chỉ bảo tận tình của quý Thầy cô và các bạn.
Thái nguyên, ngày... tháng 06 năm 2016
Sinh viên

Nguyễn Thị Minh
1


2


1.3. Bài toán lập lịch thi (Examination timetabling)............................... 10
1.4. Các cách tiếp cận hiện nay ............................................................... 11
CHƯƠNG 2: TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP TÌM KIẾM...... 13
2.1. Xung đột tối thiểu (Min-conflict)..................................................... 13
2.2. Thuật giải mô phỏng luyện kim (Simulated Annealing) ................. 13
2.3. Thuật giải leo đồi (Hill-climbing) .................................................... 14
2.4. Tìm kiếm Tabu (Tabu search) .......................................................... 14
2.5. Thuật giải di truyền (genetic algorithm) .......................................... 15
2.6. Kết luận............................................................................................. 15
CHƯƠNG 3. CƠ SỞ TÌM KIẾM TABU................................................... 17
3.1. Lược sử về tabu search (TS)............................................................. 17
3.1.1. Giới thiệu.................................................................................... 17
3.1.2. Tabu search – một dạng meta-heuristic ..................................... 18
3.1.3. Các giai đoạn phát triển của tabu search.................................... 19
3.2. Nguyên lý chung của tabu search..................................................... 20
3.3. Cách sử dụng bộ nhớ ........................................................................ 21
3.3.1. Một minh họa ............................................................................. 22
3.4. Chiến lược tăng cường (intensification) và chiến lược đa dạng
(diversification) ....................................................................................... 24
3.5. Lập trình với bộ nhớ tương thích (adaptive memory programming)25
3.6. Các nhân tố của bộ nhớ tương thích................................................. 25
CHƯƠNG 4: XÂY DỰNG MÔ HÌNH BÀI TOÁN .................................. 28
4.1. Bài toán lập lịch cho các trường đại học, cao đẳng ......................... 28
4


4.1.1. Các khái niệm............................................................................. 28
4.1.2. Mô hình của bài toán.................................................................. 30
4.1.3. Các ràng buộc cứng.................................................................... 31
4.1.4. Các ràng buộc mềm.................................................................... 31

Hình 8 - Cấu trúc của một chương trình C#............................................... 46
Hình 9 - Quá trình tự động quản lý bộ nhớ. .............................................. 46
Hình 10 - Quá trình biên dịch trong .Net ................................................... 47
Hình 11 – Các thành phần của VisualStudio 12. ....................................... 50
Hình 12 – Cấu trúc dữ liệu đầu vào............................................................ 51
Hình 13 – Giao diện khi nạp dữ liệu. ......................................................... 51
Hình 14 – Giao diện khi hoàn thành lập lịch. ............................................ 52
Hình 15 – Biểu đồ đánh giá tối ưu quá trình tìm kiếm. ............................. 53
Hình 15 – Biểu đồ đánh giá ràng buộc cứng xung đột phòng. .................. 54
Hình 16 – Biểu đồ đánh giá ràng buộc mềm lớp học cả tuần. ................... 54
Hình 17 – Lịch giảng dạy của giảng viên Nguyễn Hiền Trinh trong tuần 55
Hình 18 – Lịch học của lớp KHMTK13A trong tuần. ............................... 55
Hình 19 – Lịch học tại phòng C2.401 ........................................................ 56

6


MỞ ĐẦU
1. Lý do chọn đề tài:
Bài toán lập lịch luôn là một bài toán cổ điển thuộc lớp bài toán NPkhó. Từ lâu đã thu hút được sự quan tâm, nghiên cứu và phát triển của nhiều
tổ chức giáo dục, các nhà khoa học bởi tính ứng dụng cao và độ phức tạp
của nó. Các bài toán lập lịch thường rất phong phú, đa dạng bởi các ràng
buộc và yêu cẩu của từng doanh nghiệp, tổ chức, trường học.
Trong nhiều thập niên qua đã có rất nhiều các phương pháp giải
được đưa ra. Tuy nhiên, tính hiệu quả của lời giải cho lớp bài toán vẫn
còn nhiều bàn cãi. Bài toán lập lịch có thể được dịnh nghĩa là một bài
toán tìm kiếm chuỗi tối ưu để thực hiện một tập các hoạt động chịu tác
động của một tập các ràng buộc cần phải được thỏa mãn. Người lập lịch
thường cố gắng thử đến mức tối đa sự sử dụng các tài nguyên nhân lực,
vật lực, máy móc và tối thiểu thời gian đòi hỏi để hoàn thành toàn bộ quá

viên hướng dẫn cung cấp, sách, báo, tạp chí, internet…) tổng hợp, phân tích
và trình bày lại theo sự hiểu biết của bản thân
Mở rộng các cách tiếp cận trước đây trên cơ sở phân tích đặc thù bài
toán cần giải quyết để đưa ra những ý kiến, đề xuất cải tiến hợp lý.
Ứng dụng những kết quả dựa trên nghiên cứu trên vào thực tế.
Giả thuyết khoa học (hoặc những đóng góp mới của đề tài)

8


CHƯƠNG 1:
TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH TRONG CÁC CƠ SỞ GIÁO
DỤC VÀ CÁC CÁCH TIẾP CẬN
Bài toán lập lịch luôn là một bài toán khó, mang tính khoa học đồng
thời tính thực tiễn cũng rất cao. Không chỉ Việt Nam mà trên toàn cầu từ lâu
việc lập lịch đã trở thành một vấn đề có tính thời sự, một bài toán gây được
sự chú ý, quan tâm của nhiều người.
Bài toán lập thời khóa biểu là một nhánh của bài toán lập lịch
trong đó đưa ra một chuỗi các sự kiện (thông thường là các môn học, bài
giảng hoặc các môn thi) và bao gồm các giáo viên và học viên trong một
khoảng thời gian định trước và thỏa mãn một tập hợp các ràng buộc của
từng loại thời khóa biểu khác nhau.
Mỗi bài toán có các tính chất riêng, khi sắp lịch thi bài toán đặt ra là
phải đáp ứng được yêu cầu về thời gian (như không được trùng hay quá sát
nhau) giữa các lần thi liên tiếp của cùng một học sinh, sinh viên. Còn khi
sắp lịch cho trường phổ thông sẽ cần quan tâm giờ rảnh mà giáo viên đăng
ký và các tiết trống giữa giờ học của học sinh đóng vai trò rất quan trọng
cho việc đánh giá kết quả của thời khóa biểu. Đối với đại học, bài toán cần
giải quyết cũng là việc tránh xung đột giữa các thành phần tham gia trong
thời khóa biểu (giáo viên, lớp học, phòng học và thiết bị). Vì thế, mục tiêu



timetabling)
Bài toán lập thời khóa biểu cho trường đại học là bài toán lập lịch
cho các bài giảng (lectures) vào từng khóa học với một số lượng phòng
học và tiết học cho trước. Điểm khác biệt chính với bài toán lập thời
khóa biểu trường phổ thông là đặc trưng của các khóa học ở trường đại
học, các sinh viên tham dự khóa học, trong khi các lớp học ở trường phổ
thông được tạo bởi tập hợp các học sinh và có thể coi như là một thực thể
đơn. Ở các trường đại học, hai khóa học khác nhau có thể có trùng sinh
viên tham dự và điều đó có thể tạo ra xung đột và sẽ không thể lập lịch
được trong cùng một tiết học. Thêm vào đó, các giáo viên ở trường phổ
thông luôn dạy nhiều hơn một lớp trong khi ở trường đại học một giảng
viên thường chỉ dạy một vài khóa học hay một vài môn học trong một kỳ.
Cuối cùng, với bài toán trường đại học kích cỡ các phòng học chiếm một
vai trò quan trọng trong khi với bài toán trường phổ thông vấn đề này là
không quan trọng bởi vì trong hầu hết các trường phổ thông mỗi lớp có
một phòng học riêng.
1.3. Bài toán lập lịch thi (Examination timetabling)
Bài toán lập lịch thi tương tự như bài toán lập thời khóa biểu cho
trường đại học nhưng ta cần phân biệt sự khác nhau giữa hai bài toán này.
Bài toán lập lịch thi có những đặc điểm khác sau đây:
 Chỉ có một kỳ thi cho mỗi một môn thi.
 Các điều kiện xung đột nói chung là hạn chế. Thực tế, có thể chấp
nhận một sinh viên có thể bỏ qua một bài giảng do sự chồng chéo các môn
học; nhưng không có sinh viên nào được phép bỏ qua một kỳ thi hết môn đã
11


học vì nếu sinh viên không qua được kỳ thi này coi như trượt môn đó.

Thông thường, người giáo vụ cần phải mất vài ngày để sắp được
một thời khóa biểu bằng tay. Mà lời giải còn có thể chứa những kết quả
không tốt lắm, ví dụ như việc giáo viên bị trống tiết giữa trong một
buổi giảng. Ngoài ra trong quá trình sắp người giáo vụ phải tương tác
rất nhiều với giảng viên để thỏa thuận giờ giảng khi xảy ra việc tranh
chấp tài nguyên.
Bởi lý do ở trên, nhu cầu đặt ra là cần một chương trình sắp thời
khóa biểu tự động. Trong hơn bốn mươi năm qua, bắt đầu từ thập niên 60,
với Gotlieb (1963)và những người khác, nhiều bài báo có liên quan đến việc
sắp thời khóa biểu tự động đã xuất hiện ở các hội nghị và tạp chí khoa học,
và các ứng dụng đã bắt đầu được phát triển cho ra các kết quả khá tốt.
Các kỹ thuật sơ khai của Schmidt-Strohlein, 1979; Junginger, 1986
được dựa trên việc giả lập quá trình sắp lịch của con người trong việc giải
bài toán. Các kỹ thuật này được gọi là heuristics trực tiếp (direct heuristic)
được dựa trên việc mở rộng liên tục (successive augmentation). Nghĩa là, họ
sẽ sắp một phần thời khóa biểu, lần lượt từng phân công, cho đến khi tất cả
các phân công đã được sắp hoặc không sắp được thêm phân công nào nữa
do vi phạm các ràng buộc.
Sau này, các nhà nghiên cứu đã bắt đầu áp dụng các kỹ thuật
tổng quát hơn trên bài toán này. Do đó ta thấy các thuật toán dựa trên
13


lập trình tuyến tính (integer programming) của Tripathy trong các năm
1984, 1992, luồng mạng (network flow) của Ostermann-de Werra, 1983,
và còn những loại khác nữa. Ngoài ra bài toán này cũng được giải quyết
bằng cách đưa nó về bài toán nổi tiếng: tô màu đồ thị (graph coloring)
của Neufeld-Tartar, 1974.
Gần đây nhất, những tiếp cận dựa trên những hướng nghiên cứu mới
bao gồm tôi luyện thép (simulated annealing) (Abramson, 1991), Tabu

này với xác xuất p, và áp dụng theo Thuật giải MC với xác xuất 1- p. Giá trị
của thông số p có ảnh hưởng lên hiệu quả của Thuật giải. Thuật giải này
được gọi là MCRW (Min-conflict Random Walk)
15


2.2. Thuật giải mô phỏng luyện kim (Simulated Annealing)
Mô phỏng luyện kim (Simulated Annealing) [6] viết tắt SA, là
một kỹ thuật tìm kiếm ngẫu nhiên (stochastic search) tỏ ra rất hữu hiệu
cho những bài toán tối ưu hóa qui mô lớn. Trong kỹ thuật này, nhiệt độ là
biến được khởi tạo ở một giá trị cao và dần dần giảm dần xuống trong
quá trình tìm kiếm. Trong quá trình tìm kiếm SA thay lời giải hiện thời
bằng cách chọn ngẫu nhiên lời giải láng giềng với một xác suất phụ
thuộc vào sự chênh lệch giữa giá trị hàm mục tiêu và tham số điều khiển
là biến nhiêt độ toàn cục. Tại những giá trị nhiệt độ cao, các bước chuyển
được chấp nhận một cách ngẫu nhiên bất luận chúng là bước chuyển có
cải thiện hàm chi phí của lời giải hay không. Khi nhiệt độ được giảm
xuống, xác xuất xuất hiện lời giải có cải thiện sẽ tăng lên và xác xuất
xuất hiện lời giải không cải thiện sẽ giảm xuống. Có một số cách thức
giảm nhiệt độ dần xuống được dùng trong một Thuật giải SA, được gọi
là lịch biểu làm nguội (cooling schedule).
2.3. Thuật giải leo đồi (Hill-climbing)
Thuật giải leo đồi (Hill-climbing) [7] chính là nền tảng cơ sở của các
kỹ thuật tìm kiếm cục bộ. Mặc dù đây là Thuật giải đơn giản nhưng lại nó
lại rất mạnh và hiệu quả trong việc giải quyết các bài toán phải thỏa mãn các
ràng buộc lớn (CSP – Constraint Satisfaction Problem). Thuật ngữ “leo đồi”
(hill-climbing) xuất phát từ cơ chế “tu chỉnh lập”: ở mỗi bước của việc tìm
kiếm, chúng ta sẽ chọn một bước chuyển mà nó cải thiện giá trị hàm mục
tiêu để thực hiện. Trong thuật giải leo đồi, chỉ những bước chuyển cải thiện
được hàm chi phí hoặc không làm cho hàm chi phí thay đổi mới được chọn

con cái tùy thuộc vào độ thích nghi (fitness) của chúng. Độ thích nghi được
đo bằng một - 6 - hàm mục tiêu. Thuật giải GA đã được áp dụng vào việc
giải hệ ràng buộc.
Việc dùng Thuật giải GA vào các bài toán tối ưu hóa có ràng buộc
làm phát sinh nhiều vấn đề mà các nhà nghiên cứu phải quan tâm giải quyết.
Một trong những vấn đề quan trọng là làm thế nào để đưa các ràng buộc vào
các hàm thích nghi (fitness function) để điều khiển quá trình tìm kiếm một
cách đóng đắn.
2.6. Kết luận
Sự thành công của bất kỳ giải thuật tìm kiếm cục bộ nào nêu trên
cũng tùy thuộc vào các đặc điểm thi công, tức là tùy thuộc vào các tham số
kỹ thuật đặc thù mà người sử dụng phải xác định khi áp dụng giải thuật tìm
kiếm cục bộ đó vào bài toán cụ thể. Quá trình thực nghiệm để xác định các
thông số kỹ thuật của một giải thuật tìm kiếm cục bộ nào đó khi áp dụng
vào một bài toán cụ thể được gọi là quá trình điều chỉnh thông số (parameter
tuning).
Trong những năm gần đây việc kết hợp các loại giải thuật tìm kiếm
cục bộ và một số giải thuật khác là một trong số các cách tiếp cận mới nhất.
Trong chương 3 sẽ trình bày chi tiết giải thuật tìm kiếm Tabu cho bài toán
lập lịch.

18


CHƯƠNG 3. CƠ SỞ TÌM KIẾM TABU
3.1. Lược sử về tabu search (TS)
3.1.1. Giới thiệu
Sự phức tạp trong các vấn đề tối ưu được gặp trong thực tế như các
vấn đề trong ngành viễn thông, hậu cần, kế hoạch tài chính, vận chuyển và
việc sản xuất đã thúc đẩy mạnh việc phát triển các kỹ thuật tối ưu mạnh mẽ.

(operation research – OR). Thiết kế hiệu quả của các phương pháp này có
thể góp phần để phát triển những phiên bản nguyên lý mới và sâu sắc hơn
trong các lĩnh vực của AI và OR có liên quan về các kỹ thuật cải thiện việc
giải quyết vấn đề.
Ngày nay nhiều nhà nghiên cứu trong lĩnh vực AI và OR đã quên
rằng hai ngành này đã phát triển cùng nhau và chia sẻ nhiều kiến thức cho
nhau. Cả hai ngành đều bắt đầu từ những kết quả của việc phát triển các
phương thức giải quyết vấn đề. Những bài báo đầu tiên về heuristic chấp
nhận các tiếp cận có ý thức về cầu nối giữa AI và OR. Tuy nhiên không lâu
sau hai lĩnh vực này bắt đầu chia rẽ, với OR thì tập trung về các kết quả,
trong khi AI thì chú trọng về tượng trưng và các phân tích định lượng.
Trong thời gian việc phân chia giữa hai ngành vẫn chưa rõ ràng,
20


vẫn có vài cố gắng để giới thiệu những tiếp cận không truyền thống
trong lĩnh vực tối ưu. Cùng lúc đó cũng có những cố gắng để giới thiệu
xác suất và các khái niệm thiết kế tích hợp vào trong các quy trình
heuristic. Không may, những phát triển này lại bị nhận chìm trong
nhiều năm. Nhưng chúng cung cấp nền tảng cho các ý tưởng nổi lên lại
vào giữa cuối thập niên 80 và trở thành nguồn gốc của các chiến lược
mà bây giờ là trái tim của tabu search.
3.1.3. Các giai đoạn phát triển của tabu search
Bốn giai đoạn phát triển chính của tabu search gồm: (1) các chiến
lược kết hợp các luật quyết định dựa trên tái cấu trúc logic và tìm kiếm với
các chiều sâu biến đổi (non-monotonic search), (2) Khả năng khôi phục và
xung đột hệ thống, (3) bộ nhớ linh hoạt dựa trên tính vừa xảy ra và tính
thường xuyên và (4) các quy trình được chọn để kết hợp các lời giải, áp
dụng cho quần thể được duy trì có hệ thống.
Giai đoạn phát triển đầu tiên đến từ việc nghiên cứu các luật quyết

dưới các hình thức khác nhau, cả bằng việc loại trừ trực tiếp các lựa chọn
“bị cấm”, cũng như bằng cách chuyển thành các đánh giá và khả năng lựa
chọn. Các giới hạn được lợi dụng hoặc được tạo bởi việc tham khảo các cấu
trúc bộ nhớ được thiết kế nhằm mục đích cụ thể.
Tabu search dựa trên giả thuyết vấn đề đã được giải, kết hợp chặt

22


chẽ “bộ nhớ thích nghi” (adaptive memory) và “thăm dò phản ứng”
(responsive exploration). Giống như việc leo núi, người leo núi phải nhớ có
chọn lọc các thành phần của quãng đường đã qua (sử dụng adaptive
memory) và lập ra các lựa chọn chiến lược trên đường (sử dụng responsive
exploration). Bộ nhớ thích nghi này cho phép việc tìm kiếm trong không
gian lời giải một cách tiết kiệm và hiệu quả.
Việc nhấn mạnh vào đặc điểm “thăm dò phản ứng” (responsive
exploration) của tabu search được lý giải rằng, dù một lựa chọn chiến lược
kém thì vẫn cung cấp nhiều thông tin hơn một lựa chọn ngẫu nhiên tốt.
(Trong hệ thống sử dụng bộ nhớ, một lựa chọn kém nhưng dựa trên chiến
lược có thể cung cấp nhiều thông tin hơn về cách mà chiến lược đã thay đổi
thuận lợi như thế nào.)
Thăm dò phản ứng tích hợp các nguyên lý cơ bản của tìm kiếm
thông minh (nghĩa là khai thác những đặc điểm lời giải tốt trong khi vẫn tìm
kiếm những vùng có tiềm năng khác). Tabu search được phối hợp với việc
tìm kiếm những con đường mới và hiệu quả hơn trong việc kết hợp những
điểm mạnh của những kỹ thuật có liên quan đến cả “bộ nhớ thích nghi”
(adaptive memory) và “thăm dò phản ứng” (responsive exploration).
3.3. Cách sử dụng bộ nhớ
Các kiến trúc bộ nhớ trong tabu search hoạt động bằng việc tham
khảo bốn chiều chính sau: tính chất “mới xảy ra” (recency), tính chất

3.3.1. Một minh họa
Đây là một minh họa cho thấy các thuộc tính có thể được sử dụng
như thế nào trong cấu trúc bộ nhớ recency-based. Xem một vấn đề tìm cây
tối ưu trên đồ thị với các nút được đánh số từ 1 đến 7. Và 3 đồ thị sau thể
hiện cho đồ thị ở bước

trong quá trình tạo ra các trạng thái để

tìm lời giải. Với quy định là khi một phép chuyển được thực hiện sẽ bao
gồm một cạnh được lấy ra và một cạnh được thêm vào để giữ nguyên cây.

25