OR-Tools Day8

실습 코드

# ------------------ Day8(25.06.15) ------------------
'''
간단한 시간표 문제를 해결하기 위한 예시 데이터
'''

# 교사 목록
teachers = ['T1', 'T2', 'T3']

# 과목 목록
subjects = ['Math', 'English', 'Science']

# 학급 목록
classes = ['1A', '1B']

# 교실 목록
rooms = ['R1', 'R2']

# 시간 슬롯(교시)
time_slots = [1, 2, 3, 4, 5]

# 각 반의 시수
class_subject_requirements = {
    '1A': {'Math': 2, 'English': 2, 'Science': 1},
    '1B': {'Math': 2, 'English': 1, 'Science': 2}
}

# 교사별 담당 과목
teacher_subjects = {
    'T1': ['Math'],
    'T2': ['English'],
    'T3': ['Science']
}

from ortools.sat.python import cp_model

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 teacher in teachers:
    for t in time_slots:
        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 room in rooms:
    for t in time_slots:
        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()
status = solver.Solve(model)

if status == cp_model.FEASIBLE or status == cp_model.OPTIMAL:
    for c in classes:
        print(f'\n{c} 시간표:')
        for t in time_slots:
            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('해를 찾을 수 없습니다.')

'''
1A 시간표:
   1교시: Science (T3, R1)
   2교시: Math (T1, R2)
   3교시: Math (T1, R2)
   4교시: English (T2, R1)
   5교시: English (T2, R2)

1B 시간표:
   1교시: Math (T1, R2)
   2교시: English (T2, R1)
   3교시: Science (T3, R1)
   4교시: Science (T3, R2)
   5교시: Math (T1, R1)
'''