Sửa lịch đã công bố với ít xáo trộn nhất bằng ASP

1. Tìm lịch mới chưa đủ khi lịch cũ đã được công bố

Một phòng đột xuất không dùng được khiến thời khóa biểu đã công bố phải điều chỉnh. Nếu chỉ tối ưu chất lượng lịch mới như đang lập lịch từ đầu, bộ giải có thể đổi nhiều lớp để giảm vài điểm phạt. Nhưng sinh viên đã sắp xếp việc đi lại, giảng viên đã nhận lịch và phòng đào tạo phải thông báo mọi thay đổi. Bài toán sửa lịch vì thế cần mô tả cả điều kiện khả thi mới lẫn chi phí xáo trộn so với bản tham chiếu.

Ví dụ có ba lớp, hai ca và hai phòng. A và B cùng giảng viên G1; C do G2 phụ trách. Lịch cũ xếp A ở ca 1 phòng R1, B ở ca 2 phòng R1, C ở ca 1 phòng R2. Khi R1 bị đóng ở ca 1, A mất vị trí cũ. B được giữ cố định vì đã có quyết định không được đổi. C có thể điều chỉnh nếu cần. Các ca được coi là rời nhau và cùng độ dài; chưa có di chuyển giữa cơ sở trong mô hình nhỏ này.

2. Đưa lịch cũ vào dữ liệu, không dùng nó như một gợi ý mơ hồ

old(a,1,r1). old(b,2,r1). old(c,1,r2).
closed(1,r1).
fixed(b).

Quan hệ old là ảnh chụp lịch đã chốt. Quan hệ closed mô tả sự cố đang áp dụng, còn fixed là quyết định nghiệp vụ về lớp phải giữ nguyên cả ca và phòng. Không nên thay đổi dữ liệu old trong quá trình thử để làm mức xáo trộn nhỏ hơn; mọi phương án trong cùng lần đánh giá phải được so với cùng một bản tham chiếu.

Một lịch cũ có thể vốn chứa lỗi hoặc không còn khớp danh mục hiện tại. Vì vậy cần kiểm chứng và ghi phiên bản dữ liệu trước khi tối ưu sửa. Với lớp mới chưa có vị trí cũ, phải định nghĩa riêng có tính là một thay đổi hay không. Bài này chỉ xét ba lớp đều đã có đúng một vị trí trong lịch cũ, nhằm tách rõ tác động của sự cố khỏi thay đổi quy mô dữ liệu.

3. Đếm lớp thay đổi khác đếm thuộc tính thay đổi

Ta dùng ba thành phần: số lớp thay vị trí, số lớp đổi ca và số lớp đổi phòng. Một lớp đổi cả ca lẫn phòng chỉ được tính một lần trong thành phần thứ nhất, nhưng góp một lần ở mỗi thành phần sau. Đếm riêng hai loại rồi cộng lại sẽ làm một lớp thay toàn bộ vị trí bị tính thành hai lớp thay đổi, sai ý nghĩa “có bao nhiêu lớp cần được thông báo”.

time_changed(L) :- at(L,S,R), old(L,T,Q), S != T.
room_changed(L) :- at(L,S,R), old(L,T,Q), R != Q.
changed(L) :- time_changed(L).
changed(L) :- room_changed(L).

Chính sách của ví dụ là tối thiểu số lớp đổi trước; nếu hòa mới tối thiểu số lớp đổi ca; nếu vẫn hòa mới tối thiểu số lớp đổi phòng. Ba cấp lần lượt dùng ưu tiên 3, 2 và 1 trong #minimize. Đây là thứ tự từ điển, không phải cộng ba đại lượng với trọng số bằng nhau. Nếu một đơn vị đào tạo coi đổi cơ sở nghiêm trọng hơn đổi ca, cần định nghĩa lại thành phần và ưu tiên theo chính sách đó.

4. Vì sao phải cho phép sửa cả lớp C?

