코넬대, 강의 시간 기반 시험 시간표를 MIP로 대체해 일정 충돌 해소

코넬대의 기말고사는 시험 그룹을 첫 강의 시간에 묶는 정적 표에 따라 편성되었다. 약 30개의 수업 시간과 22개의 시험 슬롯만 있어서, 학생들은 일상적으로 기말고사가 겹치는 상황을 겪었고, 교수진은 동시에 일정이 몰린 학생들을 위해 대체 시험을 출제해야 했다.

ORIE의 교수진과 학생들은 대학 등록처와 협력해 정수계획법 프레임워크를 구축했다. 이 프레임워크는 다단계 Group-then-Sequence 모델과 반복적 Layer-Cake 휴리스틱을 결합해, 다양한 매개변수 선택 아래에서 여러 일정 변형을 생성한다.

이 모델은 직접적 충돌과 연속 시험뿐 아니라 고차원 충돌, 즉 24시간 내에 두 개를 초과하는 시험을 치르거나 네 개의 연속 슬롯에 걸쳐 시험을 치르는 학생들까지 처리한다. 등록처는 일정의 편안함과 앞쪽 집중(front-loading), 슬롯 제외 사이의 균형을 맞추며 파레토식 옵션 중에서 선택한다.

최적화 프로그램이 일정을 짜고, 등록처가 상충 관계를 선택한다

MIP는 충돌 구조를 명시적으로 드러낸다. 스프레드시트와 조회 표가 보지 못하는 고차원 사례까지 포함해서다.

매 학기 수천 명의 학생과 수백 개의 시험이 상호작용한다. 그 규모에서 학생 편의를 균형 있게 맞출 수 있는 것은 최적화 프로그램뿐이며, 수작업으로 하는 것은 애초에 실행 가능하지 않았다.

일정 변형을 통해 등록처를 의사결정 과정에 계속 참여시킴으로써, 최적화는 블랙박스에서 기관이 신뢰하는 의사결정 지원 도구로 바뀐다.

정적 조회 표가 더 이상 데이터에 맞지 않을 때는 표를 최적화 프로그램으로 대체하되, 상충 관계 비교를 통해 일정을 선택하는 일은 사람이 맡도록 하라.

코넬대는 2024년 이후 다섯 학기 동안 기말고사 일정 편성에 이 프레임워크를 사용해 왔으며, 논문은 행정 시간과 일정 편의 측면에서 기존 강의 시간 기반 접근법보다 우수한 점을 기록하고 있다. 이 작업과 함께 오픈소스 MIP 생성기가 제공된다.