Áp dụng giải thuật di truyền và tìm kiếm cục bộ để giải quyết bài toán sắp Thời Khóa Biểu cho khoa Công Nghệ Thông Tin

Ngày nay, công nghệ thông tin đã và đang đóng vai trò quan trọng trong đời sống kinh tế, xã hội của nhiều quốc gia trên thế giới, là một phần không thể thiếu trong xã hội năng động, ngày càng hiện đại hóa. Vì vậy, việc tin học hóa vào một số lĩnh vực ứng dụng là hoàn toàn có thể và phù hợp với xu hướng hiện nay.

Xuất phát từ nhu cầu thực tế đó, việc xây dựng một chương trình sắp thời khóa biểu thực hành là rất cần thiết cho Giáo Vụ khoa, nhằm thay thế một số công việc mà trước đó phải thao tác bằng tay trên giấy tờ đạt hiệu quả không cao, mất nhiều thời gian. Vì vậy, nhóm sinh viên chúng em đã thực hiện luận văn tốt nghiệp với đề tài “Áp dụng giải thuật Di Truyền và tìm kiếm cục bộ để giải quyết bài toán sắp thời khóa biểu cho khoa Công Nghệ Thông Tin (CNTT)”.

Hệ thống “Sắp thời khoá biểu thực hành cho khoa CNTT” sẽ giúp Giáo Vụ khoa trong việc lưu trữ thời khoá biểu từ phòng Đào Tạo đưa xuống và có thể sắp lịch thực hành một cách nhanh chóng, chính xác và đạt hiệu quả cao

NỘI DUNG:

Chương 1: Giới thiệu 1

Chương 2: Phát biểu bài toán 2

I. Phát biểu bài toán 2

II. Mô hình Use Case: 4

1. Lược đồ chính của mô hình usecase: 4

2. Đặc tả từng UseCase: 4

2.1 Use Case Đăng nhập : 4

2.2 Use Case Nhập các thông tin sắp thời khóa biểu 5

2.3 Use Case Sắp xếp thời khoá biểu 7

2.4 Use Case Xem thông tin về thời khoá biểu 8

2.5 Use Case Hiệu chỉnh thời khóa biểu 10

Chương 3: Phương pháp luận 11

I. Mô hình triển khai ứng dụng MVC(Model – View – Controller) 11

II. Mô hình lớp 12

1. Sơ đồ lớp: 12

2. Sequence Diagrams cho từng UseCase 14

2.1 Đăng nhập: 14

2.2. Nhập các thông tin sắp thời khóa biểu : 15

2.2.1 Nhập thông tin về giảng viên: 15

2.2.2 Nhập thông tin về môn học: 17

2.2.3 Nhập thông tin về lớp: 19

2.2.4 Nhập thông tin về phòng: 21

2.2.5 Thông tin về thời khoá biểu lý thuyết: 23

2.3. Sắp thời khoá biểu : 27

2.4. Xem kết quả sắp thời khoá biểu: 29

2.4.1 Xem thời khóa biểu thực hành theo giảng viên : 29

2.4.2 Xem thời khóa biểu thực hành theo lớp: 29

2.4.3 Xem thời khóa biểu thực hành theo phòng: 30

2.4.4 Xem kết quả sắp thời khóa biểu thực hành: 30

2.5. Hiệu chỉnh thời khóa biểu 31

3. Thiết kế cơ sở dữ liệu 32

3.1 Mô hình dữ liệu: 32

3.2. Mô tả bảng trong cơ sở dữ liệu: 33

III. Mô hình xử lý: 43

1 Mô hình hóa bài toán: 43

2. Giải thuật Di Truyền và ứng dụng. 45

2.1 Khái quát về giải thuật Di Truyền: 45

2.2. Ứng dụng giải thuật Di Truyền. 50

3. Chiến lược tìm kiếm tối ưu cục bộ (giải thuật Greedy) và ứng dụng: 52

3.1 Khái quát giải thuật Greedy: 52

3.2. Ứng dụng chiến lược tìm kiếm cục bộ(giải thuật Greedy) 54

Chương 4: Kết quả thực nghiệm 67

I. Môi trường và công cụ phát triển ứng dụng: 67

II. Số liệu thực tế: 67

Chương 5: Kết luận và hướng phát triển 68

I. Kết quả đạt được 68

II. Hạn chế - Hướng phát triển trong tương lai 68

1. Hạn chế: 68

2. Hướng phát triển trong tương lai 68

Tài liệu tham khảo 69

Phụ lục 70

I. Hướng dẫn sử dụng phần mềm 70

LINK DOWNLOAD