제약프로그래밍 기반 개인화된 강의 시간표 최적화

1. 서 론

대학의 강의 시간표 편성은 교과목, 강의실, 시간, 교수 등 다양한 요소들을 고려해야 하는 복잡한 의사결정 과정이다. 각 강의는 교육과정 운영에 필요한 필수 조건(Hard Constraints; HCs)과 선호 조건(Soft Constraints; SCs)을 가지고 있으며, 이러한 조건들은 시간표 편성 시 반드시 고려되어야 한다. 예를 들어, 동일한 강의시간에 동일한 강의실에서는 반드시 한 개의 강의만이 배정되어야 하는 제약은 필수 조건이고, 특정 교수가 특정 강의실을 사용하고자 한다는 것은 선호 조건이다. 따라서 대학 내 각 학과는 매 학기 강의 시간표를 구성할 때 이러한 다양한 조건을 종합적으로 고려하여 최적의 시간표를 구성해야 한다. 이와 같이 여러 제약 조건이 수반된 대학의 강의 시간표를 구성하는 문제는 University Course Timetabling Problem (UCTP)으로 정의되며, 이는 여러 목표와 제약조건을 동시에 고려해야 하는 대표적인 조합 최적화 및 스케줄링 문제로 연구되어 왔다(Musa and Oyelakin, 2024).

UCTP 연구에서는 여러 상충되는 목표를 동시에 고려해야 하는 특성으로 인해, 주로 다목적 최적화 문제(Multi-objective Optimization Problem; MOP) 접근방식이 활용되어 왔다(Abdullah et al., 2010; Almeida et al., 2022). MOP는 일반적으로 하나의 해가 아닌 여러 개의 트레이드오프 해(Pareto Optimal Solutions)를 생성하며, 각 해는 서로 다른 목적 값 조합을 가지게 된다. 한편, MOP의 하위 개념으로 멀티모달 다목적 최적화 문제(Multimodal Multi-objective Optimization Problem; MMOP)가 존재한다(Li et al., 2023). MMOP는 동일한 목적 함수 값(Pareto 등가해)을 가지면서도 구조적으로 상이한 다양한 해를 찾는 특수한 문제로, 단순히 성능이 유사한 해를 찾는 것을 넘어 의미 있는 대안적 조합을 제시해야 하는 문제에 적합하다. 이는 일반적인 MOP와 달리, 해의 다양성(Diversity) 및 구조적 차별성이 중요한 평가 기준이 되며, 의사결정자에게 유사한 성능을 가진 다양한 선택지를 제공할 수 있다는 점에서 실용적 가치가 크다.

최근 교육 환경이 급격히 변화하면서 UCTP의 범위가 크게 확장되고 있다. 특히 온라인 강의의 도입, 융합 교육의 확산, 그리고 학습자 중심 교육의 강화로 인해 전통적인 강의실-교수 배정 중심의 UCTP는 다차원적으로 접근해야만 한다. 여기서 주목할 만한 변화는 학생들의 다양한 학습 수요와 선호도가 시간표 편성의 주요 고려 사항으로 부상하고 있다는 점이다. 이는 단순히 물리적 자원의 효율적 배분을 넘어, 학습 효과의 최적화와 학생 만족도 향상이라는 새로운 목표를 시간표 편성 과정에 포함해야 함을 의미한다. 이에 본 연구에서는 이러한 여러 요소들을 고려하여 학생 별 강의 시간표를 추천할 수 있는 프레임워크를 제공하고자 한다.

한편 대학생의 입장에서 자신의 한 학기 시간표를 구성하는 것은 중요한 문제이다. Larabi-Marie-Sainte et al.(2021)에 따르면, 고등 교육 기관의 학생 시간표는 학생의 성적 및 결석율에 유의한 영향을 미친다. 또한 Cordis and Pierce(2017)은 대학생의 강의 시간표 구성에 따라 학업 성취도에 유의한 영향을 미치며, 특정 시간대에 성취도가 높은 과목들이 존재한다고 밝혔다. 따라서 대학생들은 원활한 대학 생활을 수행하기 위하여 시간표를 구성할 때 개인의 조건과 개설된 강의들의 특성, 조건 및 제약 사항들을 잘 비교하고 타협하여 최적의 시간표를 구성해야 한다.

기존 연구에서 다뤄온 UCTP는 수업 별 시간, 강의실, 교수 배정을 결정하는 교육기관 중심의 문제로, 시간표 구성의 상위 단계에 해당한다. 반면 본 연구에서 다루는 University Student Timetabling Problem(USTP)은 이미 결정된 수업 시간, 강의실, 교수 정보를 고정된 파라미터로 받아, 그 범위 내에서 학생 개인의 선호도와 제약조건을 반영하여 최적의 수업 조합을 선택하는 문제이다. 즉, USTP는 UCTP로부터 결정된 결과를 입력으로 받아 학생 개별 관점에서 시간표를 구성하는 하위 문제로 정의되며, 문제의 대상과 의사결정 단위에서 분명한 차이를 가진다.

그러나 기존 UCTP 중심의 연구들은 대학 또는 학과 전체의 시간표를 최적화하는 데 집중되어 있으며, 학생 개별 시간표를 구성하는 USTP에 대한 연구는 아직 충분히 탐구되지 않았다. 이에 본 연구는 학생의 개별 조건과 선호를 반영하여 수업 선택을 지원할 수 있는 강의 시간표 추천 모델을 제안하고자 한다. 특히 본 연구에서는 실제 서비스에 적용 가능한 실용적인 최적화 모델 개발을 목표로 한다.

이러한 개인의 최적 강의 시간표를 구성하는 문제(USTP)는 MOP에 해당한다고 볼 수 있다. 시간표 구성 시 고려해야 할 요소는 강의 평점, 이동시간, 수강 학점, 과목 선호도 등 다양하며, 학생 개개인이 각 요소에 부여하는 중요도(가중치) 역시 상이하기 때문이다. 더 나아가 USTP는 MMOP의 특성도 함께 지니는데, 동일한 성적 수준과 이동 효율성을 만족하는 여러 개의 시간표가 존재할 수 있으며, 이들 시간표는 수강 과목의 조합이나 배치 구조 측면에서 서로 다른 해들로 구성될 수 있기 때문이다. 하나의 목적 값에 대해 여러 형태의 의미 있는 해 즉, 여러 가지 시간표를 제공하는 것은 의사결정자인 학생에게 다양한 대안을 제공할 수 있다는 점에서 실용적 가치가 높다. 이러한 특성으로 인해 USTP는 단일 해를 찾는 것이 아닌, 구조적으로 상이한 다수의 양질의 해를 탐색하고 제공할 수 있는 최적화 접근법이 요구된다는 것을 의미한다. 그러나 이러한 다양한 조건을 모두 반영하여 가능한 모든 시간표 조합을 탐색하는 것은 계산 비용이 매우 크고, 그로 인해 실시간 서비스 환경에서는 현실적인 한계가 존재한다.

이러한 USTP 문제를 실제 서비스에 탑재가 가능한 형태로 해결하기 위해서는 두 가지 핵심적인 요구사항이 존재한다. 첫째, 서비스 응답 시간이 실용적인 수준이어야 한다. 학생들이 실시간으로 시간표를 탐색하고 조정하는 과정에서, 과도한 대기 시간은 서비스 사용성을 크게 저하시킬 수 있기 때문이다. 둘째, 단일 대안이 아닌 복수의 대안을 제시할 수 있어야 한다. 학생들의 선호도와 제약조건은 매우 다양하며 때로는 명시적으로 표현하기 어려운 요소들을 포함하기 때문에 여러 개의 실행 가능한 시간표 옵션을 제공하는 것이 중요하다. 이러한 실용적 요구사항들을 고려한 시간표 결정 연구는 현재까지 매우 제한적이다.

