The Journal of Korean Institute of Next Generation Computing (한국차세대컴퓨팅학회논문지)

Korean Institute of Next Generation Computing (한국차세대컴퓨팅학회)
권호 표지

Improved Approximation Algorithm Based on Branch-and-Bound Technique for Label Packing Problem

라벨 패킹 문제를 위한 분기한정법에 기반한 개선된 근사 알고리즘

  • 권오흠 (부경대학교 IT융합응용공학과) ;
  • 송하주 (부경대학교 IT융합응용공학과)
  • Received : 2014.07.29
  • Accepted : 2014.10.17
  • Published : 2014.10.31
⟨ Previous Next ⟩

Abstract

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개 정도의 소수의 템플릿을 사용하는 경우에 대해서 최적 해를 찾는 분기한정법 탐색 알고리즘을 제시하고, 템플릿의 개수가 많을 경우 문제를 작은 규모의 부분 문제들로 분할하여 해결하는 휴리스틱을 제시한다. 다양한 실험 데이터를 통해 제시한 알고리즘의 성능을 평가하였으며 선행 연구에서 제시된 알고리즘과 비교하였다.

Keywords

Acknowledgement

Supported by : 부경대학교

References

  1. K. R. Baker, Introduction to sequencing and scheduling, John Wiley & Sons, New York, 1974.
  2. M. Garey and D. S. Johnson, Computers and Intractability: A guide to the NP-Completeness, W. H. Freemac and Company, New York, 1979.
  3. J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, New York, 2006.
  4. Reuven Cohen, Liran Katzir, and Danny Raz, "An Efficient Approximation for the Generalized Assignment Problem", Information Processing Letters, Vol. 100, Issue 4, pp. 162-166, November 2006. https://doi.org/10.1016/j.ipl.2006.06.003
  5. Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko, "Tight Approximation Algorithms for Maximum General Assignment Problems", SODA 2006, pp. 611-620.
  6. 권오흠, 송하주, "라벨 패킹문제를 위한 근사알고리즘", 한국차세대컴퓨팅학회 논문지, 제10권 제3호, 2014년 6월, pp.62-72.
  7. 조문행, 이철훈, "내장형 시스템을 위한 경량 실시간 스케줄링 기법의 설계 및 구현", 한국차세대컴퓨팅학회논문지, 제3권 제3호, 2007년 9월. pp. 5-12.
  8. 공민식, 정명조, 김용희, 성영락, 이철훈, "시간적 지역성을 이용한 저전력 실시간 태스크 스케쥴링", 한국차세대컴퓨팅학회 논문지, 제2권 제2호, pp.32-38, 2006년 6월.