Học từ ví dụ.
Nghiên cứu từ
bài toán thật.

Một học phần có thể mở nhiều lớp, mỗi lớp có nhiều buổi lý thuyết hoặc thực hành. Vì vậy, 80 học phần không mặc nhiên tương đương 80 biến quyết định. Nếu mỗi học phần mở hai lớp và mỗi lớp học ba buổi một tuần, mô hình cần biểu diễn 480 buổi. Phòng và giảng viên được gán cho từng buổi, còn các quan hệ cùng lớp giữ tính nhất quán của lịch.

Dữ liệu tối thiểu gồm mã buổi, học phần, giảng viên, nhóm sinh viên, sĩ số, loại phòng, miền ca và thời lượng. Danh mục phòng có sức chứa, thiết bị, cơ sở và ca bị khóa. Giảng viên có ca bận và điều kiện chuyên môn. Dùng mã định danh để liên kết các bảng, tránh ghép theo tên viết tự do.

Ví dụ trong mô phỏng. Cấu hình liên ngành có 40 giảng viên, 80 học phần, 20 phòng và 3 cơ sở. Bộ sinh hiện quy ước mỗi học phần có một lớp và một buổi 50 phút, nên có đúng 80 dòng cần xếp. Đây là giả thiết để thí nghiệm, cần mở rộng trước khi dùng với dữ liệu đào tạo thực.

Câu hỏi nghiên cứu. Khi nhân số buổi lên ba lần nhưng giữ nguyên số phòng, mật độ miền khả dụng và thời gian tìm lịch thay đổi thế nào?

Với mỗi buổi e, đặt biến x(e,t,r) bằng 1 khi buổi được xếp vào ca t và phòng r. Điều kiện đầu tiên là tổng x(e,t,r) trên miền hợp lệ bằng 1. Loại phòng, sức chứa và ca bận có thể dùng để lọc miền trước khi giải. Các cặp buổi dùng chung giảng viên, phòng hoặc nhóm sinh viên phải có khoảng thời gian không giao nhau.

Không chỉ so sánh mã ca. Hai ca 08:00–08:50 và 08:30–09:20 có mã khác nhau nhưng vẫn chồng lấn. Với hai khoảng cùng ngày, có giao nhau khi start₁ < end₂ và start₂ < end₁. Hai buổi tiếp giáp không chồng lấn, nhưng có thể chưa đủ thời gian di chuyển.

Điểm phạt mềm chỉ được tính khi lịch vượt qua toàn bộ kiểm tra cứng. Mô phỏng để trống điểm phạt của lịch vi phạm để tránh hiểu rằng một lịch sai có thể bù bằng sở thích tốt hơn. Ví dụ, lớp 54 sinh viên không thể vào phòng 45 chỗ dù giúp giảng viên tránh ca muộn.

Bài tập. Chuyển sang “Phòng chuyên dụng và sức chứa”, giảm sức chứa bằng cách đổi phòng rồi đọc lý do bị loại. Phân biệt lỗi thiếu chỗ với lỗi sai loại phòng.

Gọi τ(A,B) là số phút cần đi từ cơ sở A tới B. Với hai buổi liên tiếp của cùng giảng viên hoặc nhóm sinh viên trong ngày, điều kiện là start(sau) − end(trước) ≥ τ(A,B). Lịch 08:00–08:50 tại A, tiếp theo 09:00–09:50 tại B chỉ có 10 phút nghỉ. Nếu τ(A,B)=25, cần dịch buổi sau ít nhất tới 09:15 hoặc đổi cơ sở.

Không bắt buộc ma trận đối xứng. Bộ mẫu dùng A→B là 25 phút, B→A là 30 phút, A→C là 35 phút và C→A là 40 phút. Đây là số liệu giả lập. Anh có thể thay từng chiều trong mô phỏng để phân tích giao thông hoặc thời gian đệm. Trong cùng cơ sở, thời gian di chuyển hiện được quy ước bằng 0.

Mô phỏng kiểm tra các chặng liên tiếp theo trình tự buổi học, không cộng thời gian di chuyển qua đêm. Nếu có buổi trung gian tại B, hành trình A→B→C được kiểm tra thành hai chặng. Khi đối sánh ITC 2019, phải đọc riêng ngữ nghĩa SameAttendees và travel trong dữ liệu chuẩn, không đồng nhất tự động với quy tắc của bộ mô phỏng này.