본 연구는 위와 같은 실용적 요구사항들을 반영하여 USTP를 해결하기 위해 제약 프로그래밍(Constraint Programming; CP)을 활용한 모델을 제안한다. 이 모델은 짧은 응답시간 내에 다양한 대안을 제시할 수 있도록 설계되었다. 실제로 이러한 모델의 타당성을 평가하기 위해서 A 대학교의 수강편람 데이터를 활용하여 제약을 만족하는 근사 최적해 집합(Near-Optimal Solution Set)을 도출하고자 한다. 이후, 기존 UCTP 선행연구에서 제안한 모델과의 민감도 분석 및 탐색 시간에 대한 성능을 분석하고자 한다. 특히 탐색 시간은 본 연구에서 제안한 모델의 상용화를 염두에 두고 분석한다. 탐색 시간은 서비스 로딩시간과 직결되고 이는 기존 서비스 이용자가 기존 서비스 대신 다른 서비스를 받으러 떠나버리는 비율인 서비스 전환율(Conversion Rate)에 강한 영향을 미치기 때문이다(Stadnik and Nowak, 2018). 본 연구 결과는 대학생의 강의 시간표 구성 결과에 대한 만족도 향상과 함께 학업 성취도 향상에 유의한 영향을 미칠 수 있을 것으로 판단된다. 더 나아가 다른 조합 최적화 및 스케줄링 문제를 해결함에 있어 중요한 참고 연구가 될 수 있을 것으로 기대한다.

본 논문의 구성은 우선 제2장에서 기존 UCTP 관련 선행연구를 고찰하고 제3장에서는 해결하고자 하는 문제의 정의 및 해결 방법론을 제시한다. 제4장에서는 연구 결과를 논의한 후 제5장에서 최종 결론을 제시한다.

2. 선행연구

시간표 작성 문제(Timetabling Problem)는 제한된 시간과 자원 내에서 일정한 활동을 충돌 없이 배치하는 문제로, 다양한 응용 분야에 걸쳐 나타나는 일반적인 조합 최적화 문제이다. 이 문제는 보통 활동 간의 동시 배정 금지, 자원의 중복 사용 방지, 그리고 특정 시간에 배정할 수 없는 경우의 불가능 시간대 등의 HC를 만족하는 해를 찾는 것을 기본 목표로 한다. 또한, 활동 간 간격 조절, 특정 시간대 선호 반영, 균형 있는 자원 분배 등과 같은 SC를 고려하여, 제약 위반을 최소화하거나 만족도를 극대화하는 목적 함수를 설정하기도 한다.

이러한 일반적인 시간표 작성 문제와 달리, 대학 강의 시간표 편성 문제(UCTP)는 몇 가지 고유한 구조적 특수성을 지닌다. 우선, 과목 간에 공통 수강생이 존재하기 때문에 강의 간의 충돌 관계가 보다 복잡하게 얽혀 있으며, 강의의 길이 또한 일정하지 않고 다양한 시간 길이로 구성될 수 있다. 또한 강의실은 수용 인원과 용도의 적합성에 따라 배정이 제한되며, 인기 과목의 경우 여러 개의 분반으로 나뉘어 운영되기 때문에, 각 분반에 학생을 적절히 배정하는 문제까지 함께 고려되어야 한다. 그에 따라 UCTP는 모델링 복잡도와 현실 대응력이 높아야하기 때문에, 이론적인 측면과 실용적인 측면 모두에서 매우 중요한 연구 주제로 다루어지고 있다. 이에 대한 종합적인 연구의 흐름은 Schaerf(1999), Lewis(2008)의 연구를 참고할 수 있다. 특히 Schaerf(1999)는 자동화된 시간표 최적화 문제를 NP-Complete으로 분류하고, 정확한 해법보다는 메타휴리스틱을 기반으로 한 근사 기법이 주요하고, HC 뿐만 아니라 SC를 동시에 고려해야 하기 때문에 보다 복잡한 모델링이 필요하다고 하였다. 또한 최근에는 교육 환경이 학생 중심으로 빠르게 변화함에 따라, 대학 차원의 강의 시간표뿐만 아니라 학생 개개인의 선호와 학업 성취를 최대화하려는 USTP에 대한 관심이 높아지고 있다. 하지만 현재까지 학생 개인의 시간표 최적화 문제에 대한 연구 즉, USTP를 독립적인 문제로 정의하고 이를 체계적으로 다루는 연구는 전무한 실정이다. 본 연구에서는 이러한 USTP에 대한 최적화 모델을 제안하기 위해 기존 UCTP 선행연구에서 시도된 여러 가지 접근 방식과 방법론을 검토한다.

선행연구는 크게 두 가지 흐름으로 구분할 수 있다. 첫째, 사용한 방법론에 따라 연구를 구분할 수 있다. 예를 들어, Rappos et al.(2022)은 International Timetabling Competition(ITC) 2019에서 제공된 임의 데이터 세트를 활용해 혼합 정수 계획법(Mixed Integer Programming; MIP)에 기반한 2-Phase Matheuristics 모델을 제안했다. 이들은 Phase 1에서 MIP를 활용해 제약조건을 충족하는 초기해를 생성하고, Phase 2에서 메타휴리스틱 중 하나인 Local Search Method(LSM)를 통해 페널티(목적함수)를 최소화하는 해를 도출했다. 이 과정에서 Fix-and-Optimize 전략을 사용하여 탐색 공간을 효율적으로 축소함으로써 복잡한 제약조건이 존재함에도 우수한 해를 구했다. 또한 Aycan and Ayav(2009)는 대학 학과별 시간표 문제 해결을 위해 Simulated Annealing(SA)을 활용하는 방법론을 제안했는데, 이 연구에서는 CP를 통해 모든 필수 조건(HC)을 만족하는 초기해를 찾은 뒤, SA와 다양한 LSM 기법으로 선호 조건(SC)에 대한 페널티를 줄이는 최적해를 탐색했다.

둘째, 사용한 데이터의 종류에 따라 연구를 구분할 수 있다. Rappos et al.(2022)은 ITC 2019에서 제공된 임의 데이터 세트를 활용한 반면, Algethami and Laesanklang(2021)은 Taif University의 UCTP를 다목적 혼합 정수 계획법으로 해결하면서, 교수별 수업 부담과 성별에 따른 캠퍼스 분리 등 실제적인 제약조건을 반영해 높은 수준의 시간표 만족도를 달성했다. Moallemi and Patange(2023)은 Columbia Business School에서 COVID-19 상황을 고려해 MIP 기반 Hybrid Scheduling 모델을 설계함으로써, 사회적 거리두기와 학생들의 네트워킹 기회를 균형 있게 보장하는 시간표를 2,500명 이상의 학생에게 제공했다. Ogris et al.(2016)은 슬로베니아 초등학교를 대상으로 진화적 알고리즘 기반의 iUrnik 시스템을 개발해, 학생과 교사의 다양한 요구사항을 자동으로 반영해주는 시간표 생성 시스템을 구현했다.

추가적으로, UCTP는 선호 조건들을 최대한 만족하는 시간표를 출력하는 것을 목표로 해 다목적 최적화를 수행해야 하는 문제이기 때문에, 다목적 최적화를 구현한 방법에 따라서도 선행 연구를 구분할 수 있다. Algethami and Laesanklang(2021)의 경우, 다목적 혼합 정수 계획법을 통해 목적식 간 선형 결합으로 단일 목적식을 구현함으로써 다목적 최적화를 수행했고, Rappos et al.(2022)과 Aycan and Ayav(2009)는 휴리스틱 기반 모델을 제안하였는데, 모두 필수 조건을 충족하는 초기해를 각각 MIP와 CP로 찾은 후, LSM, SA와 같은 휴리스틱 기법을 혼합하여 선호조건을 충족하는 해를 찾되, 선호 조건을 단일 목적식과 같이 표현하여 페널티를 줄이는 방식을 활용했다. 반면, Burke et al.(2010)은 계층적 최적화를 통해, 초기에는 필수 조건과 시간 관련 선호 조건만을 고려해 부분해를 빠르게 생성한 후, 부분해를 활용해 나머지 선호 조건들을 고려한 최적해를 탐색하는 방법을 통해 다목적 최적화를 수행하였다.

