OR-Tools Day43

오늘 한 일

시간표 자동 생성 기능 개선

• 자동 배치 성능을 개선했다!
• 기존에는 그냥 OR-Tools의 CP-SAT Solver를 그대로 사용했다
• 그런데 경험적으로 1학년 과목을 미리 수동으로 고정하고 자동 배치를 돌리면 더 나은 결과가 나온다.
• 그 이유는 1학년의 경우 과목의 선택권 없이 모두 같은 과목을 듣기 때문에 어느 과목도 하나의 슬롯에 들어갈 수 없다.
• 따라서 무조건 서로 피해야하고, 이 과목들을 미리 고정해두면, 연산을 줄일 수 있다.

최대 클릭 기반 최적화

• 아 그렇다면, 전체 과목을 분석해서, 어느 두 과목도 한 슬롯에 들어가지 못하는 과목들이 있다면, 그 과목을 우선 배정하면 좋지 않을까?
• 그런 과목들을 모았을 때 가장 큰 집합을 찾아야겠다.
• 아, 이거 그래프에서 최대 클릭 수라고 했던 것 같은데!
• 그래서 최대 클리 수 탐색하는 알고리즘을 찾아서 해당 과목들을 먼저 고정해버리고 자동 배치하도록 하였다.
  

어라 성능이?

• 최대 클릭 수 과목을 고정하고 OR-Tools CP-SAT Solver 를 돌리니까 성능이 더 나빠졌다.
• 왜 그런지 생각해보니, 미리 고정할 때, 어떤 슬롯에 고정하는 지가 되게 중요한 부분인데, 임의로 고정하다보니, Solver가 제 성능을 발휘하지 못했다.
• 그러니까 사전에 고정한 것이 힌트가 아닌 제약이 되어 버린 것.
• 그래서 사전 배치를 필요하면 수정할 수 있게 하고, 초기의 힌트로만 제공하고 Solver를 돌렸다
• 성능이 좋아졌다!
• 사용자가 학생별로 하루에 치르는 최대 과목 수와 하루에 치르는 어려운 과목의 수의 최댓값을 설정한다.(테스트 예시는 둘다 2개 과목)
• 이때, 해당 값을 가지는 학생들의 총합이 최적화해야할 값으로 적을수록 좋다.
• 각각 10번씩 돌렸는데 기존에는 908명, 개선 후에는 851명으로 약 6% 개선되었다.
• 퍼센티지가 엄청나진 않지만, 이미 좋은 툴을 직접 개선할 수 있다는게 신기하다.

앞으로 할 것

• 자동 생성 기능 개선(목적함수 우선순위 가중치 방식 -> 사전식), 뭐가 더 좋을까?
• 프론트엔드 데이터 로드 방식 백엔드 중심 API로 바꾸기
• 시간표 생성 페이지 접속 시 필수 설정 안했으면 메세지 후 리디렉트
• 각종 조건의 출력 데이터 형식 일원화하기
• 듣기평가 커스텀시 시간표 생성에 반영되지 않는 문제 해결하기
• 선택 설정들 기본 값은 빈 값으로 바꾸고, 사용자가 원하면 필수 설정에서 자동 생성하는 기능, 추가로 편집할 수 있는 기능
• 학생 충돌 추가시 2개 말고 n개를 동시에 충돌로 입력할 수 있게 하기
• 특정 과목 불가한 슬롯 설정 기능 추가하기
• 과목 정보 넣으면 반영해서 듣기평가 충돌, 교사 충돌 자동으로 넣을 지, 수동이 편할 지 고민
• 목적 함수 작동 방식 바꾸기(가중치 없이 합 -> 우선 순위 방식)
• 시험 시간표 작성 시 고려 사항 우선순위 사용자 지정 기능 추가하기
• 시험 시간표를 사용자가 원하는대로 수정하는 기능 추가하기
• 시험 장소 배치 시 듣기 평가 한 층 따로 쓰게 하는 옵션
• 시험 감독 자동 배정 기능 추가하기