Establishing the optimality of sequencing heuristics for cutting stock problems

Cutting stock problems typically involve the generation of feasible cutting patterns whilst minimizing waste. In some instances the sequence of cutting these patterns is important. One objective of the sequencing stage is to minimize the maximum queue of partially cut orders. This paper presents two exact methods to meet this objective and to determine the optimality of previously introduced sequencing heuristics. The first and more simple method is based on the Lower Bound. The other, a more general method, is an implicit exhaustive search procedure. Various enhancements are introduced which allow sets of up to thirty pattern types to be successfully searched. Aspects of graph theory have been utilised to minimise the size of sets of patterns to be searched. Computing experience is reported for determining optimality.