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

CHƯƠNG 1

GIỚI THIỆU ĐỀ TÀI VÀ NGHIỆP VỤ BÀI TOÁN

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

Năm nào cũng vậy , cứ vào đầu mỗi năm học, các trường đại học, cao đẳng lại có thêm hàng ngàn tân sinh viên nhập học. Một số lượng lớn các sinh viên này sinh sống ở các tỉnh khác nên phải ở trọ ở thành phố. Việc giải quyết nơi ăn chốn ở cho sinh viên ngày càng được xã hội và lãnh đạo ở các trường quan tâm nhằm giải quyết chỗ ở ổn định cho sinh viên để các em có đủ điều kiện và môi trường sống tốt để yên tâm học tập. Ký túc xá vẫn là nơi ở được ưu tiên hàng đầu mà sinh viên lựa chọn. Không những thế đây cũng là nơi các trường mong muốn sắp xếp cho sinh viên của mình vì tính an toàn, kỷ luật, tiện lợi cũng như chi phí ở phải chăng, phù hợp với hoàn cảnh các sinh viên xa nhà. Mặc dù cho đến thời điểm hiện tại, các ký túc xá vẫn chưa đáp ứng được đầy đủ nhu cầu của sinh viên nhưng việc mở rộng, nâng cấp hạ tầng ký túc xá cũng như cung cách quản lý ký túc xá, sắp xếp phòng ở cho sinh viên đang được lãnh đạo trường quan tâm và từng bước xây dựng. Ký túc xá đại học Bách Khoa tất nhiên cũng không nằm ngoài tiến trình cải tiến và thay đổi đó. Tuy nhiên với một số lượng sinh viên đông đảo với nhiều loại hình đào tạo ( đại học, cao đẳng, cao học, v.v ) và chuyên ngành đa dạng như đại học Bách Khoa ( hơn 10 chuyên ngành ), ngoài việc mở rộng xây dựng và hiện đại hóa ký túc xá, việc cải tiến quy trình quản lý cũng cần được đặc biệt quan tâm. Trong đó, qui trình sắp xếp phòng ở cho sinh viên sao cho đáp ứng được nguyện vọng, sở thích của sinh viên thực sự là một bài toán phức tạp.

Hiện nay, hầu như các ký túc xá của các trường đại học trong thành phố đều thực hiện việc xếp phòng cho sinh viên trong ký túc xá bằng tay ở đầu mỗi học kỳ. Hậu quả là tốn rất nhiều thời gian nhưng không hiệu quả, trong đó hầu hết các ký túc xá đều không quan tâm đến các sở thích của sinh viên như: nghe nhạc, chơi thể thao, bạn ở cùng phòng Điều này làm cho các sinh viên không thực sự hài lòng và thoải mái trong khi ở ký túc xá như không được ở chung với những người bạn cùng khoa, cùng quê hay cùng sở thích, để có thể quan tâm và giúp đỡ lẫn nhau về tinh thần, cùng học tập hay chia sẻ những sở thích giống nhau về thể thao, ca nhạc, v.v

Chúng ta có thể chia việc xếp phòng này ra thành 2 giai đoạn khác nhau. Đầu tiên là xếp phòng thỏa mãn ràng buộc cứng nghĩa là sắp xếp sao cho sinh viên nam thì ở phòng dành cho nam, sinh viên nữ thì ở phòng dành cho nữ, sắp xếp sao cho không vượt quá số người tối đa ở mỗi loại phòng, và phải ưu tiên sắp xếp các sinh viên thuộc diện chính sách, sinh viên đăng ký lại. Với một số lượng phòng lớn và diện tích khác nhau cũng như số lượng giường hữu hạn, việc sắp xếp hàng ngàn sinh viên vào các phòng cùng với các ràng buộc cứng như trên không đơn giản. Thứ hai việc sắp xếp phải thỏa mãn càng nhiều càng tốt các ràng buộc mềm tức là thỏa mãn sở thích của các sinh viên thì việc xếp phòng trở nên rất phức tạp và không thể giải quyết bằng cách xếp bằng tay vì tốn quá nhiều thời gian và công sức. Lấy ví dụ là ký túc xá có gần 3000 giường và mỗi sinh viên có khoảng 20 tiêu chí lựa chọn cần phải được thoả mãn thì số ràng buộc cần phải thoả mãn cho tất cả các sinh viên là 60000, và số cách sắp xếp 3000 sinh viên vào các giường là 3000! Đây là một con số tổ hợp quá lớn mà nếu sắp xếp bằng tay thì với một vài nhân viên quản lý ký túc xá gần như không thực hiện được trong thời gian ngắn để có thể khảo sát một lời giải thích hợp.

