2차원 길로틴 절단문제를 위한 향상된 최적-우선 분지한계법

Abstract

본 연구는 하나의 큰 직사각형 자재에서 가치를 가진 여러 크기의 작은 직사각형 부품들을 절단할 때, 절단된 부품 가치의 합을 최대화하는 2차원 절단문제를 다룬다. 잘라내야 하는 부품 개수 제한이 있는 제한 문제와 없는 무제한 문제를 구분하여 최적해법을 제안한다. 두 문제 모두 부품의 가치는 넓이로 정하거나 다른 기준으로 정할 수 있고, 절단 단계수는 무제한이며, 길로틴 절단이다. 분지한계법의 효율을 향상하기 위해 최적해에 영향을 주지 않는 열등패턴의 개념을 확장하여 이를 제거하거나 생성을 줄이는 방법을 제안한다. 절단패턴 중에서 크기와 부품의 조합이 같은 중복패턴을 방지하는 방법을 제안한다. 분지끝을 판별하기 위한 상한을 개선하고, 하나의 절단패턴이 아닌 절단패턴 집합을 분지끝으로 판단할 수 있는 한계전략을 제안한다. 또한, 해법의 효율을 향상시킬 수 있는 자료구조를 제안한다. 제안 해법과 기존 해법을 비교 실험한 결과, 제안 해법은 기존의 모든 실험 문제에서 기존 해법보다 빨랐다. 개수 제한이 없는 문제에 대해 평균 96% 이상 계산 시간을 감소시켰고, 제한 있는 문제에 대해 평균 99% 계산 시간을 감소시켰다. 또한, 기존 최적 해법이 풀지 못한 두 개의 대형 문제에서 최적해를 구했다.