Xếp thời khóa biểu với ASP và Clingo

1. Bắt đầu bằng một lịch có thể kiểm tra bằng tay

Giả sử một khoa cần xếp bốn lớp học phần vào ba ca sáng thứ Hai, thứ Tư và thứ Sáu. Khoa có một phòng lý thuyết 45 chỗ và một phòng thực hành 24 chỗ. Giảng viên A phụ trách hai lớp lý thuyết, giảng viên B phụ trách Kiểm thử phần mềm và giảng viên C phụ trách Android. Giảng viên C bận sáng thứ Hai.

Mỗi lớp cần đúng một ca và một phòng. Một lịch khả thi phải đủ chỗ, đúng loại phòng, không dùng phòng hai lần trong cùng ca, không xếp giảng viên dạy đồng thời và tránh ca bận. Sau khi thỏa các điều kiện đó, ta ưu tiên lịch không buộc giảng viên A dạy cả sáng thứ Hai lẫn sáng thứ Sáu. Vi phạm ưu tiên này nhận 5 điểm.

2. Biểu diễn dữ liệu, sinh nghiệm và tính điểm

Biến quyết định được biểu diễn bằng nguyên tử xep(L,C,P). Nếu nguyên tử xuất hiện trong nghiệm, lớp L được xếp vào ca C tại phòng P. Quy tắc ung_vien/3 lọc trước các cặp ca–phòng theo điều kiện của từng lớp. Các xung đột giữa hai lớp chỉ xuất hiện khi ghép các lựa chọn, nên được xử lý sau bằng ràng buộc toàn vẹn.

% Chạy: clingo xep_lich.lp --opt-mode=opt
lop(ctdl,a,35,lt).      lop(pttk,a,30,lt).
lop(kiemthu,b,22,th).   lop(android,c,20,th).
ca(t2;t4;t6).
phong(p101,45,lt).     phong(lab02,24,th).
khong_ranh(c,t2).

% Chỉ tạo ứng viên đáp ứng điều kiện riêng của từng lớp.
ung_vien(L,C,P) :- lop(L,G,N,K), ca(C), phong(P,S,K),
                    N <= S, not khong_ranh(G,C).

% Mỗi lớp nhận đúng một cặp ca và phòng.
1 { xep(L,C,P) : ung_vien(L,C,P) } 1 :- lop(L,_,_,_).

% Hai lớp không dùng cùng phòng trong cùng ca.
:- xep(L1,C,P), xep(L2,C,P), L1 < L2.

% Cùng giảng viên không dạy đồng thời hai lớp.
:- xep(L1,C,_), xep(L2,C,_), L1 < L2,
   lop(L1,G,_,_), lop(L2,G,_,_).

day(G,C) :- xep(L,C,_), lop(L,G,_,_).
vi_pham(a) :- day(a,t2), day(a,t6).
#minimize { 5,G : vi_pham(G) }.
#show xep/3.

Trong luật lựa chọn, hai số 1 đặt cận dưới và cận trên bằng nhau. Nhờ đó, mỗi lớp nhận đúng một phần tử từ tập ứng viên. Nếu một lớp không có ứng viên, tập lựa chọn rỗng và bài toán trở thành vô nghiệm. Trong hai ràng buộc xung đột, L1 < L2 giúp xét mỗi cặp một lần và loại trường hợp so một lớp với chính nó.

Luật day/2 suy ra ca dạy từ lịch đã xếp. Sau đó, vi_pham(a) chỉ đúng khi cả hai ca được yêu cầu cùng xuất hiện. Đây là một ưu tiên có điều kiện. Chỉ dạy thứ Hai hoặc chỉ dạy thứ Sáu đều có điểm 0 theo quy tắc này.

3. Chạy và đối chiếu kết quả

clingo xep_lich.lp --opt-mode=opt

Nếu Clingo được cài dưới dạng gói Python, dùng python -m clingo thay lệnh clingo. Trong ví dụ này, giá trị tối ưu là 0. Một lịch đạt giá trị đó xếp CTDL và Kiểm thử vào thứ Hai ở hai phòng khác nhau, Android vào LAB.02 thứ Tư và Phân tích hệ thống vào P.101 cũng thứ Tư.

Clingo có thể in nhiều lịch trong quá trình tối ưu. Hãy đọc điểm tối ưu và trạng thái cuối của lần chạy. Một lịch đã tìm thấy có thể còn điểm phạt. Nếu dừng sớm, hãy lưu riêng lịch tốt nhất tìm được và trạng thái chứng minh tối ưu.

4. Tạo ba biến thể để hiểu mô hình

1. Ép CTDL học thứ Hai và Phân tích hệ thống học thứ Sáu bằng hai ràng buộc. Nếu các dữ liệu khác giữ nguyên, tối ưu là 5.
2. Giảm LAB.02 xuống 19 chỗ. Cả hai lớp thực hành mất ứng viên và bộ giải báo vô nghiệm.
3. Cho phép phòng thực hành phục vụ một lớp lý thuyết khi đủ chỗ. Tách điều kiện phu_hop(LoaiLop,LoaiPhong) thành bảng tương thích thay vì so bằng hai loại. Thử ở sức chứa ban đầu, sau đó tăng LAB.02 lên 35 chỗ. Hãy dự đoán lớp nào có thêm ứng viên trong từng trường hợp.

Khi đem mẫu này sang dữ liệu nhiều cơ sở, hãy xác định rõ quy tắc nào quyết định tính khả thi và quy tắc nào chỉ góp điểm. Một thay đổi nhỏ ở cách tính điểm có thể làm thứ hạng của hai lịch đảo chiều.

Đọc thêm tại Potassco Guide.