OR-Tools Day12

• 아직은 실제 상황보다 간소화되어 있지만, 그래도 좀 그럴듯?해지고 있다.

실습 코드

# ------------------ Day12(25.06.19) ------------------
from ortools.sat.python import cp_model

# 데이터
classes = ['1A', '1B', '2A', '2B']
subjects = ['Math', 'English', 'Science', 'Korean']
exam_slots = ['Day1-AM', 'Day1-PM', 'Day2-AM', 'Day2-PM']
rooms = ['R1', 'R2', 'R3', 'R4']
teachers = [f'T{i}' for i in range(10)]

model = cp_model.CpModel()

# 시험 배정 변수
exam_x = {}
for c in classes:
    for s in subjects:
        for t in exam_slots:
            for r in rooms:
                exam_x[c, s, t, r] = model.NewBoolVar(f'exam_{c}_{s}_{t}_{r}')

# 감독 배정 변수
supervise_y = {}
for teacher in teachers:
    for t in exam_slots:
        for r in rooms:
            supervise_y[teacher, t, r] = model.NewBoolVar(f'supervise_{teacher}_{t}_{r}')

# 각 반-과목 시험은 정확히 한 번만 배정
for c in classes:
    for s in subjects:
        model.Add(sum(exam_x[c, s, t, r] for t in exam_slots for r in rooms) == 1)

# 한 교실, 한 시간에 한 반만 시험
for r in rooms:
    for t in exam_slots:
        model.Add(sum(exam_x[c, s, t, r] for c in classes for s in subjects) <= 1)

# 한 교실, 한 시간에 감독 교사 2명
for r in rooms:
    for t in exam_slots:
        model.Add(sum(supervise_y[teacher, t, r] for teacher in teachers) == 2)

# 한 교사는 같은 시간에 한 교실만 감독
for teacher in teachers:
    for t in exam_slots:
        model.Add(sum(supervise_y[teacher, t, r] for r in rooms) <= 1)

# 시험이 있는 곳에만 감독 배정
for t in exam_slots:
    for r in rooms:
        model.Add(2 * sum(exam_x[c, s, t, r] for c in classes for s in subjects) >= sum(supervise_y[teacher, t, r] for teacher in teachers))

# 감독 교사별 감독 횟수 균형 목적함수(최대- 최소 최소화)
total_supervise = [sum(supervise_y[teacher, t, r] for t in exam_slots for r in rooms) for teacher in teachers]
max_supervise = model.NewIntVar(0, len(exam_slots)*len(rooms), 'max_supervise')
min_supervise = model.NewIntVar(0, len(exam_slots)*len(rooms), 'min_supervise')
model.AddMaxEquality(max_supervise, total_supervise)
model.AddMinEquality(min_supervise, total_supervise)
model.Minimize(max_supervise - min_supervise)

# 풀이
solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print('시험 시간표 및 감독 배정 결과:')
    for t in exam_slots:
        for r in rooms:
            for c in classes:
                for s in subjects:
                    if solver.Value(exam_x[c, s, t, r]):
                        print(f'{t} {r}: {c} {s} 시험')
            teacher_in_room = [teacher for teacher in teachers if solver.Value(supervise_y[teacher, t, r])]
            if teacher_in_room:
                print(f'   감독: {", ".join(teacher_in_room)}')
    # === 각 교사별 감독 횟수 출력 ===
    print("\n[교사별 감독 횟수]")
    for teacher in teachers:
        count = sum(
            solver.Value(supervise_y[teacher, t, r])
            for t in exam_slots
            for r in rooms
        )
        print(f"{teacher}: {count}회")
else:
    print('해를 찾지 못했습니다.')

'''
시험 시간표 및 감독 배정 결과:
Day1-AM R1: 1B Science 시험
   감독: T0, T7
Day1-AM R2: 2A Science 시험
   감독: T2, T6
Day1-AM R3: 2A English 시험
   감독: T5, T9
Day1-AM R4: 1A English 시험
   감독: T1, T8
Day1-PM R1: 2B Science 시험
   감독: T3, T4
Day1-PM R2: 2A Korean 시험
   감독: T1, T6
Day1-PM R3: 2A Math 시험
   감독: T8, T9
Day1-PM R4: 1A Math 시험
   감독: T2, T7
Day2-AM R1: 1B Korean 시험
   감독: T0, T2
Day2-AM R2: 1A Science 시험
   감독: T1, T4
Day2-AM R3: 2B Korean 시험
   감독: T3, T6
Day2-AM R4: 2B English 시험
   감독: T5, T9
Day2-PM R1: 1B Math 시험
   감독: T3, T7
Day2-PM R2: 1A Korean 시험
   감독: T1, T8
Day2-PM R3: 2B Math 시험
   감독: T4, T5
Day2-PM R4: 1B English 시험
   감독: T0, T9

[교사별 감독 횟수]
T0: 3회
T1: 4회
T2: 3회
T3: 3회
T4: 3회
T5: 3회
T6: 3회
T7: 3회
T8: 3회
T9: 4회
'''