A không thể dùng R1 ở ca 1 vì phòng đóng. Nếu A chuyển sang ca 2, nó trùng giảng viên với B đang cố định ở ca 2, bất kể chọn phòng nào. Vì thế A phải ở ca 1 và chuyển sang R2. Nhưng R2 ca 1 đang có C. C phải rời vị trí cũ. Đến ca 2, R1 đã có B, nên C nhận R2. Chuỗi lập luận cho thấy ít nhất hai lớp A và C phải đổi, dù sự cố ban đầu chỉ tác động trực tiếp đến vị trí của A.

Vector xáo trộn là (2,1,1). Số đầu tiên bằng hai lớp nhận thông báo thay đổi; số thứ hai bằng một lớp đổi ca; số thứ ba bằng một lớp đổi phòng. Nếu đóng băng cả B và C, không còn vị trí hợp lệ cho A nên mô hình vô nghiệm. Kết quả này chứng minh phạm vi sửa hiện tại quá hẹp đối với sự cố và ràng buộc đã cho, không chứng minh mọi cách điều chỉnh nghiệp vụ đều bất khả thi.

5. Chạy tối ưu và đối chiếu tập lịch tốt nhất

Cài python -m pip install "clingo==5.8.3", sau đó chạy python asp_sua_lich_it_xao_tron.py. Chương trình Python gọi ASP rồi vét cạn một miền rất nhỏ gồm các ca–phòng cho ba lớp. Oracle kiểm tra phòng đóng, chống trùng phòng, giảng viên và các lớp bị cố định, sau đó tự tính vector xáo trộn bằng cách so vị trí với lịch cũ.

"""Sửa lịch theo ba cấp ưu tiên và đối chiếu bằng oracle vét cạn."""
from itertools import product
import clingo

PROGRAM = r"""
course(a;b;c). slot(1..2). room(r1;r2).
teacher(a,g1). teacher(b,g1). teacher(c,g2).
old(a,1,r1). old(b,2,r1). old(c,1,r2).
1 { at(L,S,R) : slot(S), room(R) } 1 :- course(L).
:- at(L,S,R), at(M,S,R), L < M.
:- at(L,S,R), at(M,S,Q), teacher(L,G), teacher(M,G), L < M.
:- closed(S,R), at(L,S,R).
:- fixed(L), old(L,S,R), not at(L,S,R).
time_changed(L) :- at(L,S,R), old(L,T,Q), S != T.
room_changed(L) :- at(L,S,R), old(L,T,Q), R != Q.
changed(L) :- time_changed(L).
changed(L) :- room_changed(L).
#minimize { 1@3,L : changed(L); 1@2,L : time_changed(L); 1@1,L : room_changed(L) }.
#show at/3.
"""
OLD = ((1, "r1"), (2, "r1"), (1, "r2"))

def score(schedule):
    times = sum(x[0] != y[0] for x, y in zip(schedule, OLD))
    rooms = sum(x[1] != y[1] for x, y in zip(schedule, OLD))
    return (sum(x != y for x, y in zip(schedule, OLD)), times, rooms)

def solve(extra):
    ctl = clingo.Control(["0", "--opt-mode=optN", "--warn=none"])
    ctl.add("base", [], PROGRAM + extra)
    ctl.ground([("base", [])])
    found = set()
    def collect(model):
        if not model.optimality_proven:
            return
        rows = {str(a.arguments[0]): (a.arguments[1].number, str(a.arguments[2]))
                for a in model.symbols(shown=True)}
        schedule = tuple(rows[l] for l in ("a", "b", "c"))
        assert tuple(model.cost) == score(schedule)
        found.add(schedule)
    result = ctl.solve(on_model=collect)
    assert result.exhausted and not result.interrupted
    return found

def oracle(frozen):
    feasible = []
    positions = list(product((1, 2), ("r1", "r2")))
    for s in product(positions, repeat=3):
        if any(p == (1, "r1") for p in s):
            continue
        if len(set(s)) < 3 or s[0][0] == s[1][0]:
            continue
        if any(s[i] != OLD[i] for i in frozen):
            continue
        feasible.append(s)
    best = min(map(score, feasible), default=None)
    return {s for s in feasible if score(s) == best}

