Luận văn Chương trình quản lý việc xếp phòng cho sinh viên ở ký túc xá

MỤC LỤC

CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI VÀ NGHIỆP VỤ BÀI TOÁN 1

1.1 Động cơ và mục tiêu 1

1.2 Giới thiệu nghiệp vụ bài toán xếp phòng sinh viên tại ký túc xá 3

1.2.1 Giới thiệu ký túc xá Đại học Bách Khoa 3

1.2.2 Các chính sách quản lý việc đăng ký vào ở ký túc xá 4

1.3 Quy ước các thuật ngữ và ký hiệu 5

CHƯƠNG 2: CÁC CÔNG TRÌNH LIÊN QUAN VÀ CƠ SỞ LÝ THUYẾT 7

2.1 Các công trình liên quan 7

2.2 Tìm kiếm cục bộ 8

2.2.1 Giải thuật Hill-Climbing 8

2.2.2 Giải thuật Tabu search 8

2.2.3 Giải thuật mô phỏng luyện kim ( Simulated Annealing ) 9

2.2.4 So sánh ba kỹ thuật tìm kiếm cục bộ 9

2.3 Giải thuật mô phỏng luyện kim (Simulated Annealing) 9

2.3.1 Liên hệ giữa luyện kim vật lý và mô phỏng luyện kim 10

2.3.2 Giải thuật Simulated Annealing 11

2.3.3 Sự phân bố đều và tính hội tụ 13

2.3.4 Lịch biểu làm nguội 14

2.4 Giải thuật mô phỏng luyện kim cải tiến 15

2.4.1 Vấn đề tổng quát 15

2.4.2 Hai giải thuật mô phỏng luyện kim cải tiến 17

2.4.3 Sự hợp lý của các đề nghị này 18

2.5 Localized Simulated Annealing 19

2.5.1 Các không gian con và đánh giá trên các vùng này 20

2.5.2 Chiến thuật LSA 21

2.5.3 Đánh giá giải thuật LSA 24

2.6 Informed Simulated Annealing 25

2.6.1 Tiện ích của các cặp biến-giá trị 25

2.6.2 Tiện ích trong tìm kiếm mô phỏng luyện kim thực tế 29

2.6.3 Hiện thực ISA 34

2.7 So sánh LSA với ISA và lựa chọn kỹ thuật giải quyết bài toán 39

CHƯƠNG 3: THIẾT KẾ CHƯƠNG TRÌNH 40

3.1 Giới thiệu về các ràng buộc của hệ thống 42

3.1.1 Ràng buộc cứng 42

3.1.2 Ràng buộc mềm 43

3.1.3 Các ràng buộc phòng – sinh viên 44

3.1.4 Các ràng buộc sinh viên – sinh viên 45

3.2 Hàm mục tiêu 47

3.2.1 Giới thiệu về hàm mục tiêu 47

3.2.2 Công thức xác định hàm mục tiêu 47

3.3 Lịch biểu làm nguội 48

3.3.1 Lịch biểu làm nguội cấp số nhân 48

3.4 Lời giải lân cận 49

3.5 Thiết kế hệ thống 49

3.5.1 Khối chức năng quản lý sinh viên 50

3.5.2 Khối chức năng xếp phòng 51

3.5.3 Khối chức năng quản lý ký túc xá 51

3.6 Thiết kế dữ liệu cho chương trình 51

3.6.1 Dữ liệu quản lý ký túc xá 51

3.6.2 Dữ liệu đăng ký vào ở của sinh viên 53

3.6.3 Dữ liệu chi phí cho các ràng buộc 55

3.7 Thiết kế giao diện người dùng 55

3.7.1 Quản trị 56

3.7.2 Quản lý sinh viên 56

3.7.3 Quản lý ký túc xá 57

3.7.4 Xếp phòng 57

3.7.5 Báo cáo 58

3.7.6 Trợ giúp 58

CHƯƠNG 4: HIỆN THỰC VÀ KẾT QUẢ THỰC NGHIỆM 61

4.1 Hiện thực chương trình 61

4.1.1 Tạo lời giải ban đầu thỏa mãn ràng buộc cứng 62

4.1.2 Kỹ thuật chọn lời giải lân cận 62

4.1.3 Hàm mục tiêu 63

4.1.4 Lịch biểu làm nguội cấp số nhân có số lần thực thi xác định trước 65

4.1.5 Giải thuật ISA 66

4.2 Hiện thực giao diện người dùng 67

4.3 Kết quả thực nghiệm 71

CHƯƠNG 5: TỔNG KẾT VÀ ĐÁNH GIÁ 74

5.1 Tổng kết 74

5.2 Đánh giá 75

5.2.1 Ưu điểm 75

5.2.2 Hạn chế 76

5.3 Hướng phát triển của luận văn 77

TÀI LIỆU THAM KHẢO 78

PHỤ LỤC i