수업 시간표 완전성 검증
수업 시간표의 완전성은 할당 가능한 슬롯의 총 개수와 주간 수업 횟수의 합이 일치함을 의미합니다. 이를 검증하기 위해 두 가지 객체가 필요합니다: 시간표 템플릿과 강의 객체입니다. 템플릿에서 할당 가능한 슬롯 수를 추출하고, 강의 객체에서 해당 과목의 주차별 수업 횟수를 얻습니다. 사용자는 모든 반이 동일한 템플릿을 사용하기를 요구하여 검증 과정이 단순화되었습니다.
우선순위 기반 계층적 배정
우선순위 배정 요구사항은 과목의 중요도와 밀접합니다. 사용자는 수학, 국어, 과학을 가능한 매일 첫 두 교시에 배치하기를 강조했습니다. 전체 시간표 기준으로 수학은 매일 1교시 또는 2교시에 위치하며, 주당 4회의 수학 수업과 1회의 과학 수업이 주 5일에 고르게 분포되어야 합니다. 국어는 주당 7회 수업 중 5회를 1~2교시에 할당하여 수학과 과학의 빈자리를 채웁니다. 우선순위 설계는 수학을 최우선으로 배치하고, 이어서 과학, 국어 순으로 처리하며, 나머지 과목은 이후에 배정합니다.
시간 충돌 없는 배정 알고리즘
시간 충돌 해결은 배정 시스템의 핵심 요구사항입니다. 기존 프로토타입은 다음과 같이 구현되었습니다: 전역 시간표(중첩 리스트)를 생성합니다. 첫 번째 수준은 각 반의 시간표, 두 번째 수준은 반별 요일, 세 번째 수준은 요일별 교시입니다. 강의 정보표와 교사 책임표를 결합하여 (반, 과목명, 교사명, 주차) 속성을 가진 새 테이블을 계산합니다. 이후 4중 반복문을 실행합니다:
- 첫 번째 루프: (교사명, 과목명) 튜플 집합을 순회하며 각 과목의 주차와 담당 반을 확인.
- 두 번째 루프: 각 요일을 순회.
- 세 번째 루프: 각 요일의 교시를 순회.
- 네 번째 루프: 각 반을 순회.
시간 충돌 방지를 위해, 특정 교시가 특정 반에 할당되면 즉시 반 루프를 종료하고 다음 교시로 이동합니다. 즉, 동일 교시에는 하나의 반만 존재할 수 있습니다. 계층적 배정을 위해 첫 번째 루프의 순서는 과목 우선순위에 따라 결정되지만, 일부 보조 과목이 2교시에 배정될 수 있습니다. 비연속 배정을 위해 주차별 최대 배정 횟수를 계산하고, 동일 과목의 일일 배정 횟수를 제한합니다. 이 프로토타입은 시간 충돌과 비연속 배정을 만족하고, 우선순위 배정과 주간 균등 분포를 부분적으로 충족했지만, 전체 완전성 검증은 누락되었습니다.
핵심 알고리즘 코드
def assign_schedule(template, course_data, duties, output_path, show_teacher):
schedules = initialize_empty_schedules(template)
teacher_course_list = get_sorted_teacher_courses(duties, course_data)
day_order = [1, 5, 2, 4, 3] # 균등 분포를 위한 요일 순서
day_queue = Queue()
for day in day_order:
day_queue.put(day)
for teacher_course in teacher_course_list:
teacher, course_name = teacher_course[0]
class_info_list = teacher_course[1]
total_remaining = {class_id: total for class_id, total in class_info_list}
daily_remaining = {class_id: int(total / 5) + 1 for class_id, total in class_info_list}
for _ in range(5):
current_day = day_queue.get()
day_queue.put(current_day)
daily_remaining_copy = daily_remaining.copy()
for period in range(1, 8):
for class_id in daily_remaining_copy.keys():
display_name = course_name if not show_teacher else f"{course_name}({teacher})"
condition_1 = daily_remaining_copy[class_id] > 0
condition_2 = total_remaining[class_id] > 0
if not (condition_1 and condition_2):
continue
condition_3 = schedules[class_id-1][period-1][current_day-1] == ""
condition_4 = (period == 1) or (schedules[class_id-1][period-2][current_day-1] != display_name)
condition_5 = (period == 7) or (schedules[class_id-1][period][current_day-1] != display_name)
if condition_3 and condition_4 and condition_5:
schedules[class_id-1][period-1][current_day-1] = display_name
daily_remaining_copy[class_id] -= 1
total_remaining[class_id] -= 1
break
if sum(daily_remaining_copy.values()) == 0:
break
if sum(total_remaining.values()) == 0:
break
output_file = Path(output_path) / "master_schedule.xls"
save_to_excel(schedules, str(output_file))
알고리즘 발전: 포인터 이동 방식 변경
기존 알고리즘은 시간 충돌과 비연속 배정에 중점을 두었지만, 주간 균등 분포(요구사항 5)를 충분히 처리하지 못했습니다. 새로운 설계에서는 포인터 이동 방식을 변경했습니다:
- 이전 방식: 요일 → 교시 → 반 순서로 이동하며, 시간 충돌을 쉽게 방지했지만 주간 균등 분포는 어려웠습니다.
- 새 방식: 교시 → 요일 → 반 순서로 이동하여 주간 균등 분포를 용이하게 했습니다. 비연속 배정은 마지막 포인터에 조건을 추가하여 처리합니다.
시간 충돌을 해결하기 위해 교사별 시간표(2차원: 요일 × 교시)를 전역 변수로 유지합니다. 배정 시 교사 시간표의 해당 슬롯이 비어 있는지 확인합니다.
개선된 처리 코드
def process_assignments(self):
template = self.get_template()
total_days = len(template[0])
periods_per_day = len(template)
ordered_items = self.get_priority_ordered_courses()
for item in ordered_items:
course, teacher, classes, weekly_count, priority = item
remaining = {c: weekly_count for c in classes}
if teacher not in self.teacher_schedule:
self.teacher_schedule[teacher] = deepcopy(self.get_teacher_slot_template())
for class_id in classes:
if remaining[class_id] <= 0:
continue
if class_id not in self.class_schedule:
self.class_schedule[class_id] = deepcopy(template)
for period in range(periods_per_day):
if remaining[class_id] <= 0:
break
for day in range(total_days):
if remaining[class_id] <= 0:
break
cond1 = self.class_schedule[class_id][period][day] is None
cond2 = (period > 0) and (self.class_schedule[class_id][period-1][day] != course) or (period == 0)
cond3 = self.teacher_schedule[teacher][period][day] == ""
cond4 = (period > 0 and priority < CONTINUOUS_BOUNDARY and
isinstance(self.teacher_schedule[teacher][period-1][day], tuple) and
self.teacher_schedule[teacher][period-1][day][0] != class_id) or True
if cond1 and cond2 and cond3 and cond4:
self.class_schedule[class_id][period][day] = course
self.teacher_schedule[teacher][period][day] = (class_id, course)
remaining[class_id] -= 1
if period == periods_per_day - 1 and day == total_days - 1:
self.unassigned_items.append((course, teacher, class_id, remaining[class_id]))
완전성 검증 구현
완전성 검증은 간단합니다: 템플릿의 할당 가능한 슬롯 수와 강의 정보표의 총 수업 횟수를 비교합니다. 두 값이 같으면 데이터가 완전한 것입니다.
문제점과 해결 방안
테스트 과정에서 두 가지 예외 상황이 발견되었습니다:
- 비연속 배정 위반: 특정 과목이 동일 반에서 연속 교시에 배정되지 않아야 하지만, 다른 빈 슬롯이 없어 배정이 불가능한 경우. 해결책: 우선순위가 낮은 과목(priority < CONTINUOUS_BOUNDARY)에만 이 제약을 적용하고, 높은 우선순위 과목은 제약을 완화합니다. 사용자에게 문제가 발생한 과목의 우선순위를 낮추도록 안내합니다.
- 시간 충돌: 동일 교사가 여러 반에 동시 배정되는 상황. 해결책: 동일 교사가 담당하는 과목의 우선순위를 동일하게 설정하여 충돌 가능성을 줄입니다.
유연한 변경 사항
- 템플릿 변경: 고정 과목(예: 반회) 위치를 조정할 수 있으며, 모든 반에 적용됩니다.
- 주당 수업 횟수 변경: 템플릿 슬롯 수와 일치해야 합니다.
- 과목명 변경: 책임 정보표의 과목명도 동기화해야 합니다.
- 우선순위 변경: 과목 배치 순서에 영향을 주며, 누락을 방지하기 위해 규칙을 따라야 합니다.
- 교사 책임 변경: 자유롭게 변경 가능합니다.
- 일일 수업 횟수 변경: 템플릿 변경과 동일합니다.
출력 형태
사용자 요구에 따라 Word 테이블 형식으로 출력할 수 있습니다. 한 가지 방법은 템플릿을 XML로 저장하고, 과목명 위치를 플레이스홀더로 설정한 후 Jinja2와 같은 템플릿 엔진으로 렌더링하는 것입니다. Excel 출력 모드는 기본적으로 반 시간표와 교사 시간표를 모두 제공하며, 부가 기능으로 교사 시간표 출력 옵션을 포함할 수 있습니다.
사용자 인터페이스는 입력 영역과 출력 영역으로 간단히 유지되며, 교사 시간표 표시 옵션은 제거되었고, 두 가지 시간표가 동시에 출력됩니다. 이제 사용자 문서 작성 단계로 넘어갈 수 있습니다.