Abstract: For on the rectangular items cutting stock problem, an optimization algorithm based on
two-segment patterns is proposed. Firstly, a constrained packing algorithm is constructed to generate
the two-segment patterns of rectangular items on the plate. Then, column generation algorithm is used
to generate a virtual cutting plan according to the current remaining demand of rectangular items,
several patterns are added into actual cutting plan according to the rule that no redundant rectangular
item is generated, and the current remaining demand of rectangular items is updated. The above steps
are repeated until the remaining demand of rectangular items is zero. Compared the proposed
algorithm with two algorithms in the literature through benchmark instances, results of numerical
experiments show that material utilization of the proposed algorithm is higher than two literature
algorithms about 1.61% and 0.78%, respectively.

Key words: cutting stock problem, two-segment patterns, column generation algorithm, constrained
packing, rectangular items