KUR Creative

ttm.mvp1 소개

직접 써 보기: https://d2lcrs3mclmhcg.cloudfront.net/

1. 서론

중/고등학교 시간표 스케줄링은 NP-Hard 문제로[1], 복잡하고 다양한 요구사항과 지속적인 변경에 대응해야 하는 까다로운 문제다.

현재 시장의 솔루션들[2]은 생성하는 시간표의 품질이 낮고, 수업이 변경될 때마다 시간표를 수동으로 조정해야 한다. 또한 UI/UX와 편의성이 매우 뒤떨어지며, 시간표 담당 교사는 저열한 솔루션으로 인해 과로에 시달리고 있다. 기존 솔루션의 저품질 시간표는 불공평한 배정으로 교사 간의 갈등을 유발하며, 심지어 학생들의 학업 성취도에도 악영향을 미치고 있다.

교사 시간표 스케줄링 프로그램(이하 ttm)은 다음 세가지 요소를 도입하여, 기존 솔루션의 문제점을 해결한다.

ttm.mvp1은 ttm의 핵심 기능을 검증하는 테크 데모(tech demo)이다.
이 문서는 ttm.mvp1의 기술적 사항에 대해 설명한다.

2. 개괄

resource/ttm.mvp1.구성도.png
그림 1: 전체 시스템 구성도. 원은 소프트웨어 컴포넌트, 직사각형은 데이터.

실행 과정

  1. 유저가 입력 테이블에 입력한 데이터를 UI 상태로 변환
  2. UI 상태를 CP 서버 API 요청(request)으로 변환
  3. 요청을 서버로 전송
  4. 서버는 Constraint Programming을 적용한 조합 최적화를 수행하여 최적의 시간표를 계산
  5. 계산 결과를 응답(response)으로 변환하여 UI에 전달
  6. UI의 출력 테이블에 시간표를 표시

배포

Terraform을 활용하여 AWS에 배포

사용 기술

Frontend:

Backend:

통신: Transit

3. 문제

3.1. 문제 정의: 조합 최적화

resource/교사시간표예시.png
그림 2: 시간표 예시. 시간표의 각 칸은 <반,과목,선생,교시>의 튜플과
이에 대응하는 부울 변수(true=할당/false=미할당)로 표현할 수 있다.

교사 시간표 스케줄링 문제는 조합 최적화(Combinatorial Optimization) 문제로 접근할 수 있다. 시간표에서 수업을 할당하거나/할당하지 않는 "한 칸"은 <반C, 과목S, 선생T, 교시TS>인 튜플로 표현할 수 있다. 각 튜플마다 시간표 할당/미할당을 표시하는 bool 변수를 맵핑한다. 예를 들어 <C=3학년3반, S=과학, T=홍길동, TS=월요일 1교시>에 수업을 할당한다면, <3-3, 국어, 홍길동, mon1>이 가리키는 부울 변수는 true가 된다(그림 2).
반이 nC개, 과목이 nS개, 교사가 nT명, 일주일의 모든 교시(월1, 월2, ...금n) 수가 nTS일 경우, 가능한 모든 시간표의 조합은 2nC x nS x nT x nTS가 된다. 즉, 교사 시간표 스케줄링 문제는 시간복잡도 O(2N)의 NP-hard 문제이며, 전수 조사(Brute Force)로는 해결하기 힘들다.

3.2. 문제: 다양하고 복잡한 입력과 정책

교사 시간표 스케줄링은 NP-hard 문제일 뿐 아니라, 매우 다양한 요구사항과 시간표 정책에 유연하게 대응해야 하는 문제이다. 시간표에 대한 정책은 필수 정책과 권장 정책으로 나눌 수 있다. 필수 정책은 반드시 준수해야 하며, 이를 위반하는 시간표는 사용할 수 없다. 다음은 필수 정책의 예시이다.

반면 필수적이지는 않으나, 생성된 시간표의 품질을 좌우하는 권장 정책들이 있다. 다음은 우선순위가 높은 순으로 나열한 권장 정책 예시이다.

