UBND TỈNH QUẢNG NAM
TRƯỜNG ĐẠI HỌC QUẢNG NAM
KHOA: CÔNG NGHỆ THÔNG TIN
----------
NGUYỄN THỊ THÚY KIỀU
BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU VÀ ỨNG
DỤNG XÂY DỰNG CHƯƠNG TRÌNH
LẬP THỜI KHÓA BIỂU
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC
Quảng Nam, tháng 04 năm 2017
LỜI CẢM ƠN
Trên thực tế không có thành công nào mà không gn lin vi s htrợ, giúp đ
ít hay nhiu, trực tiếp hay gián tiếp t ngưi khác. Thật vậy! Trong suốt thời
gian thực hin đ i khóa luận ca nh, tôi luôn nhận được s quan m ng dẫn,
chỉ bo tận tình từ Thy giáo, Thạc sĩ Huỳnh Tấn Khải đth hn thành tt lun
văn này. Tôi xin trân trọng gửi đến Thầy một lời cảm ơn sâu sắc!
Tôi cũng xin chân thành cm ơn qThầy, Cô khoa Công nghệ thông tin, trường
Đại học Quảng Nam đã tận tình truyền đt kiến thức cho tôi trong suốt bốn năm hc
tại trường. Với vốn kiến thức được tiếp thu trong quá trình học tập không chỉ là nền
tảng cho qtrình nghiên cứu đề tài này mà còn là hành trang q báu đi bước vào
đời mt cách vững chắc tự tin.
Tôi cũng thầm biết ơn sự ng hộ ca gia đình, bn bè những ni tn u
luôn chỗ dựa tinh thần vững chắc cho tôi.
Cuối cùng, tôi xin kính chúc quý Thầy, Cô dồi dào sức khỏe thành công trong
sự nghiệp trồng người cao quý.
Trong quá tnh thực hiện đtài, khó tránh khỏi sai sót, rất mong quý Thầy, Cô
bỏ qua. Đồng thời do trình độ lý luận cũng như kinh nghiệm thực tin còn hn chế nên
bài báo cáo không th tránh khỏi những thiếu sót, rất mong nhận được ý kiến đóng p
t qThầy, đtôi thể học hỏi tm được nhiều kinh nghiệm và sẽ hoàn thành
tt n i o o sắp ti.
Xin chân thành cảm ơn!
Qung Nam, ngày 13 tháng 04 năm 2017
Sinh viên thực hiện
Nguyn Thị Thúy Kiều
UBND TỈNH QUẢNG NAM
TRƯỜNG ĐẠI HỌC QUẢNG NAM
KHOA: CÔNG NGHỆ THÔNG TIN
---------
KHÓA LUẬN TỐT NGHIỆP
Tên đề tài:
BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU VÀ ỨNG
DỤNG XÂY DỰNG CHƯƠNG TRÌNH
LẬP THỜI KHÓA BIỂU
Sinh viên thực hiện:
NGUYỄN THỊ THÙY KIỀU
MSSV: 2113021017
CHUYÊN NGÀNH
CÔNG NGHỆ THÔNG TIN
KHÓA: 2013 – 2017
Cán bộ hướng dẫn
ThS. HUỲNH TẤN KHẢI
Quảng Nam, ngày 14 tháng 04 năm 2017
MỤC LỤC
Phần 1. MỞ ĐẦU ...........................................................................................................1
1.1. Lí do chọn đề tài ................................................................................................1
1.2. Mục tiêu của đề tài .............................................................................................2
1.3. Đối tượng và phạm vi nghiên cứu......................................................................2
1.4. Phương pháp nghiên cứu ...................................................................................2
1.5. Đóng góp của đề tài ...........................................................................................2
1.6. Cấu trúc của đề tài ..............................................................................................3
Phần 2. NỘI DUNG NGHIÊN CỨU ............................................................................4
Chương 1. CƠ SỞ LÝ THUYẾT .................................................................................4
1.1. Giới thiệu bài toán tối ưu tổng quát và phân loại ..............................................4
1.1.1. Giới thiệu bài toán tối ưu tổng quát ............................................................4
1.1.2. Phân loại các bài toán tối ưu .......................................................................5
1.2. Ứng dụng của lý thuyết tối ưu ...........................................................................7
1.2.1. Phương pháp mô hình hóa ..........................................................................7
1.2.2. Một số ứng dụng của lý thuyết tối ưu .........................................................7
1.3. Các phương pháp giải bài toán tối ưu đa mục tiêu ......................................... 10
1.3.1. Phương pháp ràng buộc (Constraint method) .......................................... 10
1.3.2. Phương pháp tổng trọng số ...................................................................... 11
1.3.3. Phương pháp sử dụng giải thuật di truyền (Genetic Alogithm – GA) ..... 13
1.4. Kết chương ...................................................................................................... 22
Chương 2. ỨNG DỤNG GIẢI THUẬT DI TRUYỀN ............................................ 23
VÀO BÀI TOÁN LẬP THỜI KHÓA BIỂU ............................................................ 23
2.1. Tìm hiểu chung về bài toán lập thời khóa biểu ............................................... 23
2.1.1. Mô tả bài toán lập thời khóa biểu ............................................................. 23
2.1.2. Các đối tượng của thời khóa biểu ............................................................ 24
2.1.3. Quy trình lập thời khóa biểu .................................................................... 25
2.2. Ứng dụng giải thuật di truyền vào bài toán lập thời khóa biểu....................... 25
2.2.1. Giai đoạn 1: Xếp lịch học các lớp ............................................................ 26
2.2.2. Giai đoạn 2: Xếp lịch học cho toàn bộ cơ sở ........................................... 33
2.3. Kết chương ...................................................................................................... 36
Chương 3: XÂY DỰNG CHƯƠNG TRÌNH LẬP THỜI KHÓA BIỂU ............... 37
3.1. Phân tích chức năng của hệ thống ................................................................... 37
3.1.1. Biểu đồ phân cấp chức năng (FDD) ......................................................... 37
3.1.2. Mô tả chi tiết chức năng ........................................................................... 37
3.1.3. Danh sách các tác nhân ............................................................................ 39
3.1.4. Biểu đồ ca sử dụng (USECASE - UC) ..................................................... 40
3.2. Xây dựng chức năng của hệ thống .................................................................. 41
3.2.1. Thu thập thông tin tài nguyên .................................................................. 41
3.2.2. Xây dựng chức năng ................................................................................ 43
3.3. Một số giao diện hệ thống ............................................................................... 46
3.3.1. Giao diện chính của hệ thống ................................................................... 46
3.3.2. Giao diện giới thiệu hệ thống ................................................................... 47
3.3.3. Giao diện các ràng buộc Giáo viên .......................................................... 48
3.3.4. Giao diện các ràng buộc Lớp học ............................................................ 48
3.3.5. Giao diện các ràng buộc chung về Khóa học ........................................... 49
3.3.6. Giao diện in danh sách giáo viên ............................................................. 50
3.3.7. Giao diện trang in thời khóa biểu cho giáo viên ...................................... 50
3.3.8. Giao diện thiết lập các ràng buộc cho Giáo viên ..................................... 52
3.3.9. Giao diện thiết lập thông tin ..................................................................... 52
3.3.10. Giao diện thiết lập tiết dạy được/ không được phép xếp thời khóa biểu . 53
3.3.11. Giao diện xếp thời khóa biểu tự động ...................................................... 54
3.3.12. Giao diện trang in thời khóa biểu chính ................................................... 54
Phần 3. KẾT LUẬN VÀ KIẾN NGHỊ ...................................................................... 56
1. Kết luận .............................................................................................................. 56
2. Kiến nghị ............................................................................................................ 56
Phần 4. TÀI LIỆU THAM KHẢO ............................................................................ 57
DANH MỤC HÌNH ẢNH
Hình 1.1 - Các giả thiết của bài toán ............................................................................ 10
Hình 1.2 - Kết quả (giải bằng thuật toán PRIM) .......................................................... 10
Hình 1.3 - Sơ đồ khối của giải thuật di truyền ............................................................. 17
Hình 1.4 - Toán tử Chéo hóa áp dụng cho chuỗi số nguyên hoán vị. .......................... 18
Hình 1.5 - Toán tử chéo hóa áp dụng cho chuỗi nhị phân. .......................................... 18
Hình 1.6 - Toán tử Chéo hóa áp dụng cho chuỗi hoán vị ............................................. 18
Hình 1.7 - Toán tử chéo hóa áp dụng cho chuỗi hoán vị ............................................. 19
Hình 1.8 - Toán tử chéo hóa áp dụng cho chuỗi hoán vị ............................................. 19
Hình 1.9 - Đột biến 2 gen gần nhau .............................................................................. 20
Hình 1.10 - Đột biến 2 gen cách xa nhau ..................................................................... 20
Hình 1.11 - Đột biến 3 gen cách xa nhau ..................................................................... 20
Hình 1.12 - Đột biến đảo ngược chuỗi con .................................................................. 21
Hình 1.13 - Đột biến bằng cách dịch chuyển ............................................................... 21
Hình 2.1 - Quy trình lập thời khóa biểu ....................................................................... 25
Hình 2.2 - Mô hình cá thể trong lịch lớp học ............................................................... 26
Hình 2.3 - Phân bổ các nhiễm sắc thể môn học ........................................................... 28
Hình 2.4 - Bảng phân bố các môn học trên lịch học .................................................... 29
Hình 2.5 - Lai ghép tạo ra 2 cá thể con từ 2 nhiễm sắc thể cha – mẹ ........................... 31
Hình 2.6 - Xác suất xảy ra đối với phép đột biến ......................................................... 33
Hình 2.7 - Mô hình cá thể lịch cơ sở ............................................................................ 34
Hình 3.1 - Biểu đồ phân cấp chức năng hệ thống lập thời khóa biểu .......................... 37
Hình 3.2 - Ký hiệu của ca sử dụng ............................................................................... 41
Hình 3.3 - Biểu đồ ca sử dụng của hệ thống Lập thời khóa biểu ................................. 41
Hình 3.4 - Giao diện chính của hệ thống ...................................................................... 47
Hình 3.5 - Giao diện giới thiệu hệ thống ...................................................................... 48
Hình 3.6 - Giao diện ràng buộc chung cho Giáo viên .................................................. 48
Hình 3.7 - Giao diện các ràng buộc chung cho Lớp học .............................................. 49
Hình 3.8 - Giao diện các ràng buộc chung về Khóa học .............................................. 50