템플릿 패킹 문제에 대한 최적-적합 전략을 사용한 근사 알고리즘
An approximation algorithm using best-fit strategy for template packing problem1)
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
이 논문에서는 서로 다른 종류의 아이템들을 생산하기 위해서 필요한 템플릿을 구성하는 것과 관련된 일종의 패킹문제를 다룬다. 고정된 개수의 아이템이 배치된 하나 혹은 그 이상의 템플릿을 반복 인쇄함으로써 요구된 수량의 아이템들을 생산한다. 문제의 목적은 초과 생산량이 최소가 되도록 아이템들을 템플릿에 배치하는 것이다. 이 문제는NP-hard임이 밝혀져 있으며, 탐욕적 기법과 분기한정법에 기반한 근사 알고리즘이 알려져 있다. 본 논문에서는 이문제를 해결하기 위하여 잘 알려진 최적-적합 전략을 이용한 또 다른 다항시간 근사 알고리즘을 제시한다. 다양한실험 데이터를 통해 제시한 알고리즘의 성능을 평가하였으며 선행 연구에서 제시된 알고리즘과 비교하였다.
Abstract
This paper deals with a kind of packing problem of which the goal is to compose one or more templates which will be used to produce the items of different types. Each template consists of a fixed number of slots which are assigned to the item types and the production of the items is accomplished by printing the template repeatedly. The objective is to minimize the total number of produced items. This problem is known to be NP-hard. Approximation algorithms based on either greedy approach or branch-and-bound technique have been proposed. We present another polynomial time approximation algorithm based on the well-known best-fit strategy. We perform experiments to compare the performance of the proposed algorithm with the previous ones.
참고문헌 (9)
- R. Cohen, "An Efficient Approximation for the Generalized Assignment Problem", Information Processing Letters, 100(4), pp.162~166 (2006)
- J. Du, "Complexity of scheduling parallel task systems", SIAM J. Discrete Math, 2(4), pp.473~487 (1989)
- L. Fleischer, "Tight Approximation Algorithms for Maximum General Assignment Problems", Proceedings of Symposium on Discrete Algorithms, pp.611~620 (2006)
- M. Garey, "Computers and Intractability: A guide to the NP-Completeness" (1979), W. H. Freemac and Company
- A. Lodi, "Recent advances on two-dimensional bin packing problems", Discrete Applied Mathematics, 123(3), pp.379~396 (2002)
- 공민식, "시간적 지역성을 이용한 저전력 실시간 태스크 스케쥴링", 한국차세대컴퓨팅학회 논문지, 2(2), pp.32~38 (2006)
- 권오흠, "라벨 패킹 문제를 위한 분기한정법에 기반한 개선된 근사 알고리즘", 한국차세대컴퓨팅학회 논문지, 10(5), pp.13~24 (2014), 한국차세대컴퓨팅학회
- 윤현철, "동적 최장공통비상위문자열 문제 해결 알고리즘", 한국차세대컴퓨팅학회 논문지, 6(6), pp.35~43 (2010), 한국차세대컴퓨팅학회
- 조문행, "내장형 시스템을 위한 경량 실시간 스케줄링 기법의 설계 및 구현", 한국차세대컴퓨팅학회논문지, 3(3), pp.5~12 (2007)