Bounds for a problem of sequencing patterns

In some wood cutting settings, the cutting sequence of the patterns produced to minimize trim waste and satisfy customers' requirements is important. Each different part size cut is put into a stack which is removed only after the last part of that size is cut. It is desired to minimize the maximum number of stacks often because of space limitations and/or material handling problems. This problem can be viewed as a graph traversing problem and we propose a heuristic procedure that generates a solution based on an arc contraction scheme. Using this scheme, a possible way of computing a lower bound for this problem is also suggested. Limited computational results are presented to assess the quality of these bounds.