Luận Văn Ứng dụng thuật toán mô phỏng luyện kim (Simulated Annealing) xây dựng chương trình quản lý KTX đại h

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.