Common Attribute Selection Problem: Formulation, Algorithm and Heuristic

• 영문명: Common Attribute Selection Problem: Formulation, Algorithm and Heuristic
• 발행기관: 한국생산관리학회
• 저자명: 김길선(Kilsun Kim) 김학진(Hak Jin Kim)
• 간행물 정보: 『한국생산관리학회지』韓國生産管理學會誌 第19卷 第2號, 123~146쪽, 전체 24쪽
• 주제분류: 경제경영 > 경영학
• 파일형태: PDF
• 발행일자: 2008.06.30

국문 초록

  본 연구는 복수의 제품속성을 이용한 제품군의 디자인에서의 공통속성을 선택하는 문제를 다루고 있다. 본 연구는 수익최대화를 목적함수로 하는 공통속성의 선택문제를 제안하고 있으며 이를 비선형 정수조합 최적화문제로 모형화하였다. 분석결과를 통해 본 연구가 다루는 문제가 NP-complete임을 보이고, 이러한 복잡한 문제의 해를 찾기 위해 효율적인 휴리스틱 절차를 제시하였다. 본 연구가 제안하는 휴리스틱은 먼저 기존연구결과를 토대로 문제자체가 이진정수계획모형으로 축소 전환될 수 있음을 보여준다. 그 축소 전환된 문제는 여전히 NP-complete이지만, 본 연구가 제시하는 해법은 최적해를 찾는데 사용될 경우 항상 전역최적해를 구할 수 있음을 보인다. 비선형정수조합최적화문제는 전역최적해를 찾아내는 일반적인 해법이 존재하지 않는 점을 감안 할 때, 본 연구는 그러한 면에서 일정부분 공헌을 하고 있다. 그러나 제시된 해법이 최적화를 찾는데 걸리는 시간이 문제의 크기에 따라서는 상당할 수 있기 때문에, 이진정수들을 대상으로 휴리스틱 절차를 통해 해를 찾아내는 탐욕적(greedy)절차를 제안한 뒤 실험을 통해 이 절차의 성능을 검증하였다. 제안된 탐욕적 휴리스틱 절차의 성과를 상대평가하기 위하여, 수리적 분석과정에서 얻은 문제구조에 대한 이해를 바탕으로 두 번째 휴리스틱절차도 같이 제시되었으며 그 성능도 같이 평가하였다. 실험결과에 따르면 두 휴리스틱은 상당히 우수한 성능을 보였는데, 사용된 2,400개의 예시문제들을 대상으로 했을 때 평균 99.85%와 97.58%의 최적해 대비 성능을 나타내었다. 특히, 탐욕적 휴리스틱은 두 번째 휴리스틱에 비해 훨씬 나은 최악(worst-case)성과를 보여주었다.

영문 초록

  The current paper addresses the issue of common attribute selection in product line design with multiple attributes. We propose a profit maximization model of common attribute selection problem and formulate it as a mixed integer nonlinear optimization problem. We show that the problem is NP complete and develop an efficient heuristic solution procedure. Our heuristic first involves a procedure where the problem is reduced to an integer program where only binary decision variables are remaining. While the resulting problem is still NP complete, the procedure, if used in finding an optimal solution, helps in avoiding a local optimal solution which is typical in nonlinear optimization problem. In order to obtain reasonably good solutions with reasonable amount of computational time, we next devise a greedy heuristic search algorithm over the binary variables and test the performance of the heuristic through an experimental study. In order to understand the usefulness of the heuristic, we also devise another singe­pass heuristic that is based on the analytic insights and test the performance of the second heuristic as well. Our experimental study statistically showed that both greedy and single­pass heuristics showed very good on­average performance, 99.85% and 97.58% of the optimal solutions respectively, across the experimental factors we considered and the greedy heuristic showed much better worst­case performance than the single­pass heuristic does.

목차

요약
1. Introduction
2. Model
3. Complexity Result and Existence of Global Optimal Solution Procedure
4. Heuristic Search Algorithms
5. Design of Experimental Study
6. Results
7. Conclusion
References
Appendix
Abstract
저자소개

키워드

Product Line Design Commonality Modeling Heuristic Computational Study