이처럼 기존 연구는 혁신적인 모델이나 알고리즘을 적용해 UCTP의 복잡한 요구사항을 해결한다는 점에서 의의가 크지만 교육기관 중심의 UCTP 해결이 대부분을 차지해 학생 개인의 시간표 최적화 문제(USTP)에 직접적으로 적용하기 어려운 점이 존재한다. 또한 특정 대학의 고유한 물리적 제약이나 실용적 요구사항(즉각적인 수정, 빠른 응답 시간 등)을 반영하는 연구 역시 제한적이다. 따라서 학생 중심의 USTP를 다루면서도 실제 서비스로의 구현 가능성과 다양한 대안 제시에 대한 요구를 충족시키는 모델 개발이 필요하다.

한편, 본 연구에서는 다양한 제약조건을 효율적으로 다루기 위해 제약프로그래밍(CP)을 활용한다. CP는 ‘무엇(What)을 만족해야 하는가’에 초점을 맞춰 제약을 기술하는 방식으로, ‘어떻게(How) 해결할 것인가’를 수학적으로 복잡하게 정의할 필요 없이 문제를 모델링할 수 있도록 한다(Hooker, 2018). 이러한 선언적 모델링 방식은, 선형 수식과 추가적인 Cutting Planes 기법을 필요로 하는 MIP와 같은 명령적 접근에 비해 훨씬 더 간단하고 유연하며, 다양한 문제에 손쉽게 확장 가능한 장점이 있다(Van Hoeve and Katriel, 2006; Heipcke, 1999).

CP 모델에서 사용되는 Interval variable은 활동의 시작 시점, 종료 시점, 기간(Duration)을 포함하는 시간 구간을 변수로 정의할 수 있도록 하며, 이는 MIP의 단순한 이진 변수와는 달리 시간 혹은 구간으로 표현할 수 있는 정보를 자연스럽게 표현하고 제약조건과 연동 가능한 강점이 있다. 또한, CP는 전역 제약(Global Constraint; GC)이라 불리는 고수준 제약 표현을 지원하며, 이는 기존 수식으로 표현하기에 복잡한 제약을 간단한 제약 한 줄로 모델에 통합할 수 있게 해준다. 예를 들어, AllDifferent는 여러 변수의 값이 서로 달라야 함을 보장하며, PresenceOf는 Optional variable의 존재 여부를 모델링할 때 사용된다. 이때 Optional variable은 존재 여부가 결정되어야 하는 변수로, Optional interval variable과 Optional integer variable 모두 해당될 수 있다. NoOverlap은 여러 활동 간의 시간 겹침을 방지하는 제약을 의미한다. CP 관련 제약, 모델링 방법에 대한 상세한 내용은 Bockmayr and Hooker(2005)를 참고한다.

또한 CP는 제약 전파 알고리즘(Constraint Propagation Algorithm)을 통해 변수가 가질 수 있는 도메인을 동적으로 축소함으로써 탐색 공간을 크게 줄인다(Bockmayr and Hooker, 2005). 이는 모든 제약조건에 대해 연쇄적으로 위반 여부를 확인하면서, 변수 간 도메인 충돌을 제거해주는 방식이다. 반면 MIP에서는 Branch & Bound 기법을 사용할 수 있으나, Branch-ing 되는 경우의 수가 기하적으로 증가하여 시간이 많이 소요될 수 있다. 또한 MIP의 해법으로 Branch & Cut 기법을 통해 선형 완화(Linear Relaxation) 후 상·하한(Upper Bound and Lower Bounds)을 설정하고, 충돌되는 제약을 추가(Cutting Planes)함으로써 탐색 공간을 좁혀나갈 수도 있다. 그러나 이 과정에서 별도의 Cutting Planes 계산이 필요하며, 제약조건을 새롭게 수정하거나 추가할 경우 다시금 복잡한 과정을 거쳐야 해 이 또한 많은 시간이 소요될 수 있다. 현장에서 문제 요구사항이 빈번히 변동되는 상황에서는 이러한 절차와 시간 손해가 상당한 부담으로 작용한다(Garcia de la Banda, 2023).

CP는 제약조건을 선언적 형태로 구현하고 선형 완화나 Cutting Planes 추가 계산이 불필요하기 때문에 실제 적용에서 상대적으로 용이하다. 이러한 CP의 장점을 바탕으로 본 연구는 USTP 해결을 위한 최적화 모델을 제안한다. 제안 모델은 제한된 시간 내에 고품질의 개인 시간표를 도출해야 하는 서비스 환경에서, 대학의 물리적 제약과 학생들의 다양한 요구사항을 반영하면서도 신속하고 유연한 대응이 가능하도록 설계되었다.

3. 문제 정의

본 연구에서 제안하는 모델은 대학교 재학생의 개인 맞춤형 강의 시간표의 효과적 구성을 목표로 한다. 본 연구에서 다루는 USTP문제는 단순히 강의를 시간 슬롯에 배치하는 것을 넘어, 강의평, 전공학점 등 학업적 특성과 강의실 간 거리로 대표되는 물리적 제약을 모두 고려해야 하는 복잡한 최적화 문제이다. 여기서 슬롯이라 함은, 강의 시간표를 30분 단위로 나누어 구분한 개념을 지칭한다. A 대학교의 강의 특성상 다양한 강의 시간이 존재하여, 30분 단위의 슬롯 개념을 도입하였다. 본 모델은 모든 학과 학생에게 공통으로 적용 가능한 수강 요건과 제약조건을 기반으로 설계되었으며, 실험에서는 A대학교 산업공학과 재학생을 예시로 활용하여 모델의 적용 가능성을 검토하였다. 구체적으로 다음과 같은 특성들을 고려한다:

• 1) 물리적(지리적) 특성: 캠퍼스 부지의 넓은 면적과 10°~15°의 경사로 이루어진 A 대학교의 캠퍼스 특성상, 강의실 간 이동시간이 상당히 상이하다. 예를 들어, 특정 두 수업간에는 21분이 소요되어(웹 지도 최단 거리 기준), 각 강의 사이의 쉬는 시간(15분) 내 이동이 현실적으로 불가능한 경우가 존재한다.
• 2) 학업적 특성: A 대학교의 강의는 크게 전공과목과 교양과목으로 분류된다. 또한 모든 과목은 1학점, 1.5학점, 2학점, 3학점으로 구성되며, 수업 운영 방식은 과목의 특성과 교육과정에 따라 주 1회 또는 주 2회로 이루어진다. 전공과목에 대해서 전공필수과목과 전공선택과목이 존재하고, 교양과목에 있어서는 교양필수과목과 교양선택과목이 있으며, 그밖에 일반선택과목이 존재한다. 교양과목은 1~13영역으로 각각의 강의내용 특성에 따라 분류된다(Appendix 1 참조). A 대학의 경우, 한 학기 최대 수강학점이 24학점이고, 학과 및 단과대학 별로 상이한 세부 이수 조건들이 존재하며, 특히 산업공학과의 경우 전공 필수와 선택 과목들의 구분이 명확하다.

