소형제품이 포함된 무제한 2차원 절단 문제에 대해 최적-우선 분지한계법을 이용한 순환해법

Abstract

2차원 절단 문제는 하나의 큰 직사각형 자재를 가치가 주어진 다양한 크기의 작은 직사각형 제품으로 절단할 때, 절단된 제품 가치의 합을 최대화하는 문제이다. 이 문제는 생산 원가절감에 직접적으로 도움이 되어 광범위한 분야에서 응용한다. 2차원 절단 문제는 NP-complete 문제이나 최적 해법이 많이 연구되었다. 본 연구에서는 제품수에 제한이 없는 무제한 2차원 절단 문제 중에서 특히 소형제품이 포함된 경우의 문제를 다룬다. 2차원 절단 문제의 해법은 G et al.이 제안한 최적-우선 분지한계법과 Hifi와 Zissimopoulos가 제안한 순환해법이 대표적이다. 대부분의 문제에서는 최적-우선 분지한계법이 더 효율이 좋으나 소형제품이 포함된 문제에서는 순환해법이 더 효율이 좋다. 본 연구에서 제안하는 해법은 순환해법을 바탕으로 최적-우선 분지한계법을 이용한다. 먼저 최적-우선 분지한계법으로 부분해를 구하고 여기서 산출된 부분해를 이용하여 순환해법을 수행한다. 이 해법은 부분해를 이용하므로 분지 횟수와 수행시간을 줄인다. 제안하는 해법은 대부분의 문제에서 순환해법보다 빠르게 해를 구하였다.