사례기반추론을 이용한 스케줄링 문제에서의 유사도 학습

Abstract

사례기반추론은 과거의 유사한 사례를 기반으로 새로 발생한 문제를 해결하는 방법론으로, 계획 문제를 포함하여 의료 및 건강, 금융, 법, 전자학습에서 지식 관리나 추천 시스템에 이르기까지 다양한 분야에 적용되어 왔다. 성공적인 사례기반추론 시스템을 위해서는 사례 베이스의 효과적 관리, 사례의 적합한 표현 방식과 같은 다양한 요소들이 갖춰져야 하나, 그 중 사례 간 유사도는 해의 선택에 직접적인 영향을 끼친다는 점에서 그 중요성이 매우 높다고 할 수 있다. 본 연구는 사례기반추론에서 사례기반추론 시스템에서 일반적으로 사용되는 근접 이웃 방법 기반의 유사도를 학습하는 방법을 제시하고, 이를 사례기반추론을 이용한 스케줄링 문제를 중심으로 해결하였다. 이를 위한 혼합정수계획 및 비선형 계획 기반의 유사도 학습 방법론을 제안하였으며, 스케줄링 문제의 특징을 반영한 계층적 유사도를 기반으로 가장 어려운 스케줄링 문제 중 하나인 반도체 스케줄링 문제에 성공적으로 적용하였다. 제안된 학습 방법론은 기계 학습 분야에서 널리 사용되는 UCI 데이터 셋을 기반으로 평가되었으며, 실제 크기의 반도체 패키징 라인의 스케줄링 문제에 적용한 성능 비교도 함께 수행하였다. 계층적 유사도에서는 유사도 계산 시 스케줄링 문제에서 고려될 수 있는 다양한 특징을 반영하여 계층을 구분하고, 이를 다양한 조합으로 비교하였다. 이를 통하여 제안된 방법론이 기존 방법론에 비해 나음을 보였으며, 최종적으로 계층적 유사도를 통해 뛰어난 품질의 스케줄을 확보할 수 있었다.