Novel Constant-Factor Approximation Algorithm for the Two-Dimensional Rectangular Cutting Problems

Recently the problem of two-dimensional (rectangular) cutting has been one of the famous problems which have attracted many researchers’ attention and several methods for its optimization have been presented. The two-dimensional cutting problem can be solved by using algorithms for the two-dimensional knapsack problem. In the two-dimensional cutting problem, there is a large rectangular piece which is considered as the main piece and also there are some other rectangular pieces with smaller areas than the main piece. The purpose of this problem is to cut the largest rectangular sheet so that the smaller sheets can be produced while the resulted wastes to be minimized. Solving the problem of two dimensional cutting is really important in each industry in which sheet cutting is required, because of minimizing the wastes. The existing precise algorithms for solving this problem possess exponential time complexity. In fact, this is a NP-hard problem. Consequently, a precise algorithm is not practically useful especially with a lot of inputs. So other methods should be used to solve these problems. One of them is approximation algorithms. The main contribution of this paper with the aim of reducing wasted parts is to present an approximation algorithm with approximation ratio, where the height and width of each piece is at most K. The computational results also verify the improvements of our algorithm.

کلیدواژه ها:

2-dimensional cutting problem ، approximation algorithm ، approximation ratio