Abstract: This paper discusses the two dimensional sheet cutting stock problem, that is, use the least
number of sheets to cut out a certain number of rectangular pieces. A deterministic algorithm is
proposed which based on the combination of knapsack algorithm and linear programming algorithm.
First, a knapsack algorithm is constructed to generates the four blocks uniform strip pattern, then the
linear programming algorithm is used to generate the cutting plans which iteratively calls the above
knapsack algorithm to improve the objective function based on the principle of minimum production
cost and changes the current value of punched items to generate a new pattern according to the
current value. Lastly, a set of optimal cutting patterns is selected to form the cutting scheme. The
algorithm was compared with the famous T-shape algorithm using some benchmark problem tests.
The results show that the algorithm can save more sheets than the T-shape one, and the calculation
time is reasonable in practical application.

Key words: two-dimensional cutting, rectangle cutting stock, knapsack algorithm, linear
programming algorithm