Link tải luận văn miễn phí cho ae Kết nối
2. Mục đích nghiên cứu...........................................................................................................10
3. Nhiệm vụ nghiên cứu..........................................................................................................11
4. Đối tượng và phạm vi nghiên cứu.......................................................................................11
5. Phương pháp nghiên cứu ....................................................................................................11
Chương 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH HIỆN NAY VÀ CÁC CÁCH
TIẾP CẬN ..........................................................................................................................12
1.1 Bài toán lập thời khóa biểu cho trường phổ thông (School timetabling).............................13
1.2 Bài toán lập thời khóa biểu cho trường đại học (University timetabling) ...........................13
1.3 Bài toán lập lịch thi (Examination timetabling)...................................................................14
1.4 Bài toán lập lịch theo tín chỉ ................................................................................................15
1.5 Ưu điểm của cách đào tạo theo tín chỉ....................................................................17
1.6 Các cách tiếp cận hiện nay...................................................................................................18
Chương 2: TỔNG QUAN VỀ CÁC PHƯƠNG PHÁP TÌM KIẾM..................................21
2.1 Xung đột tối thiểu (Min-conflict) ........................................................................................21
2.2 Thuật giải mô phỏng luyện kim (Simulated Annealing) .....................................................21
2.3 Thuật giải leo đồi (Hill-climbing)........................................................................................22
2.4 Tìm kiếm Tabu (Tabu search)..............................................................................................22
2.5 Thuật giải di truyền (Genetic Algorithm) ............................................................................23 2.6 Kết luận................................................................................................................................23
Chương 3: CƠ SỞ TÌM KIẾM TABU...............................................................................24
3.1 Lược Sử Về Tabu Search.....................................................................................................24
3.1.1 Giới Thiệu .....................................................................................................................24
3.1.2 Tabu Search – Một Dạng Meta-heuristic......................................................................25
3.1.3 Các Giai Đoạn Phát Triển Của Tabu Search.................................................................25
3.2 Nguyên Lý Chung Của Tabu Search ...................................................................................26
3.3 Cách Sử Dụng Bộ Nhớ ........................................................................................................27
3.3.1 Một Minh Họa...............................................................................................................28
3.4 Chiến Lược Tăng Cường (Intensification) và Chiến Lược Đa Dạng (Diversification)......30
3.5 Lập Trình Với Bộ Nhớ Tương Thích (Adaptive Memory Programming)...........................31
3.6 Các Nhân Tố Của Bộ Nhớ Tương Thích .............................................................................31
Chương 4: BÀI TOÁN LẬP LỊCH THEO TÍN CHỈ.........................................................33
4.1 Các khái niệm ......................................................................................................................33
4.2 Mô hình của bài toán............................................................................................................35
4.3 Các ràng buộc cứng..............................................................................................................36
4.4 Các ràng buộc mềm .............................................................................................................36
4.5 Ví dụ minh họa: ...................................................................................................................37
4.6 Hướng tiếp cận cho bài toán ................................................................................................38
4.6.1 Bước 1: Khởi tạo lời giải ban đầu ngẫu nhiên ..............................................................39
4.6.2 Bước 2: Cải thiện chất lượng lời giải bằng giải thuật tìm kiếm Tabu...........................40
4.7 Định dạng tập tin dữ liệu CSV đầu vào: ..............................................................................44
4.8 Khảo sát và thống kê kết quả thực nghiệm thực tế ..............................................................45
4.9 So sánh kết quả thực nghiệm với kết quả của phần mềm Open Course Timetable.............47
KẾT LUẬN ........................................................................................................................49
TÀI LIỆU THAM KHẢO..................................................................................................50
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 NP-khó. 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 đượ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á trình nhằm sắp xếp lịch tối ưu nhất. Vì thế bài toán lập lịch là một vấn đề rất
khó để giải quyết.
Những năm gần đây, đã có nhiều hướng phát triển phong phú của các giải
thuật nhằm đưa ra lời giải tốt nhất cho bài toán này. Với đề tài “Giải bài toán lập
lịch theo tín chỉ sử dụng giải thuật tìm kiếm Tabu”, khóa luận mạnh dạn nghiên cứu
một phương pháp mới cho việc giải các bài toán lập lịch cho mô hình các đơn vị,
các cơ sở đào tạo có hình thức tổ chức, hoạt động giống với các Trung tâm Đào tạo
Chứng chỉ Quốc tế theo Tín chỉ.
2. Mục đích nghiên cứu
Bài toán lập lịch đã từ lâu trở thành một bài toán nổi tiếng và thu hút được
sự quan tâm của rất nhiều nhà nghiên cứu, nhiều chuyên gia trong các lĩnh vực liên
quan. Sự “nổi tiếng” của bài toán này không chỉ được đo bởi độ phức tạp của vấn
đề, mà còn ở tính thực tiễn, khả năng áp dụng rất cao trên thực tế. Do đó mục tiêu
của luận văn là: Nghiên cứu kỹ thuật của giải thuật tìm kiếm Tabu cho bài toán lập
lịch theo tín chỉ.
Luận văn sẽ xem xét áp dụng kỹ thuật này vào việc xây dựng chương trình
lập lịch cho mô hình một trung tâm đào tạo theo tín chỉ.
11
3. Nhiệm vụ nghiên cứu
Nghiên cứu, tìm hiểu giải thuật tìm kiếm Tabu và trên cơ sở đó tiếp cận để
giải bài toán lập lịch, sắp xếp thời khóa biểu cho mô hình giảng dạy trong các trung
tâm đào tạo theo tín chỉ hiện nay.
4. Đối tượng và phạm vi nghiên cứu
Tìm hiểu bài toán lập lịch và các hướng giải quyết truyền thống
Tìm hiểu về giải thuật tìm kiếm Tabu
Ứng dụng thuật giải tìm kiếm Tabu vào bài toán lập lịch
Xây dựng ứng dụng lập thời khóa biểu cho các trung tâm đào tạo theo tín
chỉ
5. Phương pháp nghiên cứu
Dựa trên tài liệu thu thập từ nhiều nguồn (tài liệu, bài báo do giảng 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ế.
Chương 1: TỔNG QUAN VỀ BÀI TOÁN LẬP LỊCH HIỆN NAY 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 hay 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 thì chúng ta 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 cuối cùng của người sắp thời khóa biểu là
tạo ra một thời khóa biểu với ít xung đột nhất.
Cũng đã có các khảo sát về bài toán sắp thời khóa biểu. Như việc đưa ra
tổng quan các vấn đề về sắp thời khóa biểu thuộc ba dạng ta đã đề cập ở trên của
Schaerf, 1995 [1]. Các khảo sát về sắp lịch thi Carter & Laporte, 1996 [2] và sắp
lịch cho trường đại học Carter & Laporte, 1998 [3] Bardadym, 1996 [4].
ệm bài toán sắp
Khái niệm được thể hiện bằng hình hộp, các quan hệ là các đường nối các
hình hộp đó. Các khái niệm và các quan hệ giữa các khái niệm đó trong một bài
toán lập lịch được mô tả tổng quát ở hình (a) và được mô tả cụ thể hơn ở hình (b)
1.1 Bài toán lập thời khóa biểu cho trường phổ thông (School timetabling)
Bài toán lập thời khóa biểu cho trường phổ thông hay bài toán phân chia
giáo viên, lớp học trong một tuần đối với tất cả các môn học của một trường học.
Với ba tập hợp cho trước là tập giáo viên, tập lớp học và tập tiết học và một ma trận
ràng buộc số bài giảng một giáo viên được phân công dạy một lớp.
Bài toán yêu cầu phân chia các bài giảng vào các tiết sao cho không giáo
viên hay lớp học nào có cùng một bài giảng trong cùng một thời gian và mỗi giáo
viên đều có một số lượng nhất định các bài giảng với mỗi lớp học.
1.2 Bài toán lập thời khóa biểu cho trường đại học (University 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 gia 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 gia và điều đó có thể tạo ra xung đột và sẽ không thể lập lịch được
/file/d/1NQXftk ... sp=sharing
