Earticle

초록

한국어

신발이나 의류 등에 부착되는 라벨(label)은 먼저 고정 개수의 라벨이 배치된 템플릿(template)을 제작한 후 각각의 템플릿을 필요한 수량만큼 인쇄하여 생산한다. 이때 템플릿 내의 레이블 조합 방법에 따라 불필요한 초과생산이 발생하게 된다. 본 논문에서는 이 과정을 하나의 최적화 문제로 정형화하고, NP-hard임을 증명한 후, 의사 다항시간(pseudo-polynomial time)의 근사(approximation) 알고리즘을 제시한다. 알고리즘은 기본적으로 탐욕적(greedy) 기법을 따르며 알고리즘의 각 단계에서 동적 계획법(dynamic programming)을 이용한다. 다양한 실험 데이터를 통해 제시한 알고리즘의 성능을 평가하였다.

영어

Labels of clothes or shoes are produced by making templates containing a fixed number of labels of different types and printing them multiple times. The composition of label types in templates determines the production loss which is defined to be the over-produced quantities. In this paper, we formulate this into an optimization problem and prove its NP-hardness. Then we present a pseudo-polynomial time approximation algorithm. Our algorithm takes a greedy approach and each step of it solves a sub-problem using dynamic programming technique. We tested the algorithm for a variety of sample data and analysed its performance.

목차

요약
 Abstract
 1. 서론
 2. 관련연구 및 시간복잡도
 3. 알고리즘
  3.1 개요
  3.2 최적 템플릿 찾기
  3.3 지정된 개수 이상의 라벨 타입을 커버하는 최적 템플릿 찾기
  3.4 템플릿 별로 라벨 수의 하한값 결정하기
 4. 성능분석
 5. 결론
 참고문헌

저자

• 권오흠 [ Oh-Heum Kwon | 부경대학교 IT융합응용공학과 ]
• 송하주 [ Ha-Joo Song | 부경대학교 IT융합응용공학과 ] 교신저자

참고문헌