비가중 무제한 2차원 절단문제에 대한 최적-우선 분지한계 해법

Abstract

In this paper, a best-first branch and bound algorithm based upon the bottom-up approach for the unweighted unconstrained two-dimensional cutting problem is proposed to find the optimal solution to the problem. The algorithm uses simple and effective methods to prevent constructing duplicated patterns and reduces the searching space by dividing the branched node set. It also uses a efficient bounding strategy to fathom the set of patterns. Computational results are compared with well-known exact algorithms and demonstrate the efficiency of the proposed algorithm.