OR-Tools Day11

실습 코드

# ------------------ Day11(25.06.17) ------------------

from ortools.sat.python import cp_model
import random

# 데이터 생성
classes = [f'{grade}{section}' for grade in range(1, 6) for section in ['A', 'B']]
teachers = [f'T{i}' for i in range(1, 8)]
subjects = ['Math', 'English', 'Science', 'History', 'Art']
rooms = [f'R{i}' for i in range(1, 50)]
time_slots = [f'{day}-{period}' for day in range(1, 6) for period in range(1, 7)]

# 교사-과목 매칭(랜덤)
teacher_subjects = {t: random.sample(subjects, k=5) for t in teachers}

# 반별 과목별 수업시수(랜덤 예시)
class_subject_requirements = {
    c: {s: random.randint(3, 5) for s in subjects} for c in classes
}

model = cp_model.CpModel()
x = {}

# 변수 선언(불가능한 조합 제외)
for c in classes:
    for t in time_slots:
        for s in subjects:
            for teacher in teachers:
                if s in teacher_subjects[teacher]:
                    for room in rooms:
                        x[c, t, s, teacher, room] = model.NewBoolVar(f'x_{c}_{t}_{s}_{teacher}_{room}')

# 기본 제약조건
for c in classes:
    for t in time_slots:
        model.Add(
            sum(x[c, t, s, teacher, room]
                for s in subjects
                for teacher in teachers if s in teacher_subjects[teacher]
                for room in rooms
                ) <= 1
        )

for c in classes:
    for s in subjects:
        model.Add(
            sum(x[c, t, s, teacher, room]
                for t in time_slots
                for teacher in teachers if s in teacher_subjects[teacher]
                for room in rooms
                ) == class_subject_requirements[c][s]
        )

for t in time_slots:
    for teacher in teachers:
        model.Add(
            sum(x[c, t, s, teacher, room]
                for c in classes
                for s in subjects if s in teacher_subjects[teacher]
                for room in rooms
                ) <= 1
        )

for t in time_slots:
    for room in rooms:
        model.Add(
            sum(x[c, t, s, teacher, room]
                for c in classes
                for s in subjects
                for teacher in teachers if s in teacher_subjects[teacher]
                ) <= 1
        )

# 시간 제한 옵션
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 60
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print('해를 찾았습니다! (일부만 출력)')
    for c in classes[:2]:  # 일부 반만 출력
        print(f'\n{c} 시간표:')
        for t in time_slots[:6]:  # 일부 시간만 출력
            for s in subjects:
                for teacher in teachers:
                    if s in teacher_subjects[teacher]:
                        for room in rooms:
                            if solver.Value(x[c, t, s, teacher, room]):
                                print(f'  {t}: {s} ({teacher}, {room})')
else:
    print('해를 찾지 못했습니다. (시간 초과 또는 infeasible)')

'''
해를 찾았습니다! (일부만 출력)

1A 시간표:
  1-2: Science (T7, R5)
  1-5: Math (T7, R13)

1B 시간표:
  1-1: English (T1, R30)
  1-3: Math (T2, R12)
'''


# 해를 찾지 못했을 경우 어떤 조건이 빡빡한지 확인
print("\n[반별 수업시수 체크]")
for c in classes:
    total_required = sum(class_subject_requirements[c].values())
    print(f"{c}: 필요 수업 {total_required}, 가능한 시간 {len(time_slots)}")
    if total_required > len(time_slots):
        print(f"⚠️ {c}의 수업 요구가 시간보다 많음!")

print("\n[과목별 교사 수 체크]")
for s in subjects:
    teachers_for_s = [t for t in teachers if s in teacher_subjects[t]]
    print(f"{s}: 담당 교사 {teachers_for_s}")
    if len(teachers_for_s) == 0:
        print(f"⚠️ {s}를 가르칠 교사가 없음!")

print("\n[시간별 교실 수 체크]")
max_parallel_classes = max(sum(class_subject_requirements[c][s] for s in subjects) for c in classes)
print(f"가장 많은 수업이 필요한 반의 총 수업: {max_parallel_classes}, 교실 수: {len(rooms)}")


for s in subjects:
    total_required = sum(class_subject_requirements[c][s] for c in classes)
    total_teacher_capacity = len([t for t in teachers if s in teacher_subjects[t]]) * len(time_slots)
    print(f"{s}: 총 요구 {total_required}, 담당 교사 총 가능 {total_teacher_capacity}")
    if total_required > total_teacher_capacity:
        print(f"⚠️ {s} 과목의 수업 요구가 교사 담당 가능 시간보다 많음!")


for t in teachers:
    teacher_load = 0
    for s in teacher_subjects[t]:
        teacher_load += sum(class_subject_requirements[c][s] for c in classes)
    print(f"{t}: 담당해야 할 수업 {teacher_load}, 최대 가능 {len(time_slots)}")
    if teacher_load > len(time_slots):
        print(f"⚠️ {t}의 담당 수업이 너무 많음!")

for s in subjects:
    teachers_for_s = [t for t in teachers if s in teacher_subjects[t]]
    print(f"{s}: 담당 교사 {teachers_for_s}")
    if len(teachers_for_s) == 0:
        print(f"⚠️ {s}를 가르칠 교사가 없음!")