최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기정보처리학회논문지. The KIPS transactions. Part B. Part B, v.16B no.5, 2009년, pp.403 - 410
연용호 (목원대학교 공학교육혁신센터) , 이선영 (충북대학교 컴퓨터교육과) , 이종연 (충북대학교 컴퓨터교육과)
The two-dimensional bin packing problem(2D-BPP) has been known to be NP-hard, and it is difficult to solve the problem exactly. Many approximation methods, such as genetic algorithm, simulated annealing and tabu search etc, have been also proposed to gain better solutions. However, the existing appr...
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
2차원 저장소 적재는 어떤 문제로서 정확한 해를 구하는 것이 어려운가? | 2차원 저장소 적재는 NP-hard 문제로서 그 문제의 정확한 해를 구하는 것이 어려운 것으로 알려져 있으며, 이의 더 좋은 해를 얻기 위해 유전자(genetic) 알고리즘, 시뮬레이티드 어닐링(simulated annealing), 타부서치(tabu search)등과 같은 근사적 접근법이 제안되어 왔다. 하지만 분지한계(branch-and-bound)나 타부서치 기법들을 이용한 기존의 대표적인 근사 알고리즘들은 휴리스틱 알고리즘의 해에 기반을 둠으로 효율성이 낮고 반복수행에 의한 계산시간이 길다. | |
2차원 저장소 적재문제보더 더 좋은 해를 얻기 위해 무엇들이 제안되었는가? | 2차원 저장소 적재문제는 강한 NP-hard 문제로 이 문 제들의 정확한 해를 구하는 것은 어렵다. 따라서 기존의 많은 연구들은 더 좋은 해를 얻기 위해 휴리스틱(heuristic) 또는 메타휴리스틱(meta-heuristic)등과 같은 근사 알고리즘들 [4, 6, 11, 15-17]을 제안한 바 있다. 하지만 분지한계나 타부 서치 기법들을 이용한 기존의 대표적인 근사 알고리즘들은 휴리스틱 알고리즘의 해에 기반을 둠으로 효율성이 낮고 복수행에 의한 계산시간이 길다. | |
기존의 대표적인 근사 알고리즘들은 어떤 문제가 있는가? | 2차원 저장소 적재는 NP-hard 문제로서 그 문제의 정확한 해를 구하는 것이 어려운 것으로 알려져 있으며, 이의 더 좋은 해를 얻기 위해 유전자(genetic) 알고리즘, 시뮬레이티드 어닐링(simulated annealing), 타부서치(tabu search)등과 같은 근사적 접근법이 제안되어 왔다. 하지만 분지한계(branch-and-bound)나 타부서치 기법들을 이용한 기존의 대표적인 근사 알고리즘들은 휴리스틱 알고리즘의 해에 기반을 둠으로 효율성이 낮고 반복수행에 의한 계산시간이 길다. 따라서 본 논문에서는 이러한 근사 알고리즘의 복잡성을 간소화하고, 알고리즘의 효율성을 높이기 위해 적재가능성을 판단하는 적합성 함수(fitness function)를 정의하고 이를 이용하여 어떤 특정 개체의 적재영역을 판단하는데 영향을 주는 적재영역의 수를 계산한다. |
B. E. Bengtsson, Packing rectangular pieces-a heuristic approach, The Computer Journal Vol.25, No.3, pp.353-357, 1982
J. E. Beasley, Algorithms for unconstrained two-dimensional guillotine cutting, Journal of Operational Research Society, Vol.36, pp.297-306.
J. E. Beasley, An exact two-dimensional non-guillotine cutting tree search procedure, Operations Research, Vol.33, pp.49-64, 1985.
J. O. Berkey and P. Y. Wang, Two dimensional finite bin packing algorithms Journal of the Operational Research Society 38, pp.423-429, 1987.
N. Christofides and C. Whitlock, An algorithm for twodimensional cutting problrems, Operations Research, Vol.25, pp.30-44, 1977.
F. K. R. Chung, M. R. Garey and D. S. Johnson, On Packing two-dimensional bins, SIAM Journal of Algebraic and Discrete Methods, Vol.3, No.1, pp.66-76, 1982.
M. Dell'Amico and S. Martello, Optimal scheduling of tasks on identical parallel processors, ORSA Journal on Computing, Vol.7, No.2, pp.191-200, 1995.
M. Dell'Amico, S. Martello and D. Vigo, A lower bound for the non-oriented two-dimensional bin packing problem, Discrete Applied Mathematics, Vol.118, pp.13-24, 2002.
H. Dyckhoff, A typology of cutting and packing problems, European Journal of Operational Research, Vol.44, No.2, pp. 145-159, 1990.
H. Dyckhoff and G. Finke, Cutting and packing in production and distribution, Physica Verlag, Heidelberg, 1992.
A. El-Bouri, N. Popplewell, S. Balakrishnan and A. Alfa, A search based heuristic for the two-dimensional bin-packing problem, INFOR, Vol.32, No.4, pp.265-274, 1994.
P. C. Gilmore and R. E. Gomory, Multistage cutting problems of two and more dimensions, Operations Research, Vol.13, No.1, pp.94-120, 1965
E. Hadjiconstantinou and N. Christofides, An Exact algorithm for general, orthogonal, two-dimensional knapsack problem, European Journal of Operational Research, Vol.83, pp.39-56, 1995.
A. Lodi, S. Martello and M. Monaci, Two-dimensional packing problems: a survey, European Journal of Operational Research, Vol.141, pp.241-252, 2002.
A. Lodi, S. Martello, and D. Vigo, Neighborhood search algorithm for the guillotine non-oriented two-dimensional bin packing problem, in: S. Martello, I. H. Osman, C. Roucairol (Eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, Boston, pp.125-139, 1998.
A. Lodi, S. Martello and D. Vigo, Approximation algorithms for the oriented two-dimensional bin packing problem, European Journal of Operational Research, Vol.112, 158-166, 1999.
A. Lodi, S. Martello and D. Vigo, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS Journal of Computing, Vol.11, No.4, pp. 345-357, 1999.
A. Lodi, S. Martello, D. Vigo, Ricent advances on twodimensional bin packing problems, Discrete Applied Mathematics 123, pp.373-390, 2002.
S. Martello, M. Monaci and D. Vigo, An exact approach to the strip packing problem, Informs Journal on Computing, Vol.15, 310-319, 2003.
S. Martello and P. Toth, Lower bounds and reduction procedures for the bin packing problem, Discrete Applied Mathematics, Vol.28, pp.59-70, 1990.
S. Martello and D. Vigo, Exact solution of the two dimensional finite bin packing problem, Management Science, Vol.44, pp. 388-399, 1998.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
출판사/학술단체 등이 한시적으로 특별한 프로모션 또는 일정기간 경과 후 접근을 허용하여, 출판사/학술단체 등의 사이트에서 이용 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.