Trước những yêu cầu thực tế cần thiết đó, một chương trình xếp phòng cho sinh viên ở ký túc xá chạy hoàn toàn tự động cần được xây dựng là điều tất yếu. Yêu cầu chung là chương trình phải chạy nhanh, đáp ứng được các ràng buộc của sinh viên, có khả năng mở rộng, và dễ thêm bớt những ràng buộc do các thay đổi về nhu cầu của sinh viên hoặc các thay đổi về chính sách quản lý ký túc xá. Chương trình cần được tham khảo và phân tích kỹ càng từ nghiệp vụ thực tế để được hiện thực một cách đầy đủ và nghiêm túc. Đây chính là động cơ và cũng chính là mục tiêu cốt lõi của đề tài: cung cấp một chương trình xếp phòng cho sinh viên tại ký túc xá Đại hoc Bách Khoa với tài nguyên là một số lượng phòng, số lượng giường có giới hạn cùng với một lượng lớn sinh viên tương ứng; không những thế việc sắp xếp phải quan tâm đến các nguyện vọng và sở thích của sinh viên như chọn bạn cùng quê, cùng khoa, cùng sở thích về thể thao hay âm nhạc, và đáp ứng càng nhiều càng tốt các ràng buộc mềm trên. Độ tối ưu của bài toán được đo trên số lượng các ràng buộc được thỏa mãn theo thứ tự ưu tiên do người quản lý chương trình đưa ra.

Từ thực trạng đã nêu trên, chúng tôi sẽ xây dựng một hệ thống cơ sở dữ liệu để quản lý tài nguyên trong ký túc xá Đại học Bách Khoa như phòng, giường cũng như thông tin cá nhân về các sinh viên trong ký túc xá, và chương trình thực hiện việc xếp phòng cho sinh viên ở ký túc xá. Dữ liệu thu thập cho đề tài được xây dựng trên cơ sở số phòng, số giường, số sinh viên và các ràng buộc mềm trên cơ sở tham khảo ý kiến của ban giám đốc ký túc xá. Dữ liệu mẫu được thực hiện trên 3000 sinh viên và tài nguyên là ký túc xá có ba dãy nhà, mỗi dãy nhà có chín lầu, ngoài lầu trệt là tầng dịch vụ, quản lý hành chính, sân chơi thể thao thì mỗi lầu có 12 phòng và sức chứa của mỗi phòng là từ 8 đến 16 giường, một giường dành cho một sinh viên, Các ràng buộc mềm được quan tâm đến gồm có: sở thích về nghe nhạc, sở thích chơi thể thao, sinh viên có hút thuốc hay không, sinh viên đi làm thêm có nhu cầu học khuya, các nguyện vọng chọn bạn cùng phòng do cùng quê, cùng khoa, cùng tuổi, sở thích chọn phòng như chọn tầng, giá thuê (phòng),

Để tránh trường hợp hệ thống được hiện thực một cách cứng nhắc, không mềm dẻo và khó tùy biến, chỉ giới hạn cho mô hình một ký túc xá nhất định nào đó, chúng tôi sẽ trình bày phương pháp luận và phương hướng giải quyết cho bài toán xếp phòng tổng quát trước nhất. Khi đi vào giai đoạn hiện thực, đề tài sẽ áp dụng phương pháp luận ấy lên tập dữ liệu và hoàn cảnh cũng như thông tin đăng ký cụ thể tại ký túc xá trường Đại học Bách Khoa