수직적 제품군 디자인문제의 일반화에 대한 연구

An Extended Study on the Vertical Product Line Design Problem

본 논문은 수직적 제품군 디자인에 관한 기존 연구의 검증과 일반화에 관한 논문으로서 다음의 두 가지 목적을 위해 수행되었다. 첫째, 본 논문은 Chhajed and Kim (2005)이 제시한 수직적 제품군의 디자인에 관한 모형을 일반화한 뒤, 이 일반화된 모형이 NP-complete임을 보이고, 모형을 분석함에 있어 어려움이 발생하는 이유를 밝힌다. 둘째, Chhajed and Kim (2005)의 논문은 분석 가능한 수직적 제품군 디자인 모형을 수립하고, 이를 통해 이론적인 결과들을 도출하는데 있는 반면, 본 논문의 초점은 Chhajed and Kim (2005)에서 제시된 휴리스틱의 성능을 포괄적인 실험설정을 통해 이론적으로 검증하는데 있다. 실험결과에 따르면, 휴리스틱은 성능은 매우 우수하여 평균적으로 99.54%의 최적해를 도출하며, 이러한 결과는 다양한 실험상황하에서도 일관되게 나타난다.

In this paper, we validate and generalize the results from the study of the vertical product line design problem in literature, and pursue the following two purposes. First, we develop a generalized version of the vertical product line design problem that was introduced in Chhajed and Kim (2005), show that the problem is NP-complete, and discuss the analytic and computational challenges that are involved in dealing with the generalized problem. Second, while the main focus in Chhajed and Kim (2005) was on the development of an analytically tractable model of vertical product line design problem and on derivation of theoretical results from the model, the main focus of the current paper is to formally test the goodness of the heuristic developed in Chhajed and Kim (2005) using a comprehensive experimental framework. We show that the on-average performance of the heuristic is very good, 99.54% of the optimal solution, and is robust across diverse experimental settings with practical considerations. Furthermore we also discuss why the suggested heuristic cannot be easily applied to a generalized vertical product line design problem.