2차원 길로틴 절단문제를 위한 새로운 상한

Abstract

The two-dimensional guillotine cutting problem is to maximize sum of piece profits that cut from one stock rectangle and widely applied in the industry. the pranch-and-bound method for this problem uses complementarily several upperbounds(the Gilmore and Gornory's two-dimensional knapsack function and the Hifi and Zissimopoulos's method using one-dimensional knapsack problem, etc) to reduce the number of searched nodes. These upper bounds has a shortcoming that does not consider the bound which can complement the shortcoming of existing upper bounds. The proposed upper bound needs less memory spaces and computing time. Cornputational results show that the proposed upper bound significantly contribute to reduce the computational amount of time and number of searched nodes in tree.