Luận Văn Á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

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

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.

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

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

Công nghệ thông tin ngày càng phát triển, vì vậy việc quản lý dữ liệu và làm việc trên máy tính không còn xa lạ với mọi người. Do đó, khoa CNTT muốn xây dựng chương trình sắp thời khóa biểu thực hành trên máy tính để đáp ứng nhu cầu của khoa.
Trong mỗi học kỳ, các lớp đều có thời khóa biểu của mình trong học kỳ đó gồm lịch học các môn lý thuyết và lịch thực hành. Lịch lý thuyết của các khoa do phòng Đào Tạo sắp, còn đối với khoa CNTT, giáo vụ khoa phải xếp lịch thực hành cho mỗi lớp với các môn thực hành thuộc khoa CNTT và nhập môn tin học cho các khoa khác.
Mục tiêu cuối cùng của hệ thống, là giúp Giáo Vụ khoa dễ dàng trong việc sắp thời khoá biểu thực hành phù hợp cho cả giảng viên, các lớp thuộc khoa và các khoa khác của trường Đại Học Nông Lâm, dựa trên thời khóa biểu từ phòng Đào Tạo và một số điều kiện thực tế của khoa như:
+ Số phòng thực hành hạn chế nên một số lớp phải thực hành cả ngày chủ nhật.
+ Tình trạng giảng viên canh thực hành còn thiếu, vì thế một số giảng viên có thể phải canh thực hành cả 2 phòng
+ Đối với một số môn học không được thực hành tại một số phòng máy nhất định vì tốc độ máy chậm, thiếu các chương trình cài đặt (như phòng M306, phòng P4) nên không đáp ứng được yêu cầu học tập.
+ Ràng buộc về thời gian thực hành của các lớp, cùng một lớp môn có thể thực hành cùng một thời gian nhưng phải khác phòng.
+ Số tiết thực hành của một môn không được rơi vào 2 buổi (tiết 6 và tiết 7 hoặc tiết 12 và tiết 1).

MỤC LỤC

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