라벨 패킹 문제를 위한 근사 알고리즘
An Approximation Algorithm for Label Packing Problem
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
신발이나 의류 등에 부착되는 라벨(label)은 먼저 고정 개수의 라벨이 배치된 템플릿(template)을 제작한 후 각각의 템플릿을 필요한 수량만큼 인쇄하여 생산한다. 이때 템플릿 내의 레이블 조합 방법에 따라 불필요한 초과생산이 발생하게 된다. 본 논문에서는 이 과정을 하나의 최적화 문제로 정형화하고, NP-hard임을 증명한 후, 의사 다항시간(pseudo-polynomial time)의 근사(approximation) 알고리즘을 제시한다. 알고리즘은 기본적으로 탐욕적(greedy) 기법을 따르며 알고리즘의 각 단계에서 동적 계획법(dynamic programming)을 이용한다. 다양한 실험 데이터를 통해 제시한 알고리즘의 성능을 평가하였다.
Abstract
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.
참고문헌 (6)
- K. R. Baker, "Introduction to sequencing and scheduling" (1974), John Wiley & Sons
- M. Garey, "Computers and Intractability: A guide to the NP-Completeness" (1979), W. H. Freemac and Company
- J. Kleinberg, "Algorithm Design" (2006), Addison Wesley
- 윤현철, "동적 최장공통비상위문자열 문제 해결 알고리즘", 한국차세대컴퓨팅학회 논문지, 6(6), pp.35~43 (2010), 한국차세대컴퓨팅학회
- 조문행, "내장형 시스템을 위한 경량 실시간 스케줄링 기법의 설계 및 구현", 한국차세대컴퓨팅학회논문지, 3(3), pp.5~12 (2007)
- 공민식, "시간적 지역성을 이용한 저전력 실시간 태스크 스케쥴링", 한국차세대컴퓨팅학회 논문지, 2(2), pp.32~38 (2006)