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

Abstract

In this paper, we develop an improved branch and bound algorithm for the (un)weighted unconstrained two-dimensional cutting problem. In the proposed algorithm, we improve the branching strategies of the existing exact algorithm and reduce the size of problem by removing the dominated pieces from the problem. We apply the newly proposed definition of dominated cutting pattern and it can reduce the number of nodes that must be searched during the algorithm procedure. The efficiency of the proposed algorithm is presented through comparison with the exact algorithm known as the most efficient.