Thí nghiệm. Tăng A→B từ 25 lên 60 phút, giữ B→A ở 30. Ghi lại lớp nào phát sinh lỗi và thử sửa bằng đổi ca hoặc đổi phòng.

Mô hình hiện tính P = w₁·n₁ + w₂·n₂ + w₃·n₃ + w₄·n₄. Các đại lượng lần lượt là vi phạm ưu tiên sáng thứ Hai/thứ Sáu của một giảng viên, số lớp bắt đầu từ 15:00, số lượt giảng viên đổi cơ sở trong ngày và số nhóm 10 ghế trống. Đơn vị đếm cần công bố rõ, vì trọng số bằng nhau chưa có nghĩa mức ảnh hưởng bằng nhau.

Ví dụ giả định, lịch L₁ có 3 lớp muộn và 1 lượt đổi cơ sở. Lịch L₂ có 1 lớp muộn và 4 lượt đổi cơ sở. Nếu w_muộn=2 và w_đi=2 thì hai điểm tương ứng là 8 và 10. Nếu w_đi=1 thì điểm là 7 và 6, thứ tự đảo chiều. Đây là phép tính minh họa, không phải kết quả thực nghiệm của cấu hình lớn.

Hãy giữ nguyên dữ liệu, thay từng trọng số, rồi so sánh cả điểm tổng và vector thành phần. Nếu thứ tự ưu tiên là tuyệt đối, có thể nghiên cứu tối ưu từ điển thay vì chọn trọng số rất lớn. Đồng thời, cân nhắc độ công bằng giữa giảng viên, vì tổng phạt thấp có thể dồn bất tiện cho một người.

Bài tập. Chọn hai phương án tìm được, đặt trọng số di chuyển lần lượt 0, 2 và 10. Giải thích sự thay đổi bằng số lượt đổi cơ sở.

ASP phù hợp để thực hành luật khai báo, lựa chọn và ràng buộc. Với CP có thể nghiên cứu biến miền hữu hạn và ràng buộc toàn cục. SAT/MaxSAT biểu diễn điều kiện bằng mệnh đề và phần tối ưu có trọng số. MIP dùng biến nguyên, điều kiện tuyến tính và hàm mục tiêu. Không nên kết luận một phương pháp tốt nhất chỉ từ một ví dụ hoặc một kích thước dữ liệu.

Thiết kế baseline phải đồng nhất dữ liệu vào, điều kiện khả thi, cách tính phạt, giới hạn thời gian và phần cứng. Trước khi so thời gian, đưa lịch của mọi bộ giải qua cùng bộ kiểm tra độc lập. Một cách mã hóa bỏ sót ràng buộc di chuyển có thể chạy nhanh nhưng đang giải một bài toán khác.

Phạm vi công cụ trên trang. Bộ mô phỏng chạy JavaScript trong trình duyệt, không gọi Clingo, CP hay MIP. Năm ví dụ nhỏ dùng duyệt tổ hợp có giới hạn thời gian và số nút. Kịch bản lớn dùng lịch khởi tạo tham lam và thử thay đổi có giới hạn, nên phương án tốt nhất tìm thấy chưa chứng minh tối ưu.

Thực hành tiếp. Tải JSON của cấu hình, viết bộ chuyển đổi sang dữ kiện ASP và dùng Clingo để tạo một baseline riêng. Tệp LP dưới mô phỏng chỉ dành cho ví dụ 4 lớp.

Bộ mẫu có ba mức, lần lượt 12/24/8/2, 40/80/20/3 và 200/270/45/3 theo thứ tự giảng viên, học phần, phòng, cơ sở. Hai mức đầu có 30 ca mỗi tuần, mức cuối có 36 ca. Đây là cấu hình tổng hợp để khám phá giao diện và quy tắc, chưa phải bộ đối sánh đại diện cho một trường cụ thể.

Nên tách thí nghiệm theo từng trục. Giữ số phòng và ca cố định khi tăng lớp để quan sát độ chật. Giữ số lớp cố định khi tăng cơ sở và thời gian di chuyển để đo ảnh hưởng phân tán địa lý. Tăng tỷ lệ lớp thực hành để khảo sát nút thắt phòng chuyên dụng. Nếu thay tất cả cùng lúc, khó xác định nguyên nhân của chênh lệch.

