Task #1476
Cập nhật bởi Hải Yến Ngô cách đây 2 tháng
# **1. Mục đích** Màn hình “Xếp Xây dựng chức năng xếp thời khóa biểu tự động” dùng để: Cho phép người dùng cấu hình tham số xếp lịch (ràng buộc cứng/mên, thứ tự ưu tiên, thiết lập ràng buộc tiết ) Chọn phạm vi xếp (khoá, quý => khi cần điểu chỉnh thì có thể chọn phạm vi nhỏ hơn như tiểu đoàn, đại đội / tuần,tháng ) Thực hiện xếp tự động cho từng khóa đào tạo trong quý nhằm: Theo dõi tiến trình Giảm thao tác xếp lịch thủ công Xem kết quả sau khi xếp Tự động phân bổ môn học, bài học theo đúng quy định huấn luyện Kiểm tra Đảm bảo tuân thủ các lỗi/ràng buộc không xếp được Các bước sử dụng thuật toán **Bước 1** : Sử dụng Rule-based để chọn các ràng buộc Ràng buộc cứng : không được phép vi phạm Ràng buộc mềm: cảnh báo khi vi phạm và có tính điểm khi vi phạm (khi thêm có cột penalty để ghi đánh giá điểm) đào tạo **Bước 2** : Sử dụng Priority-based (thứ tự Hỗ trợ tối ưu tiên ) lịch học theo ngày, tuần, quý Thứ tự ưu tiên lớp Hạn chế xung đột: Thứ tự ưu tiên môn Phòng học **Bước 3** : Dùng greedy Xếp lớp ưu tiên đầu tiên trước sau đó lần lượt đến các lớp có thứ tự đằng sau Mỗi lớp thì xếp môn ưu tiên đầu tiên trước Mốc huấn luyện Kế hoạch huấn luyện Ràng buộc bài học Hỗ trợ người dùng tinh chỉnh thủ công sau đến các môn có thự tự đằng sau Thuật toán sẽ chọn phương án tốt nhất ngay tại thời điểm hiện tại mà không xét đến toàn cục **Bước 4** : Sau khi xếp xong thì sẽ tính điểm penalty(bị vi phạm các ràng buộc mềm) có cả thời khoá biểu , điểm penalty đã được quy định từ trước khi tạo ra ràng buộc. **Bước 5** : Sử dụng Hệ thống sử dụng: Greedy Algorithm để xếp lịch sơ bộ Hill Climbing để điều tối ưu và tinh chỉnh thời khoá biểu cho đẹp lịch Thuật toán tìm kiếm cục bộ, cải thiện dần lời giải bằng cách chọn phương án tốt hơn lân cận Sẽ dựa vào điểm penalty để điểu chỉnh sao cho điểm penalty xuống 0 hoặc thấp nhất có thể # **2. Câu chuyện 2. Yêu cầu nghiệp vụ (Business Story)** ## 2.1 Câu chuyện nghiệp vụ **** Hiện tại việc xếp thời khóa biểu đang thực hiện chủ yếu bằng tay: - Xếp cho từng khoá/lớp , chọn Chọn từng ngày , chọn Chọn từng môn/ bài học,... học Phải tuân Kiểm tra thủ các mốc công: Mốc huấn luyện, lịch thi, phòng luyện Lịch thi Phòng học , tiết Tiết học và giảng viên, Kế hoạch huấn luyện, thứ tự bài học , ràng buộc, thể loại tiết Giảng viên Trong thực tế: Một khóa có nhiều lớp, có nhiều khoá trong 1 khoảng thời gian , một lớp Một quý có nhiều môn học và có Có nhiều ràng buộc phức tạp , thường Thường xuyên thay đổi kế hoạch huấn luyện ## **2.2 Các vấn đề gặp phải: Tốn nhiều thời gian xếp lịch Dễ xung đột phòng học Dễ vi phạm kế hoạch huấn luyện Khó đảm bảo đúng thứ tự bài học Khó tối ưu phân bố lịch học Do đó cần chức năng xếp tự động hỗ trợ: Xếp sơ bộ nhanh Tự động xử lý ràng buộc Tinh chỉnh tối ưu lịch Cho phép người dùng chỉnh sửa tiếp bằng tay 2.2 Mong muốn** muốn Người dùng mong muốn: Chỉ cần chọn quý và khoá khóa đào tạo và quý → hệ thống tự xếp, sẽ có các chế độ xếp (xếp mới toàn bộ, xếp không Không ghi đè vào các tiết lịch đã xếp và tay Chỉ xếp lại toàn bộ trừ vào ô còn trống Có thể bấm “Xếp tự động” nhiều lần để xếp tiếp các tiết đã khoá ) vào tuân còn dư Tuân thủ các ràng buộc đầy đủ: Mốc huấn luyện Kế hoạch huấn luyện Thứ tự bài học Loại hình bài học Quy tắc môn học Tự động tối ưu lịch: Giảm tiết lẻ Giảm khoảng trống Hạn chế học quá tải Ngoài ra: Ưu tiên xếp buổi sáng các bài học chính Buổi chiều dùng để: Xếp lịch dư Dồn lịch thay đổi Xử lý conflict ## **2.3 2.3 Khó khăn** khăn - Về nghiệp vụ : Có nhiều loại tiết, có tiết: Có nhiều ràng buộc đặc thù quân sự. có sự Có các block cứng không được xếp Tốn nhiều thời gian xếp lịch Dễ xung đột phòng học Dễ vi phạm kế hoạch huấn luyện Khó đảm bảo đúng thứ tự bài học Khó tối ưu phân bố lịch học Lưu ý: Có các môn ưu tiên cao: Chiến thuật Bắn súng Thao trường # - Về dữ liệu Một quý có nhiều bài học Một bài có nhiều loại hình Có bài kéo dài nhiều ngày Có bài yêu cầu đúng khoảng thời gian - Về thuật toán Khó tối ưu toàn bộ lịch ngay từ đầu Nhiều conflict: Phòng học Tiết học Khoảng cách lịch Tiết lẻ Khó đảm bảo toàn bộ constraint đều đúng 100% 3. Quy tắc chi tiết **** : https://docs.google.com/document/d/1HDzj-z-5y2KyyhDe9dFOk0w_GRuMTAFpG094hAkQss8/edit?tab=t.u3ogbg4k9mm6 [[https://docs.google.com/document/d/1HDzj-z-5y2KyyhDe9dFOk0w_GRuMTAFpG094hAkQss8/edit?pli=1&tab=t.u3ogbg4k9mm6 4. Kết quả mong muốn ]] Sau khi xếp: # 4. GIẢI PHÁP PHẦN MỀM **** Không vi phạm hard constraint **4.1: Các chức năng ảnh hưởng ** Xếp thời khoá biểu Giảm tối đa soft constraint **4.2: Giải pháp ** Sử dụng tất cả các ràng buộc Không conflict phòng học Sử dụng thuật toàn phù hợp Đảm bảo đúng thứ tự bài học Chọn ra các mục ưu tiên hợp lý Đảm bảo đúng kế hoạch huấn luyện 4.