earticle

영어

The label packing problem is to compose one or more templates each of which consists of a fixed number of labels of different types and print them multiple times to produce the required amount of labels. The goal is to minimize the over-produced quantities. In our earlier work [6], we proved that this problem is NP-hard and proposed an approximation algorithm based on greedy approach. In this paper, we present an improved approximation algorithm. We first give an optimal algorithm based on branch-and-bound search technique that is applicable when the number of template is a small constant. For the general cases where the number of templates is large, we partition the problem into small subproblems, solve each subproblem using the optimal algorithm, and then merge the results. We tested the algorithm for a variety of sample data and analyse its performance.

한국어

라벨 패킹 문제는 고정된 개수의 라벨이 배치된 하나 혹은 그 이상의 템플릿을 반복 인쇄함으로써 라벨들을 생산할 때 초과 생산량이 최소가 되도록 템플릿을 구성하는 최적화 문제이다. 선행연구에서 이 문제가 NP-hard임이 밝혀 졌으며, 탐욕적 기법에 기반한 의사 다항시간의 근사알고리즘이 제안되었다[6]. 본 논문에서는 이 문제를 해결하기 위한 또 다른 근사 알고리즘을 제시한다. 먼저 3~4개 정도의 소수의 템플릿을 사용하는 경우에 대해서 최적 해를 찾는 분기한정법 탐색 알고리즘을 제시하고, 템플릿의 개수가 많을 경우 문제를 작은 규모의 부분 문제들로 분할하 여 해결하는 휴리스틱을 제시한다. 다양한 실험 데이터를 통해 제시한 알고리즘의 성능을 평가하였으며 선행 연구에 서 제시된 알고리즘과 비교하였다.