Pattern reduction in one-dimensional cutting stock problems

In industrial cutting operations the number of cutting patterns needed to satisfy a given set of orders may be crucial for the capacity load which can be achieved for the cutting equipment, since switching between different patterns often necessitates time-consuming set-ups. Therefore, in planning the cutting operations, one does not necessarily search for input-minimal cutting plans (i.e. cutting plans minimizing material costs) only, but also for plans with a small (or even minimal) number of cutting patterns. Such plans are usually generated in a two-step approach: in a first step, regardless of the number of patterns needed, an input-minimal cutting plan is generated while in a second step the number of patterns is reduced. In this paper a new method for the second step is presented, which can be considered as a generalization of other methods previously suggested for this purpose. The performance of the new method is evaluated on the basis of 1800 randomly generated problem instances. The solution quality of the new method turns out to be clearly superior to the existing methods, however, an increase in computing times occurs for some problem classes. In this case it is possible to speed up the proposed method considerably at the expense of a slight decrease in solution quality.