무엇을 정하나요
수업의 주간 시수마다 요일과 교시를 정합니다. 특별실은 그다음에 그리디 방식으로 배정합니다.
최소 실행 예제
from optimaru import school_timetabling as st
problem = {
"calendar": {"periods_per_day": {"0": 4, "1": 4, "2": 4}},
"subjects": [
{"id": "MATH", "name": "Math", "required_room_type": None,
"preferred_periods": [1, 2], "avoided_periods": []},
{"id": "ART", "name": "Art", "required_room_type": None,
"preferred_periods": [], "avoided_periods": []},
],
"teachers": [
{"id": "T1", "name": "Kim", "subject_ids": ["MATH"], "unavailable": [{"day": 0, "period": 1}],
"max_periods_per_week": 20, "max_periods_per_day": 4, "max_consecutive_periods": 3,
"preferred_free_days": [], "homeroom_class_id": None},
{"id": "T2", "name": "Lee", "subject_ids": ["ART"], "unavailable": [],
"max_periods_per_week": 20, "max_periods_per_day": 4, "max_consecutive_periods": 3,
"preferred_free_days": [], "homeroom_class_id": None},
],
"class_groups": [{"id": "C1", "name": "Class 1", "grade": 1, "unavailable": []}],
"rooms": [],
"courses": [
{"id": "C1-MATH", "class_group_id": "C1", "subject_id": "MATH", "teacher_ids": ["T1"],
"periods_per_week": 3, "block_periods": 0, "max_periods_per_day": 1,
"fixed_slots": [], "forbidden_slots": [], "parallel_group": None},
{"id": "C1-ART", "class_group_id": "C1", "subject_id": "ART", "teacher_ids": ["T2"],
"periods_per_week": 2, "block_periods": 2, "max_periods_per_day": 2,
"fixed_slots": [], "forbidden_slots": [], "parallel_group": None},
],
}
timetable = st.solve(problem, time_limit_seconds=2.0, random_seed=42) # 딕셔너리를 돌려줍니다
print(timetable["status"], timetable["objective_value"], timetable["penalties"])
for lesson in timetable["lessons"]:
print(lesson["course_id"], lesson["slot"], lesson["room_id"])
같은 유스케이스를 그림과 실행 결과가 담긴 Jupyter 노트북으로도 볼 수 있습니다. examples/school-timetabling.ipynb ↗
problem["calendar"]
periods_per_day | 요일별 교시 수입니다. {"0": 7, "1": 7, ...} 형식이고, 0이 월요일입니다. |
problem["subjects"][i]
id | 과목 id입니다. |
required_room_type | 필요한 특별실 유형입니다. 학급 교실에서 하면 None입니다. |
preferred_periods | 되도록 배치하고 싶은 교시입니다. |
avoided_periods | 되도록 피하고 싶은 교시입니다. |
problem["teachers"][i]
id | 교사 id입니다. |
unavailable | 수업할 수 없는 시간입니다. {"day": 0, "period": 1} 형식입니다. |
max_periods_per_week | 주간 최대 시수입니다. |
max_periods_per_day | 하루 최대 시수입니다. 없으면 6입니다. |
max_consecutive_periods | 연속 수업 한도입니다. 없으면 4입니다. |
preferred_free_days | 쉬고 싶은 요일입니다. |
problem["class_groups"][i]
id | 학급 id입니다. |
unavailable | 학급이 쓸 수 없는 시간입니다. |
problem["rooms"][i]
id | 교실 id입니다. |
room_type | 교실 유형입니다. required_room_type과 맞춰 봅니다. |
problem["courses"][i]
id | 수업 id입니다. |
class_group_id | 수업을 듣는 학급입니다. |
subject_id | 과목입니다. |
teacher_ids | 담당 교사입니다. 두 명 이상이면 공동 수업입니다. |
periods_per_week | 주간 시수입니다. |
block_periods | 2 이상이면 그만큼의 교시를 주 1회 연속 블록으로 묶습니다. |
max_periods_per_day | 이 수업의 하루 최대 시수입니다. 없으면 1입니다. |
fixed_slots | 고정된 시간입니다. 엔진이 옮기지 않습니다. |
forbidden_slots | 이 수업이 쓸 수 없는 시간입니다. |
parallel_group | 값이 같은 수업은 분반 수업으로, 항상 같은 시간에 열리고 학급 시간표의 한 칸을 차지합니다. |
풀이 파라미터
풀이를 호출할 때 넘기는 값입니다. 시간 제한, 시드, 병렬 수가 여기에 있습니다.
탐색 옵션 전체 (31)
canon.SolverConfig에 값을 넣어 config=로 넘기세요. 기본 canonical 모드에서는 최상위 SolverConfig를 받지 않습니다.
돌아오는 결과
학교 시간표는 딕셔너리를 받아 딕셔너리를 돌려줍니다. 변환할 모델이 없습니다. 결정 내용은 lessons에 있습니다.
timetable
status | 필수 위반이 없으면 FEASIBLE, 남아 있으면 INFEASIBLE입니다. |
lessons | 배치된 교시마다 하나씩 있는 목록입니다. |
objective_value | penalties에 가중치를 곱해 더한 값입니다. |
penalties | 제약 이름별 선호 위반 횟수입니다. |
notes | INFEASIBLE 결과에 남은 위반을 설명합니다. |
wall_time_seconds | 풀이에 걸린 시간입니다. |
best_objective_bound | 항상 None입니다. 로컬 서치는 하한을 증명하지 않습니다. |
timetable["lessons"][i]
course_id | 수업입니다. |
class_group_id | 학급입니다. |
subject_id | 과목입니다. |
teacher_ids | 교사입니다. |
slot | 정해진 시간입니다. {"day": 0, "period": 1} 형식입니다. |
room_id | 특별실이 필요한 수업에만 값이 있습니다. 나머지는 None이며 학급 교실을 뜻합니다. |
제약
optimaru.school_timetabling.constraints에서 클래스를 가져와 UnassignedLessonsCost()처럼 호출해서 넘깁니다. 넘긴 제약만 점수에 들어가고, 아무것도 넘기지 않으면 기본 제약을 씁니다. 목록에 같은 제약을 여러 번 넣을 수 있으며, 넣은 것마다 따로 점수에 들어갑니다. 제약마다 다음 파라미터를 받습니다.
선호 가중치만 바꾸려면 weights={"teacher_gap_cost": 40}을, 제약을 고르거나 빼거나 수준을 바꾸려면 constraints=Assembly()...를 넘기세요. Assembly는 이름마다 하나만 두므로, 이미 있는 이름을 add()하면 그 항목을 바꿉니다. 일반 constraints=[...] 목록에는 같은 이름을 여러 번 넣을 수 있고, 넣은 것마다 따로 점수에 들어갑니다. constraints= 없이 풀면 빠른 경로를 그대로 쓰고 병렬 탐색도 됩니다. 넘기면 탐색 하나로만 풉니다.
위의 최소 실행 예제에 이어서 실행합니다.
from optimaru.school_timetabling.constraints import Assembly
# 17개 전체에서 시작해 하나를 바꾸고 하나를 뺍니다
custom = st.solve(
problem, time_limit_seconds=2.0, random_seed=42,
constraints=Assembly().add("teacher_gap_cost", weight=40).drop("teacher_workday_cost"),
)
print(custom["status"], custom["penalties"])
제약 사용법 →
기존 해에서 시작하기
최신 버전이 필요합니다. pip install -U optimaru로 올려 주세요.
이 유스케이스는 문제가 딕셔너리라서 with_initial_solution이 없습니다. 이전 시간표를 solve의 initial_solution=으로 넘기세요.
위의 최소 실행 예제에 이어서 실행합니다.
better = st.solve(problem, time_limit_seconds=2.0, random_seed=42, initial_solution=timetable)
print(better["status"], better["objective_value"])
- 수업은
course_id로 맞춥니다. - 완전한 해를 넣으면 구성 단계를 건너뛰고 그 해에서 바로 탐색을 시작합니다. 일부만 넣으면 넣은 부분은 그대로 두고, 빠진 교시만 새로 구성합니다.
time_limit_seconds=0을 주면 바로 멈추므로 완전한 해는 넣은 그대로 돌아옵니다. step_count_limit = 0은 제한이 없다는 뜻이므로, 바로 멈추려면 시간 제한을 쓰세요.room_id는 결과에서 다시 계산하므로 무시합니다.fixed_slots는 그대로 유지하고, 그 밖의 시간은 수업의 남은 시수 안에서 맞아야 합니다. 그래서 고정 수업을 옮긴 완전한 해는 받지 않습니다.- 모르는 수업, 같은 시간에 두 번 나온 수업, 남은 시수보다 많은 시간, 서로 다른 시간에 놓인 분반은
ValueError를 냅니다. - 수업이 쓸 수 없는 시간을 넣어도 받아들이고 필수 위반으로 채점합니다. 그래서
INFEASIBLE 결과에서도 이어서 풀 수 있습니다.
예외와 제한
- 로컬 서치는 최적이나 불가능을 증명하지 못합니다.
INFEASIBLE은 시간 제한까지 필수 위반이 남았다는 뜻이지, 시간표가 존재하지 않는다는 뜻이 아닙니다. - 달력은 16교시까지, 요일 번호는 8 미만까지입니다. 더 크면
ValueError가 납니다. INFEASIBLE 대신 채울 수 없는 교시를 비워 두려면 첫 번째 제약을 선호로 낮추세요. Assembly().add("unassigned_lessons_cost", level="soft", weight=10_000)처럼 씁니다. 빈 교시 하나의 비용이 그 가중치이므로, 다른 선호 제약을 모두 더한 값보다 크게 두세요.- 이 설정에는
stop_at_first_feasible을 함께 쓰지 마세요. 수업을 모두 뺀 시간표도 필수 0점이라 탐색이 거기서 멈춥니다.
직접 해 보기