또한 시간표는 지속적으로 변경이 필요하다. 최초로 생성한 "기초 시간표"를 기반으로, 교사의 출장/결근/조퇴 등 일시적인 변경에 대응하는 "변형 시간표"를 생성할 수 있어야 한다. 데이터에 따르면, 교사가 3~40명일 경우, 일반적으로 1~2주에 한번은 변형 시간표를 생성하게 된다. 또한 시간표가 변경될 때마다 영향을 받는 모든 교사에게 양해를 구해야 하므로, 변경은 최소화되어야 한다.

이 모든 요구사항들이 학교, 학기마다 다르게 적용되어 개발 난이도가 상승한다:

4. 제안 해답

기존 솔루션은 필수 정책을 준수하는 시간표는 잘 생성한다. 그러나 권장 정책에 대한 고려가 적어 시간표의 품질이 낮고, 시간표 변경에 대한 지원이 미흡하다. ttm은 권장 정책과 시간표 변경 구현을 설계 단계에서부터 고려하였다.

4.1. 해답: Constraint Programming, OR-Tools CP-SAT의 적용

NP 문제를 해결하고 복잡 다양한 요구사항에 유연하게 대응하기 위해, ttm은 Constraint Programming(CP)을 적용하였다. CP는 문제의 여러 제약(Constraint) 사항을 선언적인(Declarative) 표현으로 작성하여 모델을 생성하고, 모델을 Solver에 입력하면 최적화를 거쳐 제약에 맞는 해답을 생성한다.
CP를 적용하면 최적화 알고리즘을 직접 짜는 것보다 고수준(high-level)의 선언적 코드를 작성할 수 있어 다양한 요구사항에 대응하기 쉬워진다. 또한 CP를 통해 잘 연구되어 있는 조합 최적화 알고리즘을 leverage할 수 있다.

ttm은 오픈소스 CP 라이브러리인 OR-Tools의 CP-SAT를 적용하였다. CP-SAT는 (1) 제약을 설정하여 모든 필수 정책을 만족하는(feasible) 솔루션을 찾을 수 있을 뿐 아니라, (2) 권장 정책 만족도를 목적 함수(objective function)로 정의하고 최대화/최소화하는 최적화 또한 적용할 수 있다. 이 두 기능은 ttm이 해결해야 하는 필수/권장 정책 표현에 알맞다. 필수 정책을 제약으로 표현하여 반드시 만족시키고, 권장 정책은 목적 함수로 표현하여 최적화 문제로 다룰 수 있다.

4.2. 언어: Clojure(Script) 선택

ttm.mvp1의 UI는 JS와 React로 작성했으나, 프론트엔드의 CP 입력 요청 생성(cljs)과 백엔드는 Clojure로 작성했다. Clojure를 사용한 이유는 다음과 같다.

단순함, 유연성, 함수형, 불변성
Clojure는 단순함과 유연성을 고려해 설계된 LISP 계열의 함수형 언어다. 내장 데이터 구조가 불변 타입이며, 코어 라이브러리는 일관된 설계를 바탕으로 선언적 표현을 자연스럽게 활용할 수 있도록 구성되어 있다. 이를 통해 if, for 중심의 절차적 언어보다 더 높은 수준의 추상화를 제공하며, 복잡하고 다양한 요구사항에 유연하게 대응할 수 있다.

에디터와 통합된 REPL 경험과 탐험적 코딩
Clojure는 에디터에서 함수나 표현식을 REPL로 전송하여 실행하고 결과를 확인할 수 있다. 이는 구현의 피드백 루프를 크게 줄여 빠른 프로토타이핑과 탐험적 코딩에 도움이 된다. ttm은 많은 것을 새로 학습하며 진행한 프로젝트기에 이런 요소가 유리했다.