Ghi số lớp đã xếp, số vi phạm, điểm thành phần, thời gian dựng lịch, thời gian tìm kiếm và trạng thái kết thúc. Với phương pháp ngẫu nhiên cần nhiều lần chạy và seed; với bộ sinh hiện tại, cùng cấu hình cho dữ liệu xác định. Tách tập dùng chỉnh tham số khỏi tập đánh giá độc lập để giảm thiên lệch lựa chọn.

Bài tập. Tạo 80 học phần với 20, 12 rồi 8 phòng. Tải mỗi bộ JSON và ghi nhận phần nào bắt đầu thiếu tài nguyên. Không kết luận vô nghiệm chỉ vì thuật toán chưa xếp đủ lớp.

Nếu hai lớp đều buộc học cùng ca và chỉ có một phòng phù hợp, chúng không thể cùng được phục vụ. Ví dụ nhỏ “Vô nghiệm do phòng lab bị khóa ca” minh họa trường hợp miền ca của cả hai lớp chỉ chứa sáng thứ Hai. Bộ duyệt có thể kiểm tra hết miền để xác nhận không có lịch thỏa mãn mô hình này.

Ngược lại, tìm kiếm có giới hạn có thể dừng trước khi gặp lịch hợp lệ. Khi đó, thông báo đúng là “chưa tìm thấy”, kèm giới hạn đã dùng. Lịch khởi tạo có lớp chưa xếp không phải chứng cứ vô nghiệm. Một thứ tự xếp khác hoặc bộ giải khác có thể tìm được phương án.

Để chẩn đoán, lập danh sách phòng hợp lệ cho từng lớp, kiểm tra ca bận, rồi xem các lớp cạnh tranh cùng một nguồn lực. Nhóm điều kiện theo mã và thử nới từng nhóm trên bản sao dữ liệu. Khi có công cụ hỗ trợ, nghiên cứu unsat core hoặc tập ràng buộc xung đột tối tiểu; kết quả luôn gắn với cách mã hóa và giả thiết cụ thể.

Câu hỏi nghiên cứu. Lời giải thích “thiếu một phòng lab vào T2” có thể chuyển thành đề xuất đổi ca nào với chi phí thấp nhất, mà vẫn giữ các điều kiện bắt buộc khác?

Bộ kiểm tra nên nhận dữ liệu và lịch, xác nhận mỗi lớp có đúng một vị trí rồi kiểm tra miền ca, loại phòng, sức chứa, chồng lấn, ca bận và di chuyển. Sau đó tính lại điểm phạt từ lịch thay vì tin giá trị mà thuật toán gửi ra. Nên tách phần kiểm tra khỏi phần tìm kiếm để giảm nguy cơ hai phần cùng chia sẻ một lỗi suy luận.

Các ca kiểm thử biên quan trọng gồm sĩ số bằng sức chứa, hai buổi tiếp giáp, khoảng nghỉ đúng bằng số phút di chuyển, ca khác mã nhưng chồng lấn và hai chiều A→B/B→A khác nhau. Với kiểm thử biến hình, đổi tên mã phòng đồng nhất phải giữ tính khả thi; tăng sức chứa phòng không được tạo lỗi thiếu chỗ mới.

Nút tải JSON lưu dữ liệu kịch bản đang dùng, lịch hiện tại và trọng số. CSV phục vụ xem lịch theo dòng trong bảng tính. JSON là đầu vào thuận tiện để viết validator riêng. Có thể dùng nút Nhập JSON trong Kho dữ liệu xếp lịch để mở lại tệp, kiểm tra cấu trúc rồi chỉnh dữ liệu. Muốn lưu lên máy chủ và mở trên thiết bị khác, cần đăng nhập và chọn Lưu thành bản mới hoặc Cập nhật bản đang mở. Ghi thêm phiên bản chương trình, phần cứng, giới hạn chạy và cách sinh dữ liệu trong hồ sơ thực nghiệm.

Bài tập. Tải lịch có xung đột và lịch đã sửa, chạy một trình kiểm tra bên ngoài, rồi đối chiếu từng thông báo với bộ mô phỏng trên trang.