repair = solve("closed(1,r1). fixed(b).")
assert repair == oracle({1}) == {((1, "r2"), (2, "r1"), (2, "r2"))}
assert score(next(iter(repair))) == (2, 1, 1)
assert solve("closed(1,r1). fixed(b). fixed(c).") == oracle({1, 2}) == set()
print("Lịch sửa tối ưu:", sorted(repair))
print("Vector (lớp đổi, lớp đổi ca, lớp đổi phòng): (2, 1, 1)")
print("Đóng băng cả B và C: vô nghiệm; cần xét lại phạm vi được sửa.")

Trong callback, chỉ các mô hình thuộc giai đoạn đã chứng nhận tối ưu của optN được thu lại. Mỗi vector do Clingo báo được đối chiếu với hàm Python tính từ lịch. Tập nghiệm tốt nhất của hai cách phải trùng nhau, không chỉ cùng có một giá trị mục tiêu. Lượt thứ hai cố định thêm C và xác nhận cả ASP lẫn oracle đều không tìm thấy lịch trong miền đã định.

6. Mở rộng vùng sửa theo quan hệ phụ thuộc

Khi hệ thống lớn, có thể bắt đầu từ các lớp trực tiếp bị sự cố, sau đó mở rộng sang những lớp cạnh tranh cùng phòng, ca hoặc giảng viên. Ví dụ cho thấy chỉ cho sửa A là chưa đủ; cần chạm đến C vì vị trí mới bắt buộc của A đang chiếm tài nguyên của C. Tuy vậy, việc mở rộng theo một đồ thị cục bộ chỉ là cách xây miền sửa; muốn bảo đảm không bỏ lỡ phương án tốt hơn, phải nêu rõ điều kiện hoặc kiểm tra bổ sung.

Nên phân biệt lớp cố định tuyệt đối với lớp được phép đổi nhưng chịu phạt cao. Một quyết định đã được duyệt là cứng thì không được âm thầm biến thành phạt mềm để luôn có nghiệm. Nếu người điều phối có quyền cho phép ngoại lệ, hệ thống cần ghi lại quyết định nới đó, phiên bản dữ liệu và lý do. Lịch sau sửa phải qua cùng bộ kiểm chứng ràng buộc cứng như một lịch lập mới.

7. Đánh giá chất lượng lịch và độ ổn định cùng lúc

Trên dữ liệu thực, có thể báo số lớp đổi, số sinh viên bị ảnh hưởng, số giảng viên phải đổi cơ sở, mức chênh điểm chất lượng và thời gian tìm phương án. Cùng hai lớp thay đổi có thể ảnh hưởng rất khác nếu một lớp có 20 sinh viên còn lớp kia có 150. Khi thay đơn vị xáo trộn từ lớp sang sinh viên, không nên so trực tiếp tổng chi phí với kết quả dùng đơn vị cũ.

Bài tập: bỏ cố định B, giữ các điều kiện khác và dự đoán xem vector tối ưu có cải thiện không. Sau đó thêm phòng R3 chỉ dùng được ở ca 1. Xác định trường hợp A có thể được chuyển một mình và giải thích vì sao miền tài nguyên mới làm cận dưới hai lớp thay đổi không còn áp dụng. Cuối cùng, xây ba mức sự cố: đóng một ca, đóng một phòng cả ngày và đổi ca bận của giảng viên; giữ lịch tham chiếu cố định để đo mức ổn định theo từng loại sự cố.

Nguồn về tối ưu nhiều cấp và API: Potassco Guide cho Clingo 5; Clingo 5.8: mô hình và trạng thái giải. Liên hệ Giải nhiều lượt khi dữ liệu thay đổi và Biên Pareto của các phương án lập lịch.