따라서 본 연구에서는 모든 필수 제약조건을 준수하면서 개인의 선호도를 최대한 반영하는 해를 '양질의 해'로 정의한다. 앞서 언급한 바와 같이 본 모델을 통해 여러 개의 시간표를 추천하고자 하며, 이 시간표들은 모두 양질의 해에서 추출할 수 있도록 프레임워크를 구성한다.

3.2 수식화

본 연구에서는 HC를 모두 준수하며, SC 측면에서 개인의 선호가 최대한 반영되는 측면에서 최적에 근사한 시간표 해집합을 출력하는 것을 목표로 한다. HC는 반드시 충족해야 하는 제약 조건들로, ‘지정된 슬롯에는 오직 한 개의 강의만 배정되어야 한다’, ‘같은 과목의 다른 분반을 동시에 수강할 수 없다’ 등이 존재한다. HC1~HC11의 조건에 대한 표현은 차례대로 식 (C1)~식 (C11)과 같다. 변수 및 파라미터에 대한 표기법은 <Table 1>과 같다. 여기서 Index i는 과목코드, j는 분반(Section)을 의미하며 k는 과목의 영역을 뜻한다. 추가적으로 s_empty는 시간표를 구성하고자 하는 학생이 희망하는 공강 슬롯을 입력받아 사용하는 파라미터, t_input는 시간표를 구성하고자 하는 학생이 희망하는 강의 간 최대 이동시간이다. 이때 희망 강의간 최대 이동시간이라함은, ‘연강이 존재할 경우, 학생이 최대 몇 분까지 이동시간으로 사용할 수 있는가’를 의미한다.

Table 1.

Notation

한편, 시간표 상의 실제 배정은 CP 모델의 인터벌 변수(Interval Variable)를 통해 표현되며, 각 강의는 수업 횟수에 따라 최대 두 개의 인터벌 변수(IV_ijkl1, IV_ijkl2)로 모델링 된다. 이는 모든 강의가 주 2회 강의라는 전제를 두는 것이 아니라, 강의가 주 1회~2회로 운영되는 A 대학의 유연한 강의 편성 구조를 반영한 설계다. 본 모델을 수행한 결과, 최종적으로 선택되는 강의들을 시간표 상 배치된 결과에 대한 예시는 <Figure 1>과 같다. 예를 들어, <Figure 1>의 A, E, G, H, I 강의의 경우, 주 1회 수업을 하는 강의로, 인터벌 변수가 IV_ijkl1 한 개가 존재하고, 나머지 B, C, D, F 강의의 경우 주 2회 수업을 하는 강의로 인터벌 변수가 두 개(IV_ijkl1, IV_ijkl2)가 존재한다. 각 인터벌 변수는 강의 선택 여부를 나타내는 이진 변수 X_ijkl와 연계되어 존재 여부가 결정된다. 따라서 실제 수업이 주 1회인 경우, IV_ijkl1만 존재하더라도 유효하다.

Figure 1.

Timetable Example

본 연구에서 다루는 문제상황은 MOP(Multi-Objective Optimization Problem)라고 정의할 수 있다. 일반적인 MOP에서는 보통 가중합(Weighted-sum)을 활용한 최적화를 수행한다. 그런데 MOP에서는 각 목적함수에 가중치를 부여하지 않고도 우선순위를 기반으로 최적화를 수행할 수 있다. CP는 이러한 우선순위 기반의 최적화, 즉 계층적 최적화(Lexicographic Optimization)를 자연스럽게 표현할 수 있는 프레임워크를 제공한다. 본 연구에서는 SC1(평균 선호도 점수 극대화)을 최우선적으로 최적화한 후, 그 결괏값을 만족하는 범위 내에서 SC2(총 이동시간 최소화)에 대한 추가 최적화를 수행하였다. 이와 같은 CP 기반의 계층적 최적화 과정은 <Figure 2>와 같이 Pseudo Code의 형태로 요약될 수 있다.

$\[ Maximize \frac{\sum _{i,j,k,l} X_{ijkl}\times s{c}_{ij}}{\sum _{i,j,k,l} X_{ijkl}} \]$

(O1)

$\[ Minimize \sum _{\left(ijkl\right),\left(i^{\text{'}}{j}^{\text{'}}{k}^{\text{'}}{l}^{\text{'}}\right)} t_{b_1{b}_2}\cdot X_{ijkl}\cdot X_{i^{\text{'}}{j}^{\text{'}}{k}^{\text{'}}{l}^{\text{'}}} \]$

(O2)

Figure 2.

Pseudo Code for Lexicographic Optimization

전술하였듯, 본 연구에서 제안하는 모델은 CP를 활용한다. CP를 활용할 경우, GC를 사용해 특정 제약을 선언적으로 처리할 수 있다. 따라서 식 (C2)에 해당하는 HC2를 GC를 활용한 제약 조건으로 표현한다. GC를 활용하면 해당 제약에 대해 noOverlap 제약조건을 활용할 수 있다. 나머지 HC들의 경우, 일반적인 수리식의 형태로 표현한다. 이때 HC11의 경우, 연속 강의 간 이동시간이 사용자 선호 시간 이내여야 하는 제약으로, 전술하였듯, 강의간 이동시간은 연강일 때만 계산을 수행한다. 따라서 식 (C11)과 같이 두 강의$$ \left(X_{ijkl},X_{i^{\text{'}}{j}^{\text{'}}{k}^{\text{'}}{l}^{\text{'}}}\right)$$가 연속하여 수강할 수 있는 시간표 조합에 해당하고, 두 강의의 이동시간 t_b1b2가 사용자로부터 입력받은 개별 강의간 이동시간 하한 t_input을 초과하는 경우, 두 강의를 동시에 수강하는 것을 금지한 조건부 제약으로 표현한다.

$\[ \sum _{i,j,k,l} \left(X_{ijkl}\times c{r}_{ij}\right)\le 24 \]$

(C1)

$\[ \begin{array}{c} presence Of\left(I{V}_{ijkl1}\right)=X_{ijkl}, presence Of\left(I{V}_{ijkl2}\right)\\ =X_{ijkl}no Overlap \left(I{V}_{ijkl1},I{V}_{ijkl2}\right)\end{array} \]$

(C2)

$\[ \sum _{\left(i,j_1,k_1,l_1\right),\left(i,j_2,k_2,l_2\right)s.t{j}_1\ne j_2} X_{i{j}_1{k}_1{l}_1}+X_{i{j}_2{k}_2{l}_2}\le 1\forall i\in I \]$

(C3)

$\[ \sum _{i,j,l} X_{ijkl}\le 1\forall k\in \{\mathrm{1,2},\mathrm{3,4},\mathrm{5,6},7\} \]$

(C4)

$\[ \sum _{i,j,l} X_{ijkl}\le 2\forall k=8 \]$

(C5)

$\[ X_{ijkl}=0\left(I{V}_{ijkl1},I{V}_{ijkl2}\right)\in s_{empty } \]$

(C6)

$\[ \sum _{j,k,l} X_{ijkl}\ge 1\forall i\in I_{must} \]$

(C7)

$\[ \sum _{i,j,l} X_{ijkl}\ge 1\forall k\in K_{sel} \]$

(C8)

$\[ \sum _{i,j,l} X_{ijkl}=0\forall k\in K_{unsel } \]$

(C9)

$\[ \sum _{i,j,k,l} X_{ijkl}\times s{c}_{ij}\ge s{c}_{lb}\sum _{i,j,k,l} X_{ijkl} \]$

(C10)

$\[ \begin{array}{c}{X}_{ijkl}+X_{i^{\text{'}}{j}^{\text{'}}{k}^{\text{'}}{l}^{\text{'}}}\le 1\forall (i,j,k,l),\left(i^{\text{'}},j^{\text{'}},k^{\text{'}},l^{\text{'}}\right)\\ s.t. t_{b_1{b}_2}>t_{input}\end{array} \]$