프론트엔드 - 백엔드 코드 공유
Clojure는 JVM 바이트 코드(clj)와 최적화된 JS코드(cljs)로 컴파일할 수 있다. 플랫폼에 종속된 코드가 아니라면, 동일한 코드를 프론트엔드(브라우저)에서도, 백엔드(JVM)에서도 실행할 수 있다. ttm은 CP 계산의 입력 생성을 프론트엔드에서, CP 모델 solve는 백엔드에서 실행하였다.
일반적인 언어라면 프론트엔드와 백엔드에서 수행할 작업을 설계 단계에서 미리 결정한 뒤 구현해야 하나, Clojure는 설계 결정을 뒤로 미룰 수 있어 매우 유리하다. ttm.mvp1은 일단 CP 기능을 구현하고, 결과를 확인한 뒤 OR-Tools에 독립적인 코드를 프론트엔드로 이동하였다(프론트-백 코드 공유는 JS도 가능하나, OR-Tools는 JS 구현을 제공하지 않으므로 ttm에는 적용할 수 없다).

강력한 패러다임의 라이브러리 - Datascript
Clojure는 LISP 계열의 Homoiconicity와 Syntactic macro로 인해, 다른 언어에서는 흔히 볼 수 없는 패러다임을 구현한 라이브러리들이 존재한다. Nikita Prokopov의 Datascript는 Datalog 기반 그래프 쿼리를 적용할 수 있는 in-memory DB이다. ttm.mvp1 작성 과정에서 복잡하고 다양한 집합 연산(특정 속성을 만족하는 부분집합, 교집합, 차집합 등)이 필요했는데, Datascript를 적용하여 깔끔하고 확장성 높은 코드를 작성할 수 있었다.
기존 코드에서 복잡도가 매우 높은 부분을 집합 연산으로 추상화하여 Datascript 쿼리로 표현하자, 동일한 로직을 더욱 고수준의 표현으로 간결하게 작성할 수 있었다. 또한 함수형 패러다임에서 복잡한 ad-hoc 추상화를 형성하는 기존 코드에 비해, Datascript 쿼리를 읽을 수 있는 사람이면 누구나 코드의 로직을 금방 파악할 수 있다.

4.3. UI/UX

기존 솔루션(시간풀이, 압핀, 컴시간)은 데이터 입력이 매우 번거롭고 복잡하며, 길고 장황한 매뉴얼을 읽어야 한다. 배포 면에서, 기존 솔루션들은 모두 데스크탑에 설치해야 하며, 업데이트 또한 직접 다운받아 수동으로 설치해야 한다.

ttm의 UI/UX는 미니멀리즘과 사용성을 중심으로 디자인하였다.

JS 테이블 라이브러리 Trade-off

ttm.mvp1 UI/UX의 핵심은 테이블이다. 스프레드시트와 유사한 사용성을 제공하면서도 자유롭게 커스터마이징하기 위해, 여러 라이브러리를 직접 사용해 보고 평가하는 스파이크를 진행하였다. Table Library Trade-off Matrix
JSpreadsheet는 특히 fill-handle을 지원하며, 일반적인 table 류 태그로 구현하였기에 다양한 커스터마이징이 가능하다. 그 외에 추가적인 의존성이 없는 점, 오랜 기간 유지 보수되며 안정성이 검증된 점 등으로 인해 JSpreadsheet를 선택하게 되었다.

5. 결론

지금까지 교사 시간표 스케줄링 문제를 설명하고, ttm이 문제에 접근하는 방법과 제안하는 해답을 제시하였다. 교사 시간표 스케줄링은 계산적으로 어려운 NP-Hard 문제이며, 다양한 입력과 요구사항에 대응해야 하고, 효과적인 UI/UX를 제시해야 하는 문제이다.
ttm.mvp1은 시간표 스케줄링 문제를 조합 최적화 문제로 정의하였다. Constraint Programming, OR-Tools로 근사해를 도출하며, Clojure, Datascript 등 선언적 패러다임을 적용, 복잡하고 다양한 요구사항에 대응할 수 있도록 유연하게 설계하였다. 핵심 정보 입력 및 확인이 편한 UI를 설계하고 제시하였으며, 웹앱으로 배포하여 편의성과 접근성을 높였다.

  1. resource/A survey of the state-of-the-art of optimisation methodologies in school timetabling problems.pdf ↩︎

  2. 시간풀이, 컴시간, 압핀 ↩︎

kur2402290003Archiveno more posts