(C11)

SC는 반드시 충족해야 하는 조건들은 아니지만, 최대한 충족시키면 좋은 제약 조건들이다. 본 연구에서는 SC에 해당하는 제약 조건에는 SC1에 해당하는 ‘강의 선호도 점수의 평균이 최대한 높아야 한다’와 SC2에 해당하는 ‘강의 간 이동시간이 최대한 짧아야 한다’가 존재한다.

CP에서는 SC를 일반적인 수학적 프로그래밍에서 사용하는 목적함수와 유사하게 활용할 수 있다. 본 연구에서 제안한 SC는 수식 (O1)~(O2)과 같이 표현된다. 식 (O1)는 선택된 강의들의 평균 선호도 점수를 극대화하는 형태로, 분수식 구조를 가지며 전통적인 MP에서는 비선형 목적함수로 인해 직접적인 모델링이 어렵다. 그러나 CP에서는 해당 값을 직접 목적함수로 설정하는 대신, 1단계에서 최적값을 계산한 뒤, 이를 2단계에서 제약조건으로 반영하는 방식으로 간접적인 구현이 가능하다. 또한 식 (O2)에서 이동시간은 시간표상 연속 수강이 가능한 강의쌍$$ (i,j,k,l),\left(i^{\text{'}},j^{\text{'}},k^{\text{'}},l^{\text{'}}\right)$$ 중에서 이동시간 t_b1b2가 정의된 경우에 한해 계산된다. 이때 $$ b_1=l,b_2=l^{\text{'}}$$은 각각 강의쌍의 현재 강의동을 의미한다.

4. 연구결과

본 연구는 A 대학교 재학생의 개인 선호도가 반영된 최적 강의 시간표를 도출하기 위해 CP를 활용한 모델을 제안한다. 본 연구는 제안한 방법론의 타당성을 검증하고, 기존 UCTP 연구에서 제시된 모델과 비교 분석을 수행한다. 이를 위해 본 연구에서는 제안 모델의 민감도 분석을 통해 CP 모델에서 도출한 해를 평가하고, 기존 연구와 출력 시간 및 성능을 비교하였다. 실험은 Apple M1 Pro, 16GB RAM, Mac OS 환경에서 IBM ILOG CPLEX 22.1.1 및 DOcplex를 활용하여 Python Ver.3.10.0 을 이용해 구현하였다.

4.2 모델 성능 평가 결과

<Figure 3>은 모델 간 성능 비교를 위해 본 논문에서의 제안한 CP 모델과 비교 대상인 MIP모델의 목적함수 가중치를 조정하며 실시한 민감도 분석 결과를 보여준다. MIP 모델은 UCTP 관련 선행 연구에서 자주 활용되기 때문에 비교 대상으로 채택하였다. MIP 모델의 제약 조건과 목적함수는 <Appendix 2>에 상세히 기술하였다. 본 논문에서 제안하는 모델은 각 SC에 우선순위를 부여하여 순차적 최적화를 수행하는 반면, MIP 모델은 강의평점과 이동거리를 고려한 다목적함수를 강의평점과 이동거리를 가중치로 결합한 단일 목적함수로 표현하여 사용한다. 이러한 차이로 인해 MIP 모델은 가중치 설정에 따른 성능 변동성이 존재한다. MIP 모델에서는 강의평점과 이동거리에 대한 각각의 가중치의 합이 1.0이 되도록 설정하였다. 그리고 이동 시간 상한값의 변화에 따른 최적해를 비교하기 위해 이동 시간 상한값을 0분부터 5분 간격으로 두어 변경하며 분석하였다. 또한, 현실적으로 학생들이 구성할 법한 시간표를 출력하였을 때의 수치적 결과를 평가하기 위하여 매일 오후 12시까지 공강을 배치하고, 교양필수와 전공필수에 해당하는 9, 13 영역을 필수 수강하도록 공통적으로 적용하였다. 이동시간 분석의 명확성을 위해 이동시간이 0인 조합은 제외하였으며, 각 분석에서 단일 최적해만 도출하도록 설정하였다.

Figure 3.

Pareto Frontier for Solution Space (Sensitivity Analysis)

분석 결과 <Figure 3>에서 확인할 수 있듯이 본 연구에서 제안한 CP를 활용한 모델은 이동시간 상한값과 무관하게 총 이동시간 10분 이내, 강의 선호도 점수 평균 4.475 이상의 우수한 해를 안정적으로 도출하였다. 반면 MIP 모델은 강의 선호도 점수 가중치가 0.9 이상일 때 평균 선호도 점수와 이동시간이 동반 상승하는 경향을 보였다. 이동시간 가중치 0.1인 경우 모든 해의 총 이동시간은 0분이었으며, 선호도 점수 평균은 4.38(1개), 4.43(4개)으로 분포하였다. 이동시간 가중치가 0.3 이상에서는 이동시간 0분, 선호도 점수 평균 4.39의 단일해만 도출되어, 0.1 이상의 이동시간 가중치가 목적 값에 지배적 영향을 미치는 것으로 나타났다.

또한 파레토 프론티어 분석 결과, 제안된 모델은 평균 강의 선호도 점수와 총 이동 시간 모든 측면에서 MIP 모델을 상회하는 성능을 보였다. 특히 가중치 설정 없이도 MIP의 극단적 가중치 설정(0.0:1.0, 0.9:0.1)보다 우수한 결과를 도출하였다. 이는 제안된 CP 기반의 가중치 없는 다목적 최적화 방식이 해당 문제에 더욱 적합함을 시사한다.

본 연구에서 제안한 모델은 대학생 최적 강의 시간표를 다수 제공하며, 각 시간표의 품질과 일관성이 중요하다. 이는 학생들이 해당 모델을 통해서 유의미한 선택지를 제공받고 과목의 다양성 또한 확보하기 위함이다. 따라서 제안한 모델이 제공하는 해 품질의 일관성과 다양성 측면을 검증하기 위한 실험이 필요하다. 본 연구에서는 3가지 시나리오를 설정해 해당 시나리오에 적합한 시간표를 추출하되, 동일하지 않은 5개의 시간표를 추출하도록 설정 후 실험하였다(<Table 2>~<Table 4> 참조). 이때, A 대학교 산업공학과 1학년 학생 20명의 시간표를 확인해 본 결과, 공통적으로 수강하는 과목들로 시나리오를 구성했다(20학점, 금요일 공강, 월요일 ~ 목요일 8:00 ~ 12:00 공강, 13, 9 영역 해당 과목 필수 수강).

Table 2.

Preference Scenario

첫 번째 시나리오(Case 1)는 산업공학과 1학년 학생의 일반적인 시간표 구성 상황을 반영한 것으로, 강의 평점은 4.0점 이상, 강의 간 최대 이동 시간은 10분 이하로 설정하였다. 두 번째 시나리오(Case 2)는 강의 평점 기준을 4.5점 이상으로 상향하여 선호도를 강조한 반면, 이동 시간은 최대 30분까지 허용하여 시간적 제약을 완화한 설정이다. 반대로 세 번째 시나리오(Case 3)는 이동 시간을 0분으로 제한하여 연속 강의 간 물리적 이동이 불가능한 경우를 가정하고, 대신 강의 평점 기준은 비교적 낮은 3.0점 이상으로 설정하였다. 여기서 이동 시간 0분이라는 조건은 ‘강의 간 이동이 전혀 없어야 함’을 의미하며, 이는 연강 혹은 동일 건물 내 강의실 배치와 같은 상황을 반영한 것이다. 총 3개의 시나리오에 대해 <Table 2>와 같이 정리한다.

정리하자면, <Table 3>은 A 대학교 산업공학과 1학년 재학생들의 일반적인 시간표 작성 시나리오(Case 1)에 대한 실험 결과이다. <Table 4>은 강의 평점을 극단적으로 높게 설정하는 대신, 이동시간은 고려하지 않는 시나리오(Case 2)에 대한 실험 결과이다. <Table 5>는 반대로 이동시간을 0분으로 극단적으로 설정하고, 강의 평점은 비교적 낮게 3.0점으로 설정한 시나리오(Case 3)에 대한 실험 결과이다. 3개의 시나리오에 대해서 각각 출력된 5개의 해 모두 본 연구에서 제시한 제약 조건을 모두 준수하는 것을 확인했다.

Table 3.

Objective Values of Multi Solutions using CP(Scenario 1)

Table 4.

Objective Values of Multi Solutions using CP(Scenario 2)

Table 5.

Objective Values of Multi Solutions using CP(Scenario 3)

각 시나리오에 대해 본 연구에서는 우선적으로 주어진 조건(SC1: 선호도 하한, SC2: 이동 시간 상한)을 만족하는 해를 도출한 뒤, 이 중에서 5개의 유효 해를 대표적으로 선택하여 제시하였다. 모든 해는 본 연구에서 정의한 필수 조건(HC)을 완벽히 충족하며, 계층적 최적화 방식에 따라 SC1의 조건을 만족한 해들 중 SC2(이동 시간)가 최소가 되도록 순차적으로 탐색된 결과이다. 따라서 각 Table에 제시된 Solutions 1-5는 동일한 문제에 대한 단일 최적해가 아니라, 동일한 조건 하에서 파레토 최적성을 갖는 복수의 근사 최적해이며, 학생들에게 다양한 선택지를 제공하는 것을 목적으로 한다. 이러한 방식은 시간표 다양성과 실용성 측면에서 높은 활용 가능성을 보장한다.

<Figure 4>는 제안된 모델을 통해 출력된 시간표를 실제 수강 시간표 형식으로 시각화한 결과이다. 이때 세로축은 시간대에 따라 정의한 슬롯을 의미한다. 이는 <Table 2>의 Case 1 시나리오에 대한 출력물로, 강의명은 알파벳으로 대체 표기하였다. 이때 알파벳 A, B, C에 해당하는 과목들은 모두 반드시 수강하여야 한다고 입력 조건에 입력한 교양필수와 전공필수에 해당하는 과목들이다. 나머지 알파벳에 해당하는 과목들은 최적화 과정에서 배치된 과목들이다. 모델 개발 과정에서 단순히 한두 개의 강의만 상이한 유사 시간표가 아닌, 실질적으로 차별화된 다수의 강의 조합을 제공하는 것을 목표로 하였다. 이는 수강 시간표 구성 시 학생들에게 다양한 대안을 제시하기 위함이다. <Figure 4>에서 확인할 수 있듯이, 제안된 모델은 필수 수강 과목을 제외한 나머지 강의 구성이 모두 상이한 5개의 시간표를 제공함으로써, CP 모델의 실효성을 입증하였다.

Figure 4.

Graphical Timetable of Case 1. Solution 1~5

<Table 6>은 새롭게 제안된 CP 모델과 기존 연구의 MIP, Constraint Programming-Local Search(CP-LS), Constraint Programming - Simulated Annealing(CP-SA) 모델 간의 탐색시간, 출력하는 해의 강의 선호도 평점, 이동시간을 비교한 실험 결과를 제시한다. USTP를 명확하게 다루는 선행연구는 희소했기 때문에 비교 모델에 있어 UCTP 혹은 Timetabling 관련 선행연구에서 제시한 모델들을 활용하였다. CP-LS 모델의 경우, Rappos et al.(2022)에서 제시한 MIP로 초기해를 탐색한 후, LS를 활용하는 2-Phase Matheuristics를 기반으로 모델을 구현하되, MIP대신 CP를 활용하였다. 이는 추가적으로 비교하는 모델이 CP-SA 모델로, Aycan and Ayav(2009)은 대학 학과별 시간표 문제 해결을 위해 CP로 초기해를 탐색한 후, SA를 활용하는 방법인데, 2-Phase Heuristic 기법들의 초기해 생성 방식을 통일하는 것이 분석에 있어 주요하다고 판단했기 때문이다. 두 선행 연구 모두 HC를 만족하는 초기해를 탐색한 후, SC를 최대한 충족하는 해를 Heuristic 탐색하는 방법을 활용하였다. CP를 제외한 각 모델의 파라미터는 <Table 6>에 명시된 바와 같이, 선호도 점수 평균과 이동 시간의 Elbow Point를 기준으로 설정되었다. 모든 실험은 <Table 6>의 입력 조건에 따른 동일한 개인 선호도를 적용하여 수행되었다. 본 연구에서 제안한 모델은 CP Optimizer의 복수해 반복 탐색이 가능하여 복수의 해를 탐색한다. 그러나 본 모델과의 비교에 사용된 방법론들은 모두 단일 목적 함수 기반(MIP) 또는 순차적 반복 탐색 구조(CP-LS, CP-SA)에 따라 설계되어있다. 그에 따라 본 논문에서 제안한 바와 같은 여러 개의 유효해를 출력하는 것에는 구조적 한계가 존재한다. 특히 MIP의 경우 동일 해를 제외하는 제약을 추가할 수 있으나, 각 해별로 매우 복잡한 비선형 Cardinality Constraint를 구성해야 하는 경우의 수가 발생할 수도 있다. 이는 본 모델이 실제 현장에서 수정이 필요한 경우 비전문가에게 수정의 어려움을 초래할 수 있으며, 메타휴리스틱을 사용한 방법론들은 탐색 경로의 무작위성으로 인해 다양한 해를 출력할 경우 각 해의 제약 충족 여부나 품질의 보장이 어렵다. 또한 기존의 해를 탐색하지 못하도록 제약을 추가한 후 다시 LS, SA의 Iteration을 수행해야하는 시간적 비효율이 발생한다. 그에 따라 비교 모델들은 복수의 해를 출력해서 결과를 분석하는 것은 연구 목적에 부합하지 않는다고 판단하였다. 따라서 모델 간 비교에 있어서는 단일해를 출력하도록 해 성능을 비교했다.

Table 6.

Experimental Results

실험 결과, 네 가지 모델 모두 11개의 HC를 완벽히 충족하는 해를 도출하였으며, 각각의 파라미터 설정에 기반한 최적해를 성공적으로 산출하였다. 이동시간 측면에서는 CP, MIP, CP-LS 모델이 모두 0분으로 이동이 불필요한 최적의 강의 조합을 도출했다. CP-SA 모델의 경우 8분의 이동시간이 발생하여 타 모델 대비 다소 비효율적이었으나 모든 제약 조건을 준수하는 유효한 해를 제시하였다.

실제 현장 적용을 목표로 개발된 이 모델은 온라인 서비스 환경에서의 실용성에 중점을 두었기에 총 실행 시간을 모델 평가의 핵심 지표로 설정하였다.

<Table 6>에서 볼 수 있듯이 동일 조건의 문제 해결에 대해 본 연구에서 제안된 모델은 145.47초의 총 실행 시간을 보여 타 알고리즘 대비 약 70초에서 400초(약 33% ~ 74%)가 단축되는 것을 확인할 수 있었다. MIP 기반 모델의 경우 563.31초의 총 실행 시간을 보여 제안 모델 대비 4배 이상의 시간이 소요되었다. 이러한 차이는 해 탐색 방식의 근본적 차이에서 기인한다. CP는 제약 전파를 통해 도메인을 축소하여 탐색 공간을 효율적으로 줄이는 반면, MIP는 선형 완화, 상·하한 설정, Cutting Planes 추가 등의 과정에서 탐색 공간을 축소한다. 이 과정에서 요구되는 모델의 축소 및 변환 작업이 MIP의 탐색 시간을 증가시키는 주요 요인으로 분석된다.

실제로 <Table 3> ~ <Table 5>에 제시된 개인 선호도 입력 정보를 수작업으로 검토할 경우, 이론적으로 시간표 상에 배치할 수 있는 강의들에 대한 조합들을 모두 계산하면 약 14,910개의 경우의 수(시간표 조합)를 모두 확인해야 하므로 이 과정에서 굉장히 많은 시간이 소요될 수 있으나 개발된 모델은 약 140초 내외에 최적해를 도출한다. 이는 <Table 6>에서 볼 수 있듯 선행 연구 모델들에 비해 최소 1.5배에서 최대 약 4배 이상 향상된 성능이다.

또한, <Table 6>에 제시된 일부 모델 간 평균 선호도 점수 차이는 소수점 두 자리 이내로, 예를 들어 CP-LS와 제안 모델 간의 점수 차이는 4.580점과 4.534점으로 0.046점에 불과하다. 이는 수치상으로는 우열이 존재할 수 있으나 실제 시간표 구성을 직접 비교해 보았을 때 학생 입장에서 체감할 수 있는 학업적 이점이나 선호의 차이는 사실상 미비한 수준이다. 더 나아가, 동일한 점수라 하더라도 시간표의 구체적 배치 구조는 학생 개인의 취향과 학습 성향에 따라 선호도가 달라질 수 있다. 따라서 단일 점수만으로 시간표의 품질을 평가하는 것은 한계가 있으며 다양한 해를 제공할 수 있는 제안 모델의 접근은 실용성과 선택권 측면에서 더욱 효과적인 해결책이 될 수 있다.

또한 새롭게 제안된 모델은 CP의 제약 전파 알고리즘과 GC관련 내장 알고리즘을 효과적으로 활용하여 개별 제약 조건에 대한 불필요한 알고리즘을 최소화하고 효율적인 설계를 구현했다. 그 결과, 기존 연구들보다 탐색 시간을 대폭 단축하면서도 모든 제약 조건을 충족하고 강의 선호도 평균이 4.5를 상회하는 높은 강의 평점을 가진 강의들로 구성된 최적해를 도출할 수 있었다. 이러한 결과는 본 연구에서 제안한 CP 기반 모델이 실제 현장 적용이라는 연구 목표에 가장 부합하는 방법론임을 입증한다.

5. 결 론

대학생의 학업 성취도에 직접적인 영향을 미치는 강의 시간표 조합 작업은 매우 중요하나, 모든 경우의 수를 검토하여 최적의 시간표를 도출하는 것은 현실적으로 어려운 과제이다. 본 연구는 이러한 한계점을 해소하고자 대학생을 대상으로 개인 선호도가 반영된 최적 강의 시간표를 도출하는 CP 모델을 제안하였다. 제안된 모델은 모든 제약조건을 충족하는 해를 성공적으로 도출했으며, 기존 선행 연구에서 제시한 방법론과의 성능 비교를 통해 모델의 적합성 및 타당성을 검증하였다. 이 과정에서 A 대학교 수강편람 데이터를 특정 학과 재학생이 수강 가능한 범위로 한정하여 활용하였다.

민감도 분석 결과, 제안된 CP 모델은 MIP 기반 모델과 비교하여 파라미터 변동에 관계 없이 일관된 품질의 해를 도출하는 것으로 나타났다. 특히, 다수의 시간표 조합을 제공하면서도 모든 해가 제약 조건을 준수하며, 목표함수 값의 편차가 크지 않은 것을 확인하였다. 본 연구는 실제 현장에서의 서비스 구현을 고려하여 수행되었으며, CP의 선언적 제약 처리 방식과 GC의 수정 기능을 통해 현장 전문가가 직관적으로 이해하고 수정할 수 있는 모델을 구현하였다. 특히, 기존 방법론 대비 1.5~4배 정도 빠른 총 실행 시간과 다중목적함수 적용 시 별도의 가중치 설정이 불필요하다는 점에서 온라인 서비스화를 위한 실용성을 입증하였다.

본 연구의 학술적 의의는 기존 UCTP 연구와 차별화되는 USTP의 CP 기반 최적화 모델을 제안했다는 점에 있다. 또한, 실무적 관점에서 모든 제약 조건을 충족하면서도 전역 최적해가 필수적이지 않은 상황에서 CP의 제약 전파 알고리즘을 활용한 탐색이 시간 효율성 측면에서 우수함을 보였다. 본 연구 결과는 대학생들의 시간표 구성을 지원할 뿐만 아니라, 대학 행정 측면에서 대학생들의 시간표 추천 및 관리를 위한 실질적인 지침이 될 것으로 기대된다.

다만, 본 연구 결과를 타 대학 또는 다양한 환경에서 활용하기 위해서는 몇 가지 중요한 논의가 필요하다. 예를 들어, 교과목 구분을 교양필수/교양선택, 전공필수/전공선택으로 나누지 않는 대학의 경우, 교과목 특성을 분류할 수 있는 별도의 유연한 매핑 시스템을 설계하거나, 해당 대학의 분류 체계에 따라 가중치를 적용하는 방안을 검토할 수 있을 것이다. 또한, 본 연구에서 사용된 “영역”이라는 개념이 13개로 세분화된 A 대학의 경우와 달리, 단순한 영역 분류 체계를 가진 대학에서는 영역 수를 축소하거나 다른 대안적 분류 기준을 적용해 모델의 유연성을 높이는 방식으로 활용할 수 있을 것이다. 나아가, 수업 시간 구조가 상이하거나 수업 단위가 다른 대학의 경우에는 수업 시간 패턴과 단위를 모델 내에서 매개변수화하여 조정 가능한 형태로 설계함으로써 다양한 환경에 적용할 수 있을 것이다. 또한, 본 연구의 목적함수인 평균 선호도는 수강 과목의 학점 차이를 반영하지 못한다는 한계가 있으며, 적용 대상 대학의 수강 제도에 따라 학점을 가중치로 반영하거나 전체 수강 학점 조건을 도입하는 등 현실성 있는 조정이 필요할 수 있다. 이러한 다양한 차이를 고려한 일반화 과정과 적용 방안에 대한 논의는 본 연구의 활용성을 더욱 높일 수 있을 것이다.

또한, 본 연구에서 제안한 모델을 통해 출력되는 해의 강의 선호도 평균 측면에서의 성능과 탐색시간 간의 Trade-off에 대한 논의가 필요하다. 본 연구에서는 실제 현장 적용과 온라인 서비스 환경에서의 실용성을 주요 지표로 채택한 바 있다. 이에 따라 Search Time을 줄이기 위해서 시간 제한을 강의선호도 평균치가 4.5 이상인 해들을 찾을 수 있는 수준인 10초로 설정하였고 이로 인해 MIP 모델보다 강의 선호도 평균이 다소 낮은 해를 도출하였다.

한편, 제안된 방법론에 대해서만 명시적인 시간 제한(10초)을 설정한 반면, 비교 대상인 메타휴리스틱 기반 방법론(CP-LS, CP-SA)의 경우에는 파라미터 설정에 따라 유동적으로 결정되도록 설계하였다. 이는 각 방법론이 유사한 강의 선호도 평균을 달성하는 조건 하에서의 시간 소요를 비교하기 위한 목적하에 실험하였기 때문이다. MIP 또한 유사한 강의 선호도 평균을 달성하기 위한 최소한의 시간으로 설정하였다. 이러한 실험 목적으로 인해 시간 제한의 불일치로 인해 해석상의 한계점이 존재한다. 특히, 동일한 시간 내 탐색 성능을 비교하는 기준에서는 제한적일 수 있으며, 이는 본 연구의 실험 설계상 한계로 작용할 수 있다. 만약 강의 선호도 평균치가 더 중요한 상황이라면 시간 제한을 더 늘려 더 높은 강의 선호도 평균을 가진 해를 출력할 수 있다. 이러한 탐색시간과 성능의 Trade-off에 대한 논의를 통하여 본 연구의 사용 환경에 따른 적합성을 향상시킬 수 있을 것이다.

향후 연구과제로는 우선 실제 사용자 피드백을 통한 모델의 개선 및 검증을 들 수 있다. 본 연구에서는 도출된 강의 시간표의 품질에 대해 실제 사용자인 대학생들로부터 정성적인 만족도 평가를 수행하지 못하였다. 강의 시간표에 대한 만족도 평가를 통해 추가적인 제약 조건이나 개인 선호도 관련 정보가 확인될 경우, 이를 모델에 반영하여 사용자 만족도를 제고하는 것도 중요한 과제가 될 것이다. 또한 본 연구에서는 실제 온라인 서비스화를 고려하였으나 실제 온라인 서비스로 구현을 실현하지 못한 한계점이 존재한다. 실제 온라인 서비스로 구현하였을 때의 시간표 도출 시간을 고려할 수 있도록 실시간 처리 환경을 반영한 10초~1분 이내 응답이 가능한 구조적 개선에 대한 연구 또한 중요한 과제가 될 것으로 예상된다. 예를 들어 데이터 로딩, 사용자로부터 입력받을 사항들의 형식 및 구조 등이 주요한 고려사항들이 될 것으로 예상된다. 이러한 향후 연구과제를 수행한다면 단일 학과에서 더 나아가 단과대 또는 학교 전체 재학생을 대상으로 한 모델을 제안하는 것도 기대할 수 있다. 추가적으로 본 연구에서 제안한 방법론을 현장 적용이 중요한 다른 도메인의 조합 최적화 문제에 확장 적용하는 연구가 가능할 것이다. 이러한 후속 연구를 통해 본 연구의 실용성과 일반화 가능성을 더욱 높일 수 있을 것으로 기대된다.

Acknowledgments

이 논문은 부산대학교 기본연구지원사업(2년) 및 정부(과학기술정보통신부)의 재원으로 한국연구재단(데이터사이언스융합인재양성)의 지원을 받아 수행된 연구임(RS-2023-00242528).

References

• Abdullah, S., Turabieh, H., McCollum, B., and McMullan, P. (2010), A multi-objective post-enrolment course timetabling problem: A new case study, In Proceedings of the IEEE Congress on Evolutionary Computation, Barcelona, Spain: IEEE, 1-8. [https://doi.org/10.1109/CEC.2010.5586227]
• Algethami, H. and Laesanklang, W. (2021), A mathematical model for course time tabling problem with faculty-course assignment constraints, IEEE Access, 9, 111666-111682. [https://doi.org/10.1109/ACCESS.2021.3103495]
• Almeida, J., Santos, D. R. D., and Figueira, J. R. (2022), A multi-objective model for thesis defence scheduling, arXiv preprint, arXiv:2205.07727, .
• Aycan, E. and Ayav, T. (2009), Solving the course scheduling problem using simulated annealing, In Proceedings of the 2009 IEEE International Advance Computing Conference, Patiala, India: IEEE, 462-466. [https://doi.org/10.1109/IADCC.2009.4809055]
• Bockmayr, A. and Hooker, J. N. (2005), Constraint programming. In K. Aardal, G. L. Nemhauser, and R. Weismantel (Eds.), Handbooks in Operations Research and Management Science, Amsterdam, Netherlands: Elsevier, 12, 559-600. [https://doi.org/10.1016/S0927-0507(05)12010-6]
• Burke, E. K., Mareček, J., Parkes, A. J., and Rudová, H. (2010), Decomposition, reformulation, and diving in university course timetabling, Computers & Operations Research, 37(3), 582-597. [https://doi.org/10.1016/j.cor.2009.02.023]
• Cordis, A. S. and Pierce, B. (2017), The impact of class scheduling on academic performance in quantitative and qualitative business disciplines, Global Perspectives on Accounting Education, 14, 44-66.
• Garcia de la Banda, M. (2023), Beyond optimal solutions for real-world problems, In Proceedings of the 29th International Conference on Principles and Practice of Constraint Programming, Toronto, Canada: Springer, 1-4.
• Heipcke, S. (1999), Comparing constraint programming and mathematical programming approaches to discrete optimization: The change problem, Journal of the Operational Research Society, 50(6), 581-595. [https://doi.org/10.1057/palgrave.jors.2600730]
• Hooker, J. N. (2018), Constraint programming and operations research, In Proceedings of the 24th International Conference on Principles and Practice of Constraint Programming, Lille, France: Springer, 1-21. [https://doi.org/10.1007/978-3-319-98334-9]
• Kuan, Y., Obit, J., and Alfred, R. (2017), A constraint programming approach to solving university course timetabling problem (UCTP), Advanced Science Letters, 23(3), 1952-1955. [https://doi.org/10.1166/asl.2017.10211]
• Larabi-Marie-Sainte, S., Jan, R., Al-Matouq, A., and Alabduhadi, S. (2021), The impact of timetable on student's absences and performance, PLOS ONE, 16(6), e0253102. [https://doi.org/10.1371/journal.pone.0253256]
• Lewis, R. (2008), A survey of metaheuristic-based techniques for university timetabling problems, OR Spectrum, 30(1), 167-190. [https://doi.org/10.1007/s00291-007-0097-0]
• Li, W., Zhang, T., Wang, R., Huang, S., and Liang, J. (2023), Multimodal multi-objective optimization: Comparative study of the state-of-the-art, Swarm and Evolutionary Computation, 77, 101198. [https://doi.org/10.1016/j.swevo.2023.101253]
• Moallemi, C. C. and Patange, U. (2023), Hybrid scheduling with mixed-integer programming at Columbia Business School, INFORMS Journal on Applied Analytics, 53(3), 222-240. [https://doi.org/10.1287/inte.2022.0070]
• Musa, U. B. and Oyelakin, A. M. (2024), A survey of approaches for designing course timetable scheduling systems in tertiary institutions, Journal of Systems Engineering and Information Technology, 3(1), 1-6. [https://doi.org/10.29207/joseit.v3i1.5609]
• Ogris, V., Kristan, T., Škraba, A., Urh, M., and Kofjač, D. (2016), iUrnik: Timetabling for primary educational institutions in Slovenia, Interfaces, 46(3), 231-244. [https://doi.org/10.1287/inte.2016.0846]
• Rappos, E., Thiémard, E., Robert, S., and Hêche, J.-F. (2022), A mixed-integer programming approach for solving university course timetabling problems, Journal of Scheduling, 25(5), 567-583. [https://doi.org/10.1007/s10951-021-00715-5]
• Schaerf, A. (1999), A survey of automated timetabling, Artificial Intelligence Review, 13, 87-127. [https://doi.org/10.1023/A:1006576209967]
• Stadnik, W. and Nowak, Z. (2018), The impact of web pages' load time on the conversion rate of an e-commerce platform. In L. Borzemski, J. Świątek, and Z. Wilimowska (Eds.), Information Systems Architecture and Technology: Proceedings of 38th International Conference on Information Systems Architecture and Technology – ISAT 2017, Cham, Switzerland: Springer, 655, 155-164.
• Van Hoeve, W.-J. and Katriel, I. (2006), Global constraints. In F. Rossi, P. van Beek, and T. Walsh (Eds.), Handbook of Constraint Programming, Amsterdam, Netherlands: Elsevier, 169-208. [https://doi.org/10.1016/S1574-6526